On Sun, Mar 15, 2020 at 12:28 PM Alex Hall <alex.mojaki@gmail.com> wrote:
How about http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html ?
For my part, I didn't look for that, as I was having fun playing around with the idea. But yes, that looks like it would fit the bill. And at a glance, they were smarter than me :-) -- no need to keep the underlying dict in sorted order, just find the key in the list, then use the regular O(1) dict access. But since I'm having fun, enclosed is an (incomplete) implementation of a a SortedMap. This one keeps a list of keys and values in sorted order, then can access things in O(logN). Insert is O(N), as it's using a regular old list internally. But that is all in C, and not too bad in practice. With the OP's example, it's slower than the basic dict method for creating, but much faster for finding items. (not formally timed) But back the python_ideas topic: It might be good to have a set of real, tree-based data structures -- they are the best way to go for some use cases, and are non-trivial to implement well. (and yes, starting out at a third party package, maybe one that's already out there, would be the way to go) -CHB -- Christopher Barker, PhD Python Language Consulting - Teaching - Scientific Software Development - Desktop GUI and Web Development - wxPython, numpy, scipy, Cython