python-sortedcontainers icon indicating copy to clipboard operation
python-sortedcontainers copied to clipboard

Published 20 hours ago • verified publisher icon grantjenks

add SortedArray

Open bsamedi opened this issue 3 years ago • 2 comments
trafficstars

Support for a sorted container based off the standard library array.array class.

Enables compact storage of numerical values saving times fold in memory required.

Time performance is en par with the List based implementation below 1M size, and marginally better at 10M and 100M size, as tested on M1 Max 64GB RAM

SortedArray_load-add SortedArray_load-bisect SortedArray_load-contains SortedArray_load-count SortedArray_load-delitem SortedArray_load-getitem SortedArray_load-index SortedArray_load-init SortedArray_load-intervals SortedArray_load-iter SortedArray_load-multiset SortedArray_load-neighbor SortedArray_load-pop SortedArray_load-priorityqueue SortedArray_load-ranking SortedArray_load-remove SortedArray_load-update_large SortedArray_load-update_small

bsamedi avatar Dec 24 '21 05:12 bsamedi

It’s reasonable except for the lack of array.array.sort. Can you get support for that upstream? I haven’t searched bugs.python.org but it’s worth researching.

grantjenks avatar Dec 24 '21 05:12 grantjenks

It’s reasonable except for the lack of array.array.sort. Can you get support for that upstream? I haven’t searched bugs.python.org but it’s worth researching.

Looks more like PEP rather than a bug to me. I found none. Is it a good one to request?

Before the array.sort() becomes a thing, we can try RADIX sort in pure Python, O(N) memory, O(N) time. It even works for floats What do you think?

bsamedi avatar Dec 24 '21 06:12 bsamedi