> In other languages, there are built-in data structures with binary
> search tree semantics, as an example, std::map in C++.
not being a C++ guy, I had no idea that std::map was a tree -- I always figured it was a hashtable, but you learn something new every day.
As far as I know, there is no built in data structure that is ready to go, but some tools are there.
Before I go further, the obvious think to do is see if there's a third party package that does what you want -- there are a lot of hits for "binary tree" on PyPi -- no idea if any of them are robust, mature, maintained, and meet your needs, but do go look.
> * We can insert elements into the structure in time faster than O(n),
> i.e. O(logn) for std::map
> * We can iterate over all of the elements of the structure in sorted
> order in linear time, i.e. O(n) for std::map
> Is there currently any data structure in Python with binary search
> tree semantics?
To be pedantic, I don't think you are looking for binary search semantics, but rather, binary tree performance :-)
This version is taking advantage of the fact that dicts now preserve order. So what it does is keep the keys in order, but inserting items in the right place.
And it used the stdlib bisect module to work with the keys efficiently.
In theory, it should have:
O(logN) insert
O(logN) retrieval on the nth key, value, item
O(1) retrieval of a particular key
However
- The constant for insertion are huge: it has to rebuild the dict on every insertion
- The constant for retrieval by order is kinda big -- it has to make a list out of the keys.
And this implementation has all sorts of possible optimizations that I haven't bother with yet. A big one is that it might make sense to keep the sorted list of the keys around, as you can't use bisect() on the dict.keys() iterator.
Which makes me think that we should dump the dict altogether, and simply use two lists: on of keys, and one of values. keep the keys list sorted, and you can use bisect to insert and retrieve and there you go.
I've tried this code on your example, and it appears to work, but it is painfully slow. However, your code mingles creation and retrieval, and generating random numbers, etc, so it's a bit hard to tease out where the performance hit is.
I would say that you want to think about what performance you care about: if you are going to be adding things much less often that retrieving them, and you want good "get this specific key" performance, then this approach (optimized) might be OK.
Note that this code has a few tests in it -- if you run it with pytest:
pytest sorted_dict.py
the tests will run. They are not the least bit comprehensive, but enough to play around with optimizations and no you haven't broken anything too badly.
Hmm -- maybe I'll go try a version simply with lists now...
Also, if you're talking about bank accounts, ISTM that the persistent,
secure storage mechanisms would swamp the time for finding the 1000th
oldest account. Or are all of your account data only stored in memory?
Yes, this example would probably be in a database, but I'm going to assume it's a motivating example, and the general case of wanting a data structure that's efficient for this kind of data is reasonable.
-CHB
--