Prev: Scope (?) question
Next: Updating a module level shared dictionary
From: Dimitris Leventeas on 15 Jun 2010 20:02
Hi!

I am trying to understand Python's method of passing arguments, the references
to objects etc. I fail to grasp why in populate_trie I have to make a deepcopy
of trie locally instead of just referencing to it.

If it makes any difference, I use Python 3.


from copy import deepcopy

def access_trie(d, sequence, position=None):
"""
Access the dictionary which is referred by applying consequently each
term of the sequence. In a more python terms, if sequence is 'key',
access: d['k']['e']['y'] Assume that the dictionary is at the
`position` of a list, if `position` is an argument.

>>> a = {'k': [0, {'a': [0, {'l': [0, {'o': [1, {}]}]}]}]}
>>> access_trie(a, 'kal', 1)
{'o': [1, {}]}
>>> access_trie(a, 'kalo', 1)
{}
>>> a = {'d': {'i': {'m': {'i': {'t': {'r': {'i': {'s': 1}}}}}}}}
>>> access_trie(a, 'dimitr')
{'i': {'s': 1}}
>>> access_trie(a, '')
{'d': {'i': {'m': {'i': {'t': {'r': {'i': {'s': 1}}}}}}}}
>>> access_trie(a, 'dimitris')
1
>>> b = access_trie(a, 'dimitr')
>>> b['o'] = {'s': 1}
>>> a
{'d': {'i': {'m': {'i': {'t': {'r': {'i': {'s': 1}, 'o': {'s': 1}}}}}}}}

"""

for c in sequence:
d = d[c]
if position is not None:
d = d[position]

return d


def populate_trie(trie, sequence, position=None):
"""
Populate a trie.

Assume that the counter is always at `position` 0 while the `position`
of the dictionary is the last one.

>>> trie = {}
>>> populate_trie(trie, 'taspython')
{'t': {'a': {'s': {'p': {'y': {'t': {'h': {'o': {'n': {}}}}}}}}}}
>>> trie = {}
>>> populate_trie(trie, 'kalo', 1)
{'k': [1, {'a': [1, {'l': [1, {'o': [1, {}]}]}]}]}
>>> trie = {}
>>> populate_trie(trie, 'heh', 2)
{'h': [1, 0, {'e': [1, 0, {'h': [1, 0, {}]}]}]}
>>> trie = {}
>>> trie = populate_trie(trie, 'heh', 1)
>>> populate_trie(trie, 'hah', 1)
{'h': [2, {'a': [1, {'h': [1, {}]}], 'e': [1, {'h': [1, {}]}]}]}


"""

if (position is not None) and (position >= 1):
embedded_obj = [0] * position
embedded_obj.append({})
else:
embedded_obj = {}

d = deepcopy(trie)
d2 = d
for i, character in enumerate(sequence):
d2 = access_trie(d, sequence[:i], position)
if character not in d2:
if position is None:
d2[character] = deepcopy(embedded_obj)
else:
d2[character] = d2.get(character, deepcopy(embedded_obj))
d2[character][0] += 1
elif position is not None:
d2[character][0] += 1

return d



Best regargs,
Dimitris Leventeas
--
Dimitris Leventeas
http://students.ceid.upatras.gr/~lebenteas/
From: Thomas Jollans on 16 Jun 2010 04:04
On 06/16/2010 02:02 AM, Dimitris Leventeas wrote:
> from copy import deepcopy
>
> def access_trie(d, sequence, position=None):
> [snip]
>

To see what you're on about, I removed the deepcopies from your code and
ran your examples with doctest:

% python3.1 -m doctest trie.py
**********************************************************************
File "trie.py", line 45, in trie.populate_trie
Failed example:
populate_trie(trie, 'taspython')
Expected:
{'t': {'a': {'s': {'p': {'y': {'t': {'h': {'o': {'n': {}}}}}}}}}}
Got:
{'t': {'a': {...}, 'h': {...}, 'o': {...}, 'n': {...}, 'p': {...},
's': {...}, 't': {...}, 'y': {...}}}
**********************************************************************
File "trie.py", line 48, in trie.populate_trie
Failed example:
populate_trie(trie, 'kalo', 1)
Expected:
{'k': [1, {'a': [1, {'l': [1, {'o': [1, {}]}]}]}]}
Got:
{'k': [4, {'a': [...], 'l': [...], 'o': [...]}]}
**********************************************************************
File "trie.py", line 51, in trie.populate_trie
Failed example:
populate_trie(trie, 'heh', 2)
Expected:
{'h': [1, 0, {'e': [1, 0, {'h': [1, 0, {}]}]}]}
Got:
{'h': [3, 0, {'h': [...], 'e': [...]}]}
**********************************************************************
File "trie.py", line 55, in trie.populate_trie
Failed example:
populate_trie(trie, 'hah', 1)
Expected:
{'h': [2, {'a': [1, {'h': [1, {}]}], 'e': [1, {'h': [1, {}]}]}]}
Got:
{'h': [4, {'a': [2, {'h': [...]}], 'h': [...], 'e': [...]}]}
**********************************************************************
1 items had failures:
4 of 9 in trie.populate_trie
***Test Failed*** 4 failures.

As you can see, all the letters except the first one are inserted at
level II, not in a nested level.

> if position is None:
> d2[character] = deepcopy(embedded_obj)
> else:
> d2[character] = d2.get(character, deepcopy(embedded_obj))
> d2[character][0] += 1

If you don't copy embedded_obj here, you just insert a reference to the
same object into the tree at different points. so you insert
embedded_obj, iterate one level further into the structure, and insert
the exact same embedded_obj, into itself! That's what the [...] and
{...} in the output above mean - it's returning cyclic structures.
Another example of a cyclic structure:

>>> L = list(range(5))
>>> L.append(L)
>>> L
[0, 1, 2, 3, 4, [...]]
>>>

Obviously, it goes on for ever and ever, so Python can't print it
properly, without the ...

--
Thomas
From: Dimitris Leventeas on 16 Jun 2010 05:08
Thanks Thomas!

To reply the subject's question: I don't have to. The following works
perfectly.


def populate_trie(trie, sequence, position=None):
"""
Populate a trie.

Assume that the counter is always at `position` 0 while the `position`
of the dictionary is the last one.

>>> trie = {}
>>> populate_trie(trie, 'taspython')
{'t': {'a': {'s': {'p': {'y': {'t': {'h': {'o': {'n': {}}}}}}}}}}
>>> trie = {}
>>> populate_trie(trie, 'kalo', 1)
{'k': [1, {'a': [1, {'l': [1, {'o': [1, {}]}]}]}]}
>>> trie = {}
>>> populate_trie(trie, 'heh', 2)
{'h': [1, 0, {'e': [1, 0, {'h': [1, 0, {}]}]}]}
>>> trie = {}
>>> trie = populate_trie(trie, 'heh', 1)
>>> populate_trie(trie, 'hah', 1)
{'h': [2, {'a': [1, {'h': [1, {}]}], 'e': [1, {'h': [1, {}]}]}]}


"""

if (position is not None) and (position >= 1):
embedded_obj = [0] * position
embedded_obj.append({})
else:
embedded_obj = {}

d2 = trie
for i, character in enumerate(sequence):
d2 = access_trie(trie, sequence[:i], position)
if character not in d2:
if position is None:
d2[character] = deepcopy(embedded_obj)
else:
d2[character] = d2.get(character, deepcopy(embedded_obj))
d2[character][0] += 1
elif position is not None:
d2[character][0] += 1

return trie


Best regards,
Dimitris Leventeas
--
Dimitris Leventeas
http://students.ceid.upatras.gr/~lebenteas/
 | 
Pages: 1
Prev: Scope (?) question
Next: Updating a module level shared dictionary