hi, I wasn't quite clear...
By "full name of the item" I meant the name like "plant" which was
inserted into the Trie in the first place.
So since you have this:
mytrie.add('plant',2)
Trie.items() should be yielding this:
('plant', 2)
(rather than yielding a single char value).
"prefix argument" was a general concept rather than being a specific thing.
If you think of the bottom level Trie that has the value 2 stored for
"plant":
That Trie does not know that the key is "plant", only that the last
character is "t". So it is going to be hard for its items() function to
yield "plant".
Therefore I was suggesting that the items() function could have an
additional argument, which is a prefix to be attached to all the strings
being yielded (where the "plan" part gets passed in).
Hopefully that makes it clearer instead of more muddled, but let me know...
Jonathan
On 09/04/2013 02:41 PM, Maria McKinley wrote:
Yes, that helps, thank you both.
However, I don't understand what you mean by the full name of the item. So,
in the visualizer, we can see that the instance is this:
defaultdict(<class __main__.Trie at 0x1012a10>, {'p': <__main__.Trie
instance at 0x1031290>})
Are you referring to something like this? If so, why is that preferable? I
can see including the node.value, but that doesn't seem to be what you are
talking about.
Also, what is meant by a prefix argument? The only reference I can find to
a prefix argument when I google is to do with emacs lisp, and that doesn't
look applicable.
thanks again,
Maria
On Wed, Sep 4, 2013 at 12:56 AM, Jonathan Mark <[email protected]> wrote:
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/<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 <[email protected]>
**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 <
[email protected]>**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 <
[email protected]
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 <
[email protected]> 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 <
[email protected]> 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<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 <[email protected]
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 <
[email protected]>
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 <[email protected]
wrote:
Have you tried defining __repr__?
Joseph
On Aug 29, 2013, at 7:56 PM, Maria McKinley <
[email protected]>
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 <
[email protected]> 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 <
[email protected]> 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 <[email protected]
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<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
[email protected]
1.206.724.2112
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/**mariamckinley<http://www.linkedin.com/in/mariamckinley>
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/**mariamckinley<http://www.linkedin.com/in/mariamckinley>
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/**mariamckinley<http://www.linkedin.com/in/mariamckinley>
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/**mariamckinley<http://www.linkedin.com/in/mariamckinley>
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/**mariamckinley<http://www.linkedin.com/in/mariamckinley>
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/**mariamckinley<http://www.linkedin.com/in/mariamckinley>
--
Maria Mckinley
Software Developer with Bonus SysAdmin Experience
www.mariakathryn.net
www.linkedin.com/in/**mariamckinley<http://www.linkedin.com/in/mariamckinley>
