Sorting order of SortedList?

[remram44]

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

[grantjenks]

It does a length check first. It was designed to match the blist.sortedlist behavior:

In [1]: import sortedcontainers as soco

In [2]: soco.SortedList([1, 2]) < [3]
Out[2]: False

In [3]: [1, 2] < [3]
Out[3]: True

In [4]: import blist

In [5]: blist.sortedlist([1, 2]) < [3]
Out[5]: False

What did you expect the semantics to be?

[remram44]

I don't know, anything else... matching the builtin list would make sense, even so if you can compare SortedLists with regular lists (and why wouldn't you?)

The current behavior can be explained as an algorithm, but doesn't have meaning. What does it mean for the list to be bigger? My view is if the only way to explain is to detail the algorithm, the behavior doesn't make sense. You can make a greater list become smaller by strictly adding elements, so any intuitive inclusion-like meaning doesn't hold...

>>> a = SortedList([1, 2, 3])
>>> a >= [1, 2]
True
>>> a.add(1)
>>> a >= [1, 2]
False

Does blist really use that? They state that Python's unittests pass with it...

[grantjenks]

blist.sortedlist is quite different from blist.blist. You can have a look at the source: https://github.com/DanielStutzbach/blist/blob/master/blist/_sortedlist.py#L567

Also for reference, the CPython source: https://github.com/python/cpython/blob/master/Objects/listobject.c#L2225

I think blist.sortedlist is trying to copy the CPython algorithm. If I understand it correctly then it requires:

1. == list lengths are equal and all items are equal
2. != list lengths differ or at least one item is inequal
3. < the first differing element is less than
4. > the first differing element is greater than
5. <= (3) or (1)
6. >= (4) or (1)

That's odd in its own ways but it has the advantage of defining a total ordering. I think that could be an important feature.

Out of curiosity, why did you need to compare sorted lists?

[grantjenks]

I've pushed an update for sortedcontainers.SortedList at dd06ac0. I think this mimics the "list" comparison behavior in CPython. I implemented a slightly weaker type-check by requiring only that each container inherits from Sequence.

I also believe I found a bug in the blist.sortedlist implementation. Details at DanielStutzbach/blist#77

These changes should also be applied to SortedListWithKey.

[remram44]

Thanks!

[grantjenks]

Out of curiosity, why did you need to compare sorted lists?

[remram44]

I'm actually comparing a sorted list to a regular list. I'm using SortedList as a list that will eventually need to be sorted, that might be out of your use case.

[grantjenks]

Fixed at 9816156.

[grantjenks]

Deployed to PyPI in version 1.4.2