Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Performance of list(...).insert(...)

I thought about the following question about computer's architecture. Suppose I do in Python

from bisect import bisect
index = bisect(x, a)      # O(log n)  (also, shouldn't it be a standard list function?)
x.insert(index, a)        # O(1) + memcpy()

which takes log n, plus, if I correctly understand it, a memory copy operation for x[index:]. Now I read recently that the bottleneck is usually in the communication between processor and the memory so the memory copy could be done by RAM quite fast. Is it how that works?

like image 654
ilya n. Avatar asked Jul 10 '09 15:07

ilya n.


2 Answers

Python is a language. Multiple implementations exist, and they may have different implementations for lists. So, without looking at the code of an actual implementation, you cannot know for sure how lists are implemented and how they behave under certain circumstances.

My bet would be that the references to the objects in a list are stored in contiguous memory (certainly not as a linked list...). If that is indeed so, then insertion using x.insert will cause all elements behind the inserted element to be moved. This may be done efficiently by the hardware, but the complexity would still be O(n).

For small lists the bisect operation may take more time than x.insert, even though the former is O(log n) while the latter is O(n). For long lists, however, I'd hazard a guess that x.insert is the bottleneck. In such cases you must consider using a different data structure.

like image 65
Stephan202 Avatar answered Sep 24 '22 23:09

Stephan202


Use the blist module if you need a list with better insert performance.

like image 30
Seun Osewa Avatar answered Sep 22 '22 23:09

Seun Osewa