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

Question

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?

Binary search tree? Looks like Python doesn't have one built in, but there's probably a package somewhere for one. — Colonel Thirty Two
– Colonel Thirty Two, Commented Jun 5, 2015 at 2:02
@HaiVu From the documentation of bisect.insort(): "Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step." — Tobias Uhmann
– Tobias Uhmann, Commented Sep 7, 2021 at 21:12

SexmanTaco · Accepted Answer · 2015-06-05 03:09:44Z

10

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)

edited Jun 5, 2015 at 3:09

answered Jun 5, 2015 at 2:04

SexmanTaco

3092 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

jnnnnn Over a year ago

This library is also very efficient for inserting/deleting at random locations in unsorted lists (where the order matters).

Veedrac · Accepted Answer · 2018-02-28 09:49:52Z

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.

The O(log n) part is not strictly true. sortedcontainers.SortedList stores data in balanced lists of lists and exploits data locality achieving faster amortized times. Big-O insert complexity is, strictly speaking, O(n^2), but due to large "load factor", amortized insert complexity is ~ n^(1/3).
@randomir Thanks, this is actually something I was aware of, just not at the time I wrote this. My post is fixed now.
Still a good answer, though (I wasn't aware of sortedcontainers, probably because I didn't need them until today :)).

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Related