Builtin classes list, set, dict reimplemented via B-trees

[barnesc]

Nifty, Tim Peters responded to my e-mail. I must've said something
interesting. Cool, a PyCelebrity!

[barnesc at engr.orst.edu]

...
I've gotten bored and went back to one of my other projects:
reimplementing the Python builtin classes list(), set(), dict(),
and frozenset() with balanced trees (specifically, counted B-trees
stored in memory).

In short, this allows list lookup, insertion, deletion in O(log(N))
time. It allows the set and dictionary types to be maintained in
order, and insert/lookup/remove operations here take O(log(N)) time
as well. Getting the k least or k greatest elements takes
O(log(N)+k) time.

Note that BTrees for Python have been part of ZODB for many years:

Section 5.3, _BTrees Package_
http://www.zope.org/Wikis/ZODB/FrontPage/guide/node6.html

If you install ZODB, you can use its BTrees as in-memory data
structures without using any of the rest of ZODB. If you want to
persist them, great, that's what ZODB is for.

Note that ZODB's are really B+ trees, so iterating over the smallest k
takes O(k) time. As an extension to Python's mapping protocol, the
keys/values/items/iterkeys/itervalues/iteritems methods also accept
optional lower and upper bounds on the keys to return.

A gotcha: For scalability in multiprocess database apps, ZODB's
BTrees do not store their size. As a result, len(a_ZODB_BTree) takes
time linear in the number of elements.

Thanks for the link!

That's a different question entirely ;-)


It's probably not a way to get rich quick.

Well, the Tim Peters PyCelebrity experience was fun, but not quite
as exhilarating as advertised. I'm not sure what to say. Did I get
my money's worth? There were no <wink>s, even a little sarcasm. I
guess, overall, yeah it was cool, it was worthwhile, it was fun, man,
it was a life-changing moment!

Thanks for tuning in to PyCelebrity weekly. We're always glad to
be part of your inexplicable existence in The Hostile And Indifferent
Universe (Incorporated). Contributions come from hackers like you!

Reporting live from Python-list, this is...Connelly Barnes.

Next up: Startling photographs show that Guido van Rossum was
KIDNAPPED BY ALIENS in 1990! Rumor has it that his
superhuman language design skills are really due to
neuroimplanted nanotube processors!