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.
pip install sortedcontainers
>>> from sortedcontainers import SortedList >>> l = SortedList() >>> l.update([0, 4, 1, 3, 2]) >>> l.index(3) 3 >>> l.add(5) >>> l[-1] 5
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.
Though I have still never checked the "big O" speeds of basic Python list operations,
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:
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
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).
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]