CODEWITHSUNDEEP
pythonlistinsert
user4967499
user4967499

Reputation: 325

Python: insert into list faster than O(N)?

I have a sorted list L and I have a binary search for determining where in the list to insert an element such that the resulting list will still be in order.

However L.insert(index,object) needs O(N) time complexity.

Is there another data structure for L that will serve the same purpose, but allows for a faster insertion?

Upvotes: 20

Views: 9249

Answers (2)

Veedrac
Veedrac

Reputation: 60147

A shout out to sortedcontainers.SortedList. This will keep your list in order automatically, with a fast insert time.

from sortedcontainers import SortedList

mylist = SortedList([1, 2, 4, 5])
mylist.add(3)
mylist
#>>> SortedList([1, 2, 3, 4, 5], load=1000)

SortedList insertions are amortized O(sqrt n), or O(cbrt n) with different choices of parameters, but it scales better than blist, which is O(log n), because the constants are much better. There is a very in-depth look at performance on their website.

Alternatively, you might be wanting a priority queue in which case you can get potentially-faster inserts with the heapq module.

Upvotes: 6

SexmanTaco
SexmanTaco

Reputation: 309

Check out the blist module.

https://pypi.python.org/pypi/blist/

It claims O(log n) insertion.

usage:

x = #list contents
y = blist(x)
y.insert(index, object) #now works in O(log n)

Upvotes: 10

Related Questions