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/

Reply via email to