Which is fastest dict or list.index() ?

[Tim Peters]

[Kragen Sitaker, to Raymond Hettinger]
> I'm curious how your skiplist version compares with the built-in
> Python dict type on performance; I'd been thinking about building a
> skiplist ordered dictionary extension type myself, but if you've
> already done it, maybe I should just use yours.

One of the better-kept secrets of the StandaloneZODB project

    <http://www.zope.org/Products/StandaloneZODB>

is that it comes with several flavors of C-coded B-Tree mappings and B-Tree
based sets, where B-Tree nodes and bucket leaf nodes are Python objects in
their own right, and you get persistence "for free".  Operations include
range search, intersection, union, difference, and weighted flavors of
intersection and union that compute linear combinations of integer-valued
maps (think of that as a tiny subset of NumPy <wink>).

In practice, they're sluggish compared to Python dicts, and especially for
string-keyed B-Trees (string-keyed Python dicts use all sorts of
implementation tricks for speed).  OTOH, B-Trees support O(log N) insertion
and deletion while preserving sorted order, can spill pieces to disk
gracefully in contexts dicts can't, have good locality of reference during
traversal, and are more memory-efficient than Python dicts, especially for
int-keyed and int-valued B-Trees (for Zope Reasons, those are special-cased
to store C ints directly as C ints rather than as pointers to fat Python int
objects).  One Big Surprise is that len(BTree) can take time proportional to
the number of elements in the tree:  to reduce the load on the persistence
machinery during mutation, B-Tree nodes don't save a count of the number of
key+value pairs reachable from them, and counting them requires traversing
all the leaf buckets.

They're powerful data structures and should be better known.  They should
also be better documented <wink>.  They're fresh on my mind because I'm
working on optimizing the snot out of some common B-Tree operations.

if-you-can-figure-out-how-to-use-'em-you'll-like-'em-ly y'rs  - tim