Insert a custom object in a sorted list

Question

I implemented an object with a numerical attribute. I want to keep a list of those objects sorted according to that attribute, without need to run a sort method at each insertion. I took a look to bisect module, but I do not know if I can use it also with an object. What is the best way to do that?

Answer 1

You can do this for your custom object if you implement the __lt__ method, because this is what bisect will use to compare your object.

>>> class Foo(object):
...     def __init__(self, val):
...         self.prop = val # The value to compare
...     def __lt__(self, other):
...         return self.prop < other.prop
...     def __repr__(self):
...         return 'Foo({})'.format(self.prop)
...
>>> sorted_foos = sorted([Foo(7), Foo(1), Foo(3), Foo(9)])
>>> sorted_foos
[Foo(1), Foo(3), Foo(7), Foo(9)]
>>> bisect.insort_left(sorted_foos, Foo(2))
>>> sorted_foos
[Foo(1), Foo(2), Foo(3), Foo(7), Foo(9)]

Answer 2

You may provide a custom implementation of list that override the insert method that make a binary insertion. hose the time to insert an element come from O(1) to O(log2(n)) where n is the number of element in the list.

You may also use an already implemented implementation such as sorted containers [http://www.grantjenks.com/docs/sortedcontainers/].

Anyway, whatever solution you use, you MUST implement comparators methods on your objects ( greater than (__gt__) and lesser than (__lt__) ) that use this numerical attribute to define an order on your objects. Without order, there is no sorting possible.

Here an example :

from sortedcontainers import SortedList

class OrderedObject():

    def __init__(self, id, value):
        self.id = id
        self.value = value

    def __gt__(self, other):
        if not isinstance(other,OrderedObject):
            raise Exception("OrderedObject are only comparable to OrderedObject, not to {0}".format(type(other)))
        else:
            return self.value.__gt__(other.value)

    def __lt__(self, other):
        if not isinstance(other,OrderedObject):
            raise Exception("OrderedObject are only comparable to OrderedObject, not to {0}".format(type(other)))
        else:
            return self.value.__lt__(other.value)

    def __repr__(self):
        return "<OrderedObject({0}, {1})>".format(self.id, self.value)

if __name__ == "__main__":
    a = OrderedObject('foo', 1)
    b = OrderedObject('bar', 2)
    c = OrderedObject('-*-', 3)

    mylist = [b,c,a]
    print(mylist)
    mylist.sort()
    print(mylist)

    mylist = SortedList()
    mylist.add(b)
    mylist.add(c)
    mylist.add(a)
    print(mylist)

This give the following results :

[<OrderedObject(bar, 2)>, <OrderedObject(-*-, 3)>, <OrderedObject(foo, 1)>]
[<OrderedObject(foo, 1)>, <OrderedObject(bar, 2)>, <OrderedObject(-*-, 3)>]
SortedList([<OrderedObject(foo, 1)>, <OrderedObject(bar, 2)>, <OrderedObject(-*-, 3)>])

NB : I'm not affiliated to sorted container library in any way

Answer 3

bisect doesn't support keys; read this: http://bugs.python.org/issue4356 and they don't plan to support that either for performance reasons. But I think it should work if you use __gt__, __lt__ etc.

Answer 4

You can decrease amount of sorts by:

• Introducing special variable that will show you if your list is sorted AND
• Sort list when you need to get data from it if your special variable tells you that your list has been modified.

Modification for your special variable should be performed on inserting new data.