Weeble,<br><br>Try to use the full arguments of insert(i, x), instead of using list slices. Every time you create a slice, Python copies the list into a new memory location with the sliced copy. That's probably a big performance impact there if done recursively.<br>
<br>My 2cp,<br>Xav<br>
<br><br><div class="gmail_quote">On Fri, Mar 19, 2010 at 10:13 AM, Weeble <span dir="ltr"><<a href="mailto:clockworksaint@gmail.com">clockworksaint@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
I am loading a dictionary from a text file and constructing a trie<br>
data structure in memory. However, it takes longer than I'm happy with<br>
- about 12 seconds on my computer. I profiled it, came up with some<br>
clever ideas to cut down on the work (such as by exploiting the fact<br>
that the dictionary is sorted) and was only able to shave a small<br>
fraction of the time off. However, then I tried calling gc.disable()<br>
before loading the trie and it halved the running time! I was<br>
surprised. Is that normal? I thought that the cost of garbage<br>
collection would be in some way proportional to the amount of garbage<br>
created, but I didn't think I was creating any: as far as I can tell<br>
the only objects deallocated during the load are strings, which could<br>
not be participating in cycles.<br>
<br>
I have spent a lot of time in C#, where the standard advice is not to<br>
mess about with the garbage collector because you'll probably just<br>
make things worse. Does that advice apply in Python? Is it a bad idea<br>
to call gc.disable() before loading the trie and then enable it again<br>
afterwards? Does the fact that the garbage collector is taking so much<br>
time indicate I'm doing something particularly bad here? Is there some<br>
way to give the garbage collector a hint that the whole trie is going<br>
to be long-lived and get it promoted straight to generation 2 rather<br>
than scanning it over and over?<br>
<br>
$ python<br>
Python 2.6.4 (r264:75706, Dec 7 2009, 18:43:55)<br>
[GCC 4.4.1] on linux2<br>
Type "help", "copyright", "credits" or "license" for more information.<br>
>>><br>
$ time python -c "import<br>
trie;t=trie.Trie();t.load(open('sowpods.txt'))"<br>
<br>
real 0m12.523s<br>
user 0m12.380s<br>
sys 0m0.140s<br>
$ time python -c "import<br>
trie;t=trie.Trie();t.load(open('sowpods.txt'))"<br>
<br>
real 0m12.592s<br>
user 0m12.480s<br>
sys 0m0.110s<br>
$ time python -c "import gc;gc.disable();import<br>
trie;t=trie.Trie();t.load(open('sowpods.txt'))"<br>
<br>
real 0m6.176s<br>
user 0m5.980s<br>
sys 0m0.190s<br>
$ time python -c "import gc;gc.disable();import<br>
trie;t=trie.Trie();t.load(open('sowpods.txt'))"<br>
<br>
real 0m6.331s<br>
user 0m5.530s<br>
sys 0m0.170s<br>
<br>
<br>
=== trie.py ===<br>
<br>
class Trie(object):<br>
__slots__=("root", "active")<br>
def __init__(self):<br>
self.root=[]<br>
self.active=False<br>
def insert(self, word):<br>
if len(word) == 0:<br>
self.active=True<br>
else:<br>
head = word[0]<br>
for ch, child in reversed(self.root):<br>
if ch == head:<br>
child.insert(word[1:])<br>
return<br>
child = Trie()<br>
self.root.append((head, child))<br>
child.insert(word[1:])<br>
def seek(self, word):<br>
if len(word) == 0:<br>
return self<br>
head = word[0]<br>
for ch, child in self.root:<br>
if ch == head:<br>
return child.seek(word[1:])<br>
return EMPTY_TRIE<br>
def load(self, file):<br>
for line in file:<br>
self.insert(line.strip().lower())<br>
def empty(self):<br>
return (not self.root) and not self.active<br>
def endings(self, prefix=""):<br>
if self.active:<br>
yield prefix<br>
for ch, child in self.root:<br>
for ending in child.endings(prefix+ch):<br>
yield ending<br>
<br>
EMPTY_TRIE = Trie()<br>
<font color="#888888">--<br>
<a href="http://mail.python.org/mailman/listinfo/python-list" target="_blank">http://mail.python.org/mailman/listinfo/python-list</a><br>
</font></blockquote></div><br>