On Sat, 14 Mar 2020 20:35:08 -0000 1njecti...@gmail.com wrote: > In other languages, there are built-in data structures with binary > search tree semantics, as an example, std::map in C++.
> By binary search tree semantics we mean the following: > * 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 illustrate the need, can the following program be written elegantly > and efficiently with built-in Python data structures? > Imagine that you are a fund manager at a bank. Bank accounts are added > to your fund very frequently. A bank account has an ID and a value. A > smaller ID means that the bank account was created earlier than one > with a larger ID. Each time that an account is added to your fund, you > would like to know the ID number of the 1000th oldest account, for > your records. Have you considered Python's heapq module? It fails to meet your second semantic (iterating in linear time), but should work pretty well for your stated use case (finding the 1000th oldest element in a heap). 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? Dan -- “Atoms are not things.” – Werner Heisenberg Dan Sommers, http://www.tombstonezero.net/dan _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/GS6CKCRUHZGW7PAZVK6QWPETYZB7DUGE/ Code of Conduct: http://python.org/psf/codeofconduct/
