In Koble the auto-completion of thing-names used for wiki-editting, instant-search and adding relations is getting slower and slower, mainly because I do:
result=[] things=listAllThings() for t in things: if t.startswith(key): res.append(t) for t in things: if key in t: res.append(t)
Going through the list twice makes sure I get all things that match well first (i.e. the start with the string I complete for), and then things matching less well later (they only contain the string).
Of course the world has made up a far better data-structure for indexing prefix’es of string, namely the trie, or prefix tree. James Tauber had already implemented one in python, and kindly made it available. His version didn’t do everything I needed, so I added a few methods. Here is my updated version:
http://gromgull.net/2009/11/trie.py
Enjoy!