CODEWITHSUNDEEP
pythonlistsorting
ilya n.
ilya n.

Reputation: 18826

Does python have a sorted list?

By which I mean a structure with:

I also had a related question about performance of list(...).insert(...) which is now here.

Upvotes: 174

Views: 143945

Answers (10)

Yu Yan
Yu Yan

Reputation: 23

Yes, you can use

from sortedcontainers import SortedList

ref: https://grantjenks.com/docs/sortedcontainers/sortedlist.html

Upvotes: 0

Slass33
Slass33

Reputation: 66

Use the standard library bisect module or the third-party sortedcontainers package. Alternately, the heapq module solves the problem by implementing a heap queue.

Upvotes: 0

Manish Jain
Manish Jain

Reputation: 79

An AVL Tree coupled with in-order traversal will solve this problem in the required time complexity.

Upvotes: 1

Basj
Basj

Reputation: 46303

Interesting case: if your list L is already sorted (for example because you appended them in a sorted order), you can benefit from a fast lookup in O(log n) with a standard Python list with this method:

import bisect
def in_sorted_list(elem, sorted_list):
    i = bisect.bisect_left(sorted_list, elem)
    return i != len(sorted_list) and sorted_list[i] == elem
L = ["aaa", "bcd", "hello", "world", "zzz"]
print(in_sorted_list("hellu", L))       # False

More details in this answer.

Upvotes: -2

Martin v. Löwis
Martin v. Löwis

Reputation: 127527

The standard Python list is not sorted in any form. The standard heapq module can be used to append in O(log n) to an existing list and remove the smallest one in O(log n), but isn't a sorted list in your definition.

There are various implementations of balanced trees for Python that meet your requirements, e.g. rbtree, RBTree, or pyavl.

Upvotes: 69

Dave31415
Dave31415

Reputation: 2956

import bisect

class sortedlist(list):
    '''just a list but with an insort (insert into sorted position)'''
    def insort(self, x):
        bisect.insort(self, x)

Upvotes: 5

GrantJ
GrantJ

Reputation: 8729

Is there a particular reason for your big-O requirements? Or do you just want it to be fast? The sortedcontainers module is pure-Python and fast (as in fast-as-C implementations like blist and rbtree).

The performance comparison shows it benchmarks faster or on par with blist's sorted list type. Note also that rbtree, RBTree, and PyAVL provide sorted dict and set types but don't have a sorted list type.

If performance is a requirement, always remember to benchmark. A module that substantiates the claim of being fast with Big-O notation should be suspect until it also shows benchmark comparisons.

Disclaimer: I am the author of the Python sortedcontainers module.

Installation:

pip install sortedcontainers

Usage:

>>> from sortedcontainers import SortedList
>>> l = SortedList()
>>> l.update([0, 4, 1, 3, 2])
>>> l.index(3)
3
>>> l.add(5)
>>> l[-1]
5

Upvotes: 124

Fan
Fan

Reputation: 97

It may not be hard to implement your own sortlist on Python. Below is a proof of concept:

import bisect

class sortlist:
    def __init__(self, list):
        self.list = list
        self.sort()
    def sort(self):
        l = []
        for i in range(len(self.list)):
            bisect.insort(l, self.list[i])
        self.list = l
        self.len = i
    def insert(self, value):
        bisect.insort(self.list, value)
        self.len += 1
    def show(self):
        print self.list
    def search(self,value):
        left = bisect.bisect_left(self.list, value)
        if abs(self.list[min([left,self.len-1])] - value) >= abs(self.list[left-1] - value):
            return self.list[left-1]
        else:
            return self.list[left]

list = [101, 3, 10, 14, 23, 86, 44, 45, 45, 50, 66, 95, 17, 77, 79, 84, 85, 91, 73]
slist = sortlist(list)
slist.show()
slist.insert(99)
slist.show()
print slist.search(100000000)
print slist.search(0)
print slist.search(56.7)

========= Results ============

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 101]

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 99, 101]

101

3

50

Upvotes: 0

ジョージ
ジョージ

Reputation: 1576

Though I have still never checked the "big O" speeds of basic Python list operations, the bisect standard module is probably also worth mentioning in this context: 

import bisect
L = [0, 100]

bisect.insort(L, 50)
bisect.insort(L, 20)
bisect.insort(L, 21)

print L
## [0, 20, 21, 50, 100]

i = bisect.bisect(L, 20)
print L[i-1], L[i]
## 20, 21

PS. Ah, sorry, bisect is mentioned in the referenced question. Still, I think it won't be much harm if this information will be here )

PPS. And CPython lists are actually arrays (not, say, skiplists or etc) . Well, I guess they have to be something simple, but as for me, the name is a little bit misleading.

So, if I am not mistaken, the bisect/list speeds would probably be:

  • for a push(): O(n) for the worst case ;
  • for a search: if we consider the speed of array indexing to be O(1), search should be an O(log(n)) operation ;
  • for the list creation: O(n) should be the speed of the list copying, otherwise it's O(1) for the same list )

Upd. Following a discussion in the comments, let me link here these SO questions: How is Python's List Implemented and What is the runtime complexity of python list functions

Upvotes: 39

Stephan202
Stephan202

Reputation: 61579

Though it does not (yet) provide a custom search function, the heapq module may suit your needs. It implements a heap queue using a regular list. You'd have to write your own efficient membership test that makes use of the queue's internal structure (that can be done in O(log n), I'd say...). There is one downside: extracting a sorted list has complexity O(n log n).

Upvotes: 5

Related Questions