On Mon, 10 Mar 2014 19:34:48 +0200, Marko Rauhamaa wrote: >> With a high level language like Python, using the provided hash table >> will almost always cream any hand-built tree, no matter how >> advantageous the data is to the tree. > > The main thing is there are use cases where order is essential. That's > why I have had to implement the AVL tree in Python myself.
from collections import OrderedDict gives you a fast, ordered mapping. In this case, the order is that of insertion order. If you want sort order instead, for "small" amounts of data, say below a million or ten million items, you're likely to have acceptable if not superior results by just sorting them items when and as needed. Otherwise, I expect that following the basic technique of OrderedDict, and building your data structure from a dict and an associated list, keeping the two in sync, will be faster than a pure Python implementation of an AVL tree. But of course only testing it will make that clear. http://code.activestate.com/recipes/576693-ordered-dictionary-for-py24/ Modifying the above recipe to keep items in something other than insertion order is left as an exercise. -- Steven D'Aprano http://import-that.dreamwidth.org/ -- https://mail.python.org/mailman/listinfo/python-list
