On Tuesday, August 8, 2023 at 5:50:16 PM UTC+2 Edward K. Ream wrote:
On Tuesday, August 8, 2023 at 10:27:14 AM UTC-5 Edward K. Ream wrote:
> c.all_positions_for_v shows how to generate all *positions* p such that
p.v == v.
This method "reconstitutes" positions using only VNode operations. But this
trick is only mildly interesting.
Maybe it is just mildly interesting to you, but it is orders of magnitude
faster than what you propose as a "straightforward" solution. Don't believe
me? In a tree with 100 nodes your linear search will visit 100 positions
minus number of v descendants multiplied by the number of found positions.
If a v is found only once in a tree (which is most common scenario), and
lets say v has in total 10 descendants (which is 10% of the tree), your
solution will look in 90 positions, while c.all_positions_for_v will find a
unique position by visiting only p.level() nodes.
Put the following script in a node inside LeoPy.leo and execute to see the
difference for yourself:
# ======================================================
import time
allvnodes = set(z.v for z in c.all_positions())
def all_positions_for_v(v):
for p in c.all_positions():
if p.v == v:
yield p.copy()
def measure(name, f):
t1 = time.perf_counter_ns()
for i, v in enumerate(allvnodes):
f(v)
dt = (time.perf_counter_ns() - t1)/1e6
if dt > 60000:
g.es(f'too slow: average time: {dt/i:.2f}ms')
break
else:
g.es(f'Total for {name} is {dt:.2f}ms')
g.es(f'Average for {name} is {dt/len(allvnodes):.2f}ms')
def using_p(v):
return list(all_positions_for_v(v))
def using_v(v):
return list(c.all_positions_for_v(v))
measure('using_v', using_v)
measure('using_p', using_p)
#--------------------------------------------------------------
On my machine this gives the following output:
Total for using_v is 148.46ms
Average for using_v is 0.01ms
too slow: average time: 26.26ms
So, the "straightforward" solution, using position generators is about 2600
times slower than the code using only v nodes generators.
Instead, the following straightforward generator yields positions in
outline order:
def all_positions_for_v(self, v: VNode) -> Generator:
c = self
for p in c.all_positions():
if p.v == v:
yield p.copy()
Afaik no part of Leo uses this code. Perhaps the PR should delete it.
The idea that generator using v nodes should be deleted because it isn't
used, and your remark that
> - v.self_and_subtree contains no recursion and no "yield from" statements
explains a lot to me. Not that I understand why it matters to you that
"yield from" is not being used, but I now understand a little better your
unwillingness to accept my ideas. You just don't see how much of
unnecessary work is being done under the hood of p generators. Yes, they
might seem a bit shorter or perhaps more useful or more straightforward on
the surface, but they are just hiding a lot of unnecessary complexity deep
down, while having simple and innocent appearance.
In all my code related to Leo and outlines, I've always used short helper
generators defined inside the body of the function that uses them. In most
cases the resulting code was shorter and much faster than the equivalent
code based on p generators.
I think that v generators should be used everywhere instead of the much
slower code that is usually used, but it is your call.
Vitalije
PS: By the way, "yield from" is just a shorter form that doesn't require
you to explicitly name item that you are yielding from the generator. Much
like lambda allows you to define function without explicitly naming it if
it is used in just one place.
yield from xs
# is the same as
for x in xs:
yield x
# but doesn't require inventing a new name for item x
--
You received this message because you are subscribed to the Google Groups
"leo-editor" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/leo-editor/23ea67d7-7a9a-4c6b-9b4c-0d8596c9662fn%40googlegroups.com.
