I think what is happening is:
The visualizer makes it look like the stack is being re-created each
time an item is retrieved.
Indeed, a bunch of stack frames are being put on top of the stack, so in
that sense, the stack is being re-created.
However these frames are not new, they were previously removed from the
stack (when a "yield" was done) and saved away as part of the state of
the generator objects. So the stack is just being efficiently put back
to the state it was in when the previous item was returned. (Well,
fairly efficiently.)
Another way to explain the generator magic: "yield" causes the current
stack frame to be saved away so it can be resumed later. When the
caller requests another item, the stack frame returns to the top of the
stack and continues running where it left off. If that stack frame was
in the process of traversing a nested generator, then it will request
another item in turn, causing an additional saved frame to be added back
onto the stack, etc., until the whole stack is set up again.
Your generator code looks really close to doing what you want...
I think Trie.items() should not do "yield char" though, it should yield
the full name of the item, or maybe a (name, value) pair.
This may mean adding a prefix argument to Trie.items() so the full name
will be available.
Hope that helps, feel free to query more...
Jonathan
On 09/04/2013 12:03 AM, Mark Harviston wrote:
This may be an artifact of for .. in .. yield vs a yield from. I don't have
too much experience with the visualizer (I usually use pdb to step through
code if I need to).
yield from is the "correct" way to call a generator from another generator
and yield the other generators results. (but it only works on Python 3),
and it does a better job of traversing the call-stack.
PEP 380 (http://www.python.org/dev/peps/pep-0380/) has decent information
on yield from, though it's a bit technical.
For a Trie or any Tree, traversing would have to be done this way or
perhaps with visitor/walker pattern. as in trie.walk(lambda node:
print(node)), but that isn't very Pythonic.
Look up tree traversals (pre-order, post-order, in-order, etc.), they all
use recursion somehow.
On Tue, Sep 3, 2013 at 11:41 PM, Maria McKinley <mar...@mariakathryn.net>wrote:
So, when I look at this code with the visualizer, it looks like the code
is essentially re-creating the call stack every time through. Looking at
the code structure, this sort of makes sense to me, since I think recursion
with a generator means you are essentially creating a new generator every
time through, so you are yielding to more and more generators each time
through. But, it seems crazy. I thought the whole point of generators is
that they remember where they were, so why is the whole stack being
re-created every time? Or have I just totally mis-understood what is going
on with the visualizer and/or the generator? Is there a better way to
traverse the Trie? I did end up with this code by a strange route, so maybe
the code is sub-optimal.
thanks for being patient with me,
Maria
On Sat, Aug 31, 2013 at 12:35 AM, Maria McKinley <mar...@mariakathryn.net>wrote:
Wow, okay, so that is a lot of recursion and generation for me to wrap my
brain around.
I was trying to understand what was going on, and I put the code in a
visualizer, which you can see here:
*http://tinyurl.com/orzrlh2*
So, now I can almost wrap my brain around it.
On Fri, Aug 30, 2013 at 11:18 PM, Maria McKinley <mar...@mariakathryn.net
wrote:
Yay! Thanks. Still working out exactly how to make it work how I want,
but I feel like I'm getting the idea of how this is working now... I will
post code when I have it working properly.
~maria
On Fri, Aug 30, 2013 at 10:42 PM, Mark Harviston <
mark.harvis...@gmail.com> wrote:
on line 94 you have
yield node.items()
this will yield node.items() which is itself a generator.... this is
not what you want to do.
If it was Python 3, you could do:
yield from node.items()
and that would be correct.
Since it's Python 2, you have to do
for i in node.items():
yield i
This will make the recursion work and iterate over the whole list.
--Mark
On Fri, Aug 30, 2013 at 10:04 PM, Maria McKinley <
mar...@mariakathryn.net> wrote:
I'll assume as long as people are answering me, there is enough
interest to keep going...
I was having a problem seeing the representation of my object, but I
did figure that out. I was able to print from the items method, and see
that the code wasn't yielding the correct variable in order see the letter
itself.
Each time you add a word to the trie, it adds each letter of that word
to a node. I have two words (that start with different letters) in my trie,
so when I do the loop, I see the two letters at the top node.
Weirdly, if I stick in letter.next() in the loop:
for letters in mytrie.items():
print 'letters', letters
letters.next()
I do get the 2nd layer, but no more. If I try to do more, I get
StopIteration. My biggest problem is I can't decide if the problem is my
lack of understanding of generators or if this code is just not written
correctly. Surely, it is suppose to be iterating through the entire tree,
and not just the root level? How do I drill down to lower levels? I see how
it is done for adding new words, but can't make something similar work for
looking at unknown words.
I have my code up here:
https://github.com/codedragon/trie
but it isn't a whole lot different from what is in the wikipedia
article. Just has a script for playing around with it and some print
statements stuck in.
thanks again,
Maria
On Thu, Aug 29, 2013 at 9:49 PM, Joseph Wright <jos...@mammalia.net>wrote:
No, it wouldn't help with the iteration, but I thought you were
having a problem seeing the representation of your object. Now I'm trying
to figure this thing out….
It looks like the reason the 'char' only showing the first letter is
because in the add() method, the first letter of the string is what it
assigns to head:
head, tail = s[0], s[1:]
So it uses just one letter at a time per node.
Joseph
On Aug 29, 2013, at 8:55 PM, Maria McKinley <mar...@mariakathryn.net>
wrote:
Not yet, would that solve the problem that it is not iterating? Using
some good old-fashioned print statements, I found out a little bit more.
I added the following print statements:
for char, node in self.root.iteritems():
# node.value is none when not at end of word
if node.value is None:
print 'none'
print 'char',char
print 'node',node
yield node.items()
else:
print 'stuff'
yield node
And this was the output. There are 2 words in the trie, but it only
reports the first letter of each word, and stops:
none
char p
node <trie.Trie instance at 0x10e8d0560>
<generator object items at 0x10e8bc690>
none
char t
node <trie.Trie instance at 0x10e8bab48>
<generator object items at 0x10e8bc5a0>
~maria
On Thu, Aug 29, 2013 at 7:59 PM, Joseph Wright <jos...@mammalia.net>wrote:
Have you tried defining __repr__?
Joseph
On Aug 29, 2013, at 7:56 PM, Maria McKinley <mar...@mariakathryn.net>
wrote:
Thanks Morris. That does answer one question, I can't assume code on
wikipedia is bug-free. Changing it doesn't solve the problem,
unfortunately, but you are right, time to hit the debugger. Thanks everyone.
cheers,
Maria
On Thu, Aug 29, 2013 at 5:46 PM, Morris Bernstein <
mor...@systems-deployment.com> wrote:
I hate to suggest this because I almost never use it, but have you
considered using the pdb debugger and setting a breakpoint?
Meanwhile, your problem is here:
def items(self):
"""Return an iterator over the items of the `Trie`."""
for char, node in self.root.iteritems():
if node.value is None:
yield node.items
node.items is the the Trie.items() method bound to the node object.
I think, taking a quick look at the code, you want to yield
node.items(), function call again. Looks like the same problem.
On Thu, Aug 29, 2013 at 5:17 PM, Maria McKinley <
mar...@mariakathryn.net> wrote:
Doh. Thanks. This does the trick, but it gives me the instance
location. I assumed this is because there is no __str__ method defined, but
when I added a __str__ method it didn't change anything. Probably didn't
implement the __str__ method correctly, but since I didn't even get an
error, not sure this was even the problem. (Pretty sure, for example, that
I shouldn't always be referencing the head node.)
def __str__(self):
return "Node letter is %s" % (self.root[0])
for c in mytrie.items():
print c
...:
<bound method Trie.items of <trie.Trie instance at 0x1010dc710>>
<bound method Trie.items of <trie.Trie instance at 0x1010dca70>>
thanks again,
Maria
On Thu, Aug 29, 2013 at 4:40 PM, Cris Ewing <c...@crisewing.com>wrote:
I expect that the problem here is that you are attempting to
iterate over the method itself, rather than its result. You'd need to call
the method to do that:
for c in mytrie.items():
print c
hth
c
On Aug 29, 2013, at 4:38 PM, Maria McKinley wrote:
Hello,
I hope someone on this list doesn't mind answering what I think
is a quick question. I have been playing around with the python code found
here:
http://en.wikipedia.org/wiki/Trie#A_Python_version
I can't get the iterator to work, and I wonder if I'm not calling
it correctly. I thought once I made my object, and added stuff to it, I
could just do this:
for c in mytrie.items:
print c
but I get this error:
TypeError: 'instancemethod' object is not iterable
What am I doing wrong?
thanks,
Maria
Cris Ewing
--------------------------------------------------
Principal, Cris Ewing, Developer LLC
http://www.crisewing.com
c...@crisewing.com
1.206.724.2112
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/mariamckinley
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/mariamckinley
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/mariamckinley
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/mariamckinley
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/mariamckinley
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/mariamckinley
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/mariamckinley
