A quick Google for "treap python github" yielded https://github.com/TheAlgorithms/Python/blob/master/data_structures/binary_tree/treap.py .
On Tue, 9 Nov 2021 at 21:49, Dan Stromberg <drsali...@gmail.com> wrote: > > On Tue, Nov 9, 2021 at 9:00 PM Steven D'Aprano <st...@pearwood.info> > wrote: > >> Sorting dicts has been discussed on the Python-Ideas mailing list, it is >> too hard and expensive to justify for the limited use-cases for it. If >> you want to sort a dict, you are best to sort the dict's keys, then >> create a new dict. Or possibly use a dedicated Sorted Mapping type like >> a red-black tree or similar. >> > > There are several implementations of key-order sorted dicts available in > Python, and more than a few of them are well tested. I am the maintainer > of one of them: https://pypi.org/project/treap/ which I ported from > Java. I also did a performance comparison among several of them a few > years back. > > Red-black trees are popular, perhaps especially among Java developers, but > I've never understood why. They aren't the fastest. Among traditional > tree-based key-sorted dicts, treaps are frequently fastest. > > However, SortedDict is not uncommonly faster than treaps - I believe this > is because SortedDict is very good at maximizing locality of reference. > Traditional trees are almost always going to do an entire cache line hit > for every node in large trees, even if those nodes are "next to each other" > when sorted/traversed. SortedDicts put keys that are nearly equal, in > nearly the same part of memory - so multiple values can be retrieved with a > single cache line hit. > > Sorting a dict's keys inside a loop tends to give O(n^2) algorithms, and > sometimes even O(n^2 * logn). This is not good. A traditional tree should > give O(nlogn) algorithms under similar circumstances, and although my gut > is telling me SortedDict is similar the presentation linked below suggests > a different (though still better than sorting in a loop) runtime for > SortedDict. > > It's true that key-sorted dicts are not all that common. Their most > common use is probably for implementing finite caches - evictions can > benefit from ordered keys. However, we already have functools.lru_cache. > > Here's my most recent performance comparison: > https://stromberg.dnsalias.org/~strombrg/sorted-dictionary-comparison/Datastructure%20comparison.pdf > > Here's a PyCon 2016 presentation about SortedContainers, that includes > SortedDict: > https://www.youtube.com/watch?v=7z2Ki44Vs4E > > I think it would make sense to include at least one key-sorted dict in > CPython, and feel that SortedDict would not be a bad way to go. Neither > would treap. > > > _______________________________________________ > Python-Dev mailing list -- python-dev@python.org > To unsubscribe send an email to python-dev-le...@python.org > https://mail.python.org/mailman3/lists/python-dev.python.org/ > Message archived at > https://mail.python.org/archives/list/python-dev@python.org/message/VNK4VPGA4LJH7RMR4LCCACEG2WNDBBFO/ > Code of Conduct: http://python.org/psf/codeofconduct/ > -- OpenPGP: https://hasan.d8u.us/openpgp.asc If you wish to request my time, please do so using *bit.ly/hd1AppointmentRequest <http://bit.ly/hd1AppointmentRequest>*. Si vous voudrais faire connnaisance, allez a *bit.ly/hd1AppointmentRequest <http://bit.ly/hd1AppointmentRequest>*. <https://sks-keyservers.net/pks/lookup?op=get&search=0xFEBAD7FFD041BBA1>Sent from my mobile device Envoye de mon portable
_______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-le...@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/LQHSFACZUBNKIO33TJSVRMI7QBGUDS5D/ Code of Conduct: http://python.org/psf/codeofconduct/
