Based on this older thread, it looks like the cost of list functions in Python is:
- Random access: O(1)
- Insertion/deletion to front: O(n)
- Insertion/deletion to back: O(1)
Can anyone confirm whether this is still true in Python 2.6/3.x?
Add a comment
|
5 Answers
Take a look here. It's a PEP for a different kind of list. The version specified is 2.6/3.0.
Append (insertion to back) is O(1), while insertion (everywhere else) is O(n). So yes, it looks like this is still true.
Operation...Complexity
Copy........O(n)
Append......O(1)
Insert......O(n)
Get Item....O(1)
Set Item....O(1)
Del Item....O(n)
Iteration...O(n)
Get Slice...O(k)
Del Slice...O(n)
Set Slice...O(n+k)
Extend......O(k)
Sort........O(n log n)
Multiply....O(nk)
6 Comments
Dan
Thanks Ryeguy—appreciate it. Also from the TimeComplexity doc referenced by kaizer.se: x in s........... O(n) min(s), max(x)... O(n)
Assad Ebrahim
@ryeguy: Surprised to see that insert and delete are O(n) operations. Isn't the whole point of a list data structure to reduce the time complexity of insert and delete to O(1)? From the above, it seems more like the underlying data structure is an array. Am I missing something?
Mike S
@AKE see array list. There are tradeoffs in different implementations of data structures. In your typical O(1) insert/delete list you often have Get Item as O(n).
Assad Ebrahim
@MikeS: Yes, I see. Subsequent to asking the question, I found that processor architecture also makes a different the choice of actual implementation. For example, processors with cache memory behaviour in which every memory access pulls back a cache line with adjacent memory, means that in fact the O(n) insert/deletes from adjacent memory addresses held in cache can actually be faster than an O(1) memory access from locations spread randomly in memory.
sumanth232
What is the complexity to check if an integer exists in a list of numbers ? >>> 3 in lis
|
Python 3 is mostly an evolutionary change, no big changes in the datastructures and their complexities.
The canonical source for Python collections is TimeComplexity on the Wiki.
Comments
That's correct, inserting in front forces a move of all the elements to make place.
collections.deque offers similar functionality, but is optimized for insertion on both sides.
1 Comment
Assad Ebrahim
Does that mean that the underlying data structure is an array? If it were a list, an insert anywhere, including at the front, should be an O(1) operations, right?
I know this post is old, but I recently did a little test myself. The complexity of list.insert() appears to be O(n)
Code:
'''
Independent Study, Timing insertion list method in python
'''
import time
def make_list_of_size(n):
ret_list = []
for i in range(n):
ret_list.append(n)
return ret_list
#Estimate overhead of timing loop
def get_overhead(niters):
'''
Returns the time it takes to iterate a for loop niter times
'''
tic = time.time()
for i in range(niters):
pass #Just blindly iterate, niter times
toc = time.time()
overhead = toc-tic
return overhead
def tictoc_midpoint_insertion(list_size_initial, list_size_final, niters,file):
overhead = get_overhead(niters)
list_size = list_size_initial
#insertion_pt = list_size//2 #<------- INSERTION POINT ASSIGMNET LOCATION 1
#insertion_pt = 0 #<--------------- INSERTION POINT ASSIGNMENT LOCATION 4 (insert at beginning)
delta = 100
while list_size <= list_size_final:
#insertion_pt = list_size//2 #<----------- INSERTION POINT ASSIGNMENT LOCATION 2
x = make_list_of_size(list_size)
tic = time.time()
for i in range(niters):
insertion_pt = len(x)//2 #<------------- INSERTION POINT ASSIGNMENT LOCATION 3
#insertion_pt = len(x) #<------------- INSERTION POINT ASSIGN LOC 5 insert at true end
x.insert(insertion_pt,0)
toc = time.time()
cost_per_iter = (toc-tic)/niters #overall time cost per iteration
cost_per_iter_no_overhead = (toc - tic - overhead)/niters #the fraction of time/iteration, #without overhead cost of pure iteration
print("list size = {:d}, cost without overhead = {:f} sec/iter".format(list_size,cost_per_iter_no_overhead))
file.write(str(list_size)+','+str(cost_per_iter_no_overhead)+'\n')
if list_size >= 10*delta:
delta *= 10
list_size += delta
def main():
fname = input()
file = open(fname,'w')
niters = 10000
tictoc_midpoint_insertion(100,10000000,niters,file)
file.close()
main()
See 5 positions where insertion can be done. Cost is of course a function of how large the list is, and how close you are to the beginning of the list (i.e. how many memory locations have to be re-organized)
Ignore left image of plot
Comments
Fwiw, there is a faster (for some ops... insert is O(log n)) list implementation called BList if you need it. BList
Comments
