Hello, You may not view this as a bug, but it was a big surprise for me! SortedDict() .keys() used to return sets that could do .intersect() operations. It must now be converted from SortedKeysView (or something?) to a set() and this uses tons of memory and time. The iloc method was also removed. I only got that far before I realized the build I was troubleshooting had a newer version than dev and was broken because of it. Please put a "breaking changes" section into the documentation when making these sorts of things! Or better yet, don't go fixing what isn't broken and also remove functionality :-D

With bintrees being discontinued, and projects using it being urged to migrate to sortedcontainers, I have a feature question. In bintrees, you can look up the "floor" and "ceiling" items given a key that is either too big or too small. For example:

import bintrees
x = bintrees.BinaryTree()
x[10] = 'ten'
assert x.floor_item(15) == (10, 'ten')
assert x.ceiling_item(5) == (10, 'ten')

As far as I can tell, this isn't possible in sortedcontainers. Am I missing anything? If not, is it a planned feature to add? Alternatively, do you have any pointers for a direction toward implementing it?

I would like to be able to have a SortedDict where the sorting is determined by the value being added, or some combination of the key and the value. Basically, the ability for me to provide a key function that takes two arguments.

The following code gives an exception in version 1.5.7:

import sortedcontainers

class Simple(object):
    def __init__(self):
        self.code = 0
        self.time = 0

    def __lt__(self, other):
        return self.time < other.time

o1 = Simple()
o1.time = 3
o1.code = 12
o2 = Simple()
o2.time = 3
o2.code = 18

l = sortedcontainers.SortedList()
l.add(o1)
l.add(o2)
print(l[1] in l) #This prints "False"
l.index(l[1])

ValueError: <__main__.Simple object at 0x7f863f4c4a10> is not in list

The problem seems to be related with the definition of the __lt__ method, as in this case o1 ≮ o2, o2 ≮ o1, but o1 ≠ o2. From the docs, the index() function "Return the smallest k such that L[k] == x and i <= k < j", but that is not true in this case.

(I'm guessing you've thought about this already and decided against, but just wanted to make sure.)

The Python glossary defines sequence as:

An iterable which supports efficient element access using integer indices via the __getitem__() special method and defines a __len__() method that returns the length of the sequence. Some built-in sequence types are list, str, tuple, and bytes. Note that dict also supports __getitem__() and __len__(), but is considered a mapping rather than a sequence because the lookups use arbitrary immutable keys rather than integers.

The collections.abc.Sequence abstract base class defines a much richer interface that goes beyond just __getitem__() and __len__(), adding count(), index(),__contains__(), and __reversed__(). Types that implement this expanded interface can be registered explicitly using register().

SortedDicts have a well-defined ordering, and offer efficient element access using integer indices. So ideally a SortedDict would be able to be used anywhere a Sequence was required.

But because of the overloaded semantics of __getitem__, SortedDict of course has to choose to use it for the Mapping-style implementation rather than the Sequence-style, and thus probably gives up any right to claim that it implements Sequence. Seems like a shame!

(Can't help but wonder if some fancier version of register could allow SortedDict to specify iloc as its __getitem__ implementation when being treated as a Sequence, and wonder whether e.g. Haskell or Clojure would never have a problem like this.)

In any case, we're out of luck right? The Keys-, Values-, and ItemsViews that SortedDict offers are as much Sequence support as SortedDict can provide?

Curious to get your thoughts. And wonder if it's worth adding any takeaways from this to the SortedDict docs. e.g. "Because of limitations in Python, SortedDict cannot implement the Sequence interface even though it took all the right vitamins. Instead you must use a SortedDict's KeysView, ValuesView, or ItemsView anywhere you'd want to use a SortedDict as a Sequence."

On Python 3.4.1:

>>> l = SortedListWithKey(key=lambda x: 1)
>>> class A: pass
... 
>>> l.add(A())
>>> l.add(A())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/muon/kirmvenv2/lib/python3.4/site-packages/sortedcontainers/sortedlistwithkey.py", line 21, in add
    self._list.add(pair)
  File "/home/muon/kirmvenv2/lib/python3.4/site-packages/sortedcontainers/sortedlist.py", line 51, in add
    pos = bisect_right(self._maxes, val)
TypeError: unorderable types: A() < A()

This is because in Python 3 comparing incomparable types dies horribly instead of returning True.

This pull request fixes #158 by prepending existing elements to new ones (to stick with the same ordering as the add() method).

I have run the included tox tests and benchmarks offline and have not seen any noticeable difference in performance after looking at the benchmark plots.

It seems that SortedList doesn't implement support for pickling except by inheriting object.__reduce__. The pickle output therefore contains field that are implementation details of the class.

Consider the result of calling __reduce__() on SortedList([1, 2, 3]):

>>> sortedcontainers.SortedList((1, 3, 2)).__reduce__()
(<function _reconstructor at 0x7f566564c268>, (<class 'sortedcontainers.sortedlist.SortedList'>, <class 'object'>, None), {'_len': 3, '_lists': [[1, 2, 3]], '_maxes': [3], '_index': [], '_load': 1000, '_twice': 2000, '_half': 500, '_offset': 0})

Pickling and unpickling presently works with this implementation, but this approach has two issues:

• it is not optimal wrt space, since it includes unnecessary data. Ideally it would only pickle the sequence of 1, 2, 3, and the fact that it's stored in a SortedList. The __reduce__ protocol is designed with such usage in mind.
• it leaks private fields, which are clearly implementation details, into the peristent format. Even a slight change in the implementation would likely cause unpickling to fail.

An implementation that resolves both issues might look like this, in the case of SortedList:

    def __reduce__(self):
        return type(self), (), None, iter(self)

Here is a small comparison of the two:

class X(sortedcontainers.SortedList):
    def __reduce__(self):
        return type(self), (), None, iter(self)

class Y(sortedcontainers.SortedList):
  pass

>>> x, y = X([1, 2, 3]), Y([1, 2, 3])
>>> x.__reduce__()
(<class '__main__.X'>, (), None, <itertools.chain object at 0x7f5665d444a8>)
>>> pickle.dumps(x, protocol=pickle.HIGHEST_PROTOCOL)
b'\x80\x04\x95\x1d\x00\x00\x00\x00\x00\x00\x00\x8c\x08__main__\x94\x8c\x01X\x94\x93\x94)R\x94(K\x01K\x02K\x03e.'
>>> pickle.loads(_)
X([1, 2, 3], load=1000)
>>> pickle.dumps(y, protocol=pickle.HIGHEST_PROTOCOL)
b'\x80\x04\x95\x80\x00\x00\x00\x00\x00\x00\x00\x8c\x08__main__\x94\x8c\x01Y\x94\x93\x94)\x81\x94}\x94(\x8c\x04_len\x94K\x03\x8c\x06_lists\x94]\x94]\x94(K\x01K\x02K\x03ea\x8c\x06_maxes\x94]\x94K\x03a\x8c\x06_index\x94]\x94\x8c\x05_load\x94M\xe8\x03\x8c\x06_twice\x94M\xd0\x07\x8c\x05_half\x94M\xf4\x01\x8c\x07_offset\x94K\x00ub.'
>>> pickle.loads(_)
Y([1, 2, 3], load=1000)

SortedList objects don't compare the same way lists do, or in any way that I could make sense of.

>>> SortedList([1, 2]) < [3]
False
>>> SortedList([1, 2]) < [0]
False
>>> SortedList([1, 2]) < [0, 4]
False
>>> SortedList([1, 2]) > [0, 4]
False

Hi Grant,

I'm the author of bidict. I just came across SortedContainers and it looks excellent. Kudos on the great work! I'm delighted to have found another high-quality Python collections library, and look forward to studying it further.

In the meantime, thanks to finding this project, I've already made a tiny change to the development version of bidict that I'm excited about: now users can make a SortedBidict type (backed by your SortedDict) in just a few lines of code:

>>> import bidict, sortedcontainers
>>>
>>> class sortedbidict(bidict.bidict):
...     _dict_class = sortedcontainers.SortedDict
>>>
>>> b = sortedbidict({'Tokyo': 'Japan', 'Cairo': 'Egypt', 'Lima': 'Peru'})
>>>
>>> list(b.items())  # b stays sorted by its keys
[('Cairo', 'Egypt'), ('Lima', 'Peru'), ('Tokyo', 'Japan')]
>>>
>>> list(b.inv.items())  # b.inv stays sorted by *its* keys (b's values!)
[('Egypt', 'Cairo'), ('Japan', 'Tokyo'), ('Peru', 'Lima')]
>>>
>>> b.index('Lima')  # passes through to SortedDict's implementation
1
>>> b.iloc[-1]
'Tokyo'
>>> b.peekitem(index=-1)
('Tokyo', 'Japan')
>>> b.inv.peekitem(index=-1)
('Peru', 'Lima')
>>> b.popitem(last=False)
('Cairo', 'Egypt')
>>> list(b.items())
[('Lima', 'Peru'), ('Tokyo', 'Japan')]
>>> list(b.inv.items())
[('Japan', 'Tokyo'), ('Peru', 'Lima')]

Documented more here.

Always interested to hear more ideas for fruitful interop and in collaboration in general. In case of interest!

Thanks for reading and best wishes.

Josh

P.S. Hope you don't mind my using your tracker for this. Please of course feel free to close / migrate to anywhere else you prefer. bidict has a (mostly inactive) channel at https://gitter.im/jab/bidict in case you'd ever like to chat there.

#This is running in Pycharm and Conda

from sortedcontainers import SortedList, SortedSet, SortedDict import timeit import random

def test_speed(data,sorted_data): for val in data: #Accessing this is not an issue sorted_data.add(val)

data = [] numpts = 10 ** 5 for i in range(numpts): data.append(random.random()) print(f'Num of pts:{len(data)}')

sorted_data = SortedList() n_runs=10 result = timeit.timeit(stmt='test_speed(data,sorted_data)', globals=globals(), number=n_runs) print(f'Speed is {1000*result/n_runs:0.0f}ms')

Motivation

• Other programming languages support high-level APIs like

  • Get next smaller value (or item)
  • Get floor value (or item)
  • Get ceil value (or item)
  • Get next larger value (or item) In Tree data structure.

• We can achieve this by using bisect method + index range check, but providing higher-level API would help users to avoid writing wrapper code every time.

API Definition

SortedList

• def next_smaller(self, value: object) -> Optional[object]
• def floor (self, value: object) -> Optional[object]
• def ceil (self, value: object) -> Optional[object]
• def next_greater(self, value: object) -> Optional[object]

SortedSet

• def next_smaller(self, value: Hashable) -> Optional[object]
• def floor (self, value: Hashable) -> Optional[object]
• def ceil (self, value: Hashable) -> Optional[object]
• def next_greater(self, value: Hashable) -> Optional[object]

SortedDict

• def next_smaller_item(self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]
• def floor_item (self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]
• def ceil_item (self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]
• def next_greater_item(self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]

Prototype Code (Implementation / Tests)

• https://github.com/grantjenks/python-sortedcontainers/pull/206

P.S

• If this idea sounds good to you, I'd love to discuss API design (including naming), testing strategy, etc.
• Thank you so much for your attention and participation.

Hi, thanks for your work :)

would it be possible to add a new function to the SortedDict (and therefore also SortedList) which sets a key a new value and returns the index position in one go? Eg.: index = sorteddict.setitem_returnindex(key,value)

Usecase: I want to add a new key,value to the SortedDict and I want to know at which total index this key was sorted in. Since performance is important, I assume that such a combined method would be much faster than sorting it in and then again search the key to get the index.

I assume that when sorting the new key into the SortedDict, we already search for the correct index to insert it. So we should be able to simply return this index and then there is no need to search for it twice. I already read the source code and tried to add it myself, but: 1) sortedcontainers is still frequently updated, I don't want to overwrite eg. the init of SortedDict to make it use a custom SortedList, because this might mess with future updates. 2) I did not fully understand the internal structure with lists and maxes yet :D And it seems bisect "insort" also does not return the index, which makes it more difficult =/ (I really don't understand why "insort" does not return the index, it would be so easy -.- )

Hi,

I have some code where unpickling SortedLists and SortedSets takes a significant amount of the runtime of my program (I have a lot of them!)

The problem is, I think, that as __reduce__ just says that set and key should be passed to init, then the iterable values then get fed into self._update one at a time.

Would it be possible to speed things up, as the iterable is already known to be sorted? I wasn't sure of the best way to do this, one option would be to add a constructor method issorted, but then that might get used by other people (and maybe incorrectly), and you might not want that?

Warehouse now uses the project_urls provided to display links in the sidebar on this screen, as well as including them in API responses to help automation tool find the source code for Requests.

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