steve+comp.lang.python at pearwood.info
Fri Mar 14 00:57:47 CET 2014
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
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.
Modifying the above recipe to keep items in something other than
insertion order is left as an exercise.
More information about the Python-list