[Tutor] Python creating trie
Can someone explain me this code to create a trie from words? import collections words = ["bad", "sad", "abyss"] Trie = lambda: collections.defaultdict(Trie) trie = Trie() END = True for i, word in enumerate(words): reduce(dict.__getitem__, word, trie)[END] = i print(trie.values()) I am not able to understand lambda usage and reduce function here. Thanks, ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Python creating trie
anish singh wrote:
> Can someone explain me this code to create a trie
> from words?
>
> import collections
> words = ["bad", "sad", "abyss"]
>
> Trie = lambda: collections.defaultdict(Trie)
> trie = Trie()
> END = True
>
> for i, word in enumerate(words):
> reduce(dict.__getitem__, word, trie)[END] = i
> print(trie.values())
>
>
> I am not able to understand lambda usage and reduce
> function here.
foo = lambda: expr
is just another way to write
def foo():
return expr
In the example the function is
def Trie():
return collections.defauldict(Trie)
This function creates a defaultdict whose values automatically spring into
existence and are defaultdict themselves:
>>> Trie = lambda: collections.defaultdict(Trie)
>>> trie = Trie()
>>> trie["a"]["b"]["c"]
defaultdict( at 0x7f220e21cae8>, {})
>>> trie
defaultdict( at 0x7f220e21cae8>, {'a':
defaultdict( at 0x7f220e21cae8>, {'b':
defaultdict( at 0x7f220e21cae8>, {'c':
defaultdict( at 0x7f220e21cae8>, {})})})})
You can achieve the same with the standard dict by checking explicitly for
the key:
>>> trie = {}
>>> t = trie
>>> for key in ["a", "b", "c"]:
... if key not in t:
... t[key] = {}
... t = t[key]
...
>>> trie
{'a': {'b': {'c': {
Can you rewrite this with the dict.setdefault() method?
The reduce() function is basically a single loop:
>>> def reduce(func, items, initial):
... result = initial
... for item in items:
... result = func(result, item)
... return result
...
>>> reduce(lambda a, b: a + b, [1, 2, 3], 42)
48
Rewritten without reduce:
>>> result = 42
>>> for item in [1, 2, 3]:
... result = result + item
...
>>> result
48
If we rewrite your code following the examples above we get
trie = {}
END = True
for i, word in enumerate(words):
t = trie
for c in word:
t = t.setdefault(c, {})
t[END] = i
print(trie.values())
which you may find a bit easier to follow.
You are not alone.
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Python creating trie
On Sun, Nov 12, 2017 at 02:37:06AM -0800, anish singh wrote: > Can someone explain me this code to create a trie > from words? Not really. What makes this a trie? Where did you get this code from? > import collections > words = ["bad", "sad", "abyss"] > > Trie = lambda: collections.defaultdict(Trie) > trie = Trie() > END = True > > for i, word in enumerate(words): > reduce(dict.__getitem__, word, trie)[END] = i > print(trie.values()) > > > I am not able to understand lambda usage and reduce > function here. The lambda is exactly equivalent to: # Trie = lambda: collections.defaultdict(Trie) def Trie(): return collections.defaultdict(Trie) Does that help? The call to reduce (inside the loop) can be re-written as (untested): # for i, word in enumerate(words): # reduce(dict.__getitem__, word, trie)[END] = i for i, word in enumerate(words): value = trie for item in word: value = value[item] value[END] = i -- Steve ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
[Tutor] (no subject)
我在使用closure 時，遇到了一些問題。 例如一個簡單的例子， def f1(a): def f2(b): return a+b return f2 f1=f1(10) 這時f1會發生衝突 ，這是正常的嗎? ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] (no subject)
On 12/11/17 15:54, 劉權陞 wrote: > 我在使用closure 時，遇到了一些問題。 > 例如一個簡單的例子， > > def f1(a): > def f2(b): > return a+b > return f2 > > f1=f1(10) > > 這時f1會發生衝突 ，這是正常的嗎? Can you tell us what language this is? Or better still post an English translation? That's what most of us speak on this list... -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ http://www.amazon.com/author/alan_gauld Follow my photo-blog on Flickr at: http://www.flickr.com/photos/alangauldphotos ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] (no subject)
Sorry 劉權陞 <01patrick...@gmail.com>, but this is an English-language mailing list. I do not understand what question you are asking. On Sun, Nov 12, 2017 at 11:54:52PM +0800, 劉權陞 wrote: > 我在使用closure 時，遇到了一些問題。 > 例如一個簡單的例子， > > def f1(a): > def f2(b): > return a+b > return f2 > > f1=f1(10) > > 這時f1會發生衝突 ，這是正常的嗎? -- Steve ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
[Tutor] Fwd: Re: (no subject)
Forwarding to the list... From: RRRoy BBBean Organisation: DDDead MMMail To: Alan Gauld , tutor@python.org On Sun, 2017-11-12 at 23:06 +, Alan Gauld via Tutor wrote: > On 12/11/17 15:54, 劉權陞 wrote: ... > Can you tell us what language this is? > Or better still post an English translation? > That's what most of us speak on this list... ... It's Chinese. Google Translate does a decent job with Chinese, much better than Korean at least. > I encountered some problems when using closure. > For example, a simple example, > > def f1 (a): > def f2 (b): > return a + b > return f2 > > f1 = f1 (10) > > This time f1 conflict, is this normal? It appears to be a question about currying in Python? ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
