CODEWITHSUNDEEP
pythonperformancelist
Dan
Dan

Reputation: 1697

Cost of list functions in Python

Based on this older thread, it looks like the cost of list functions in Python is:

Can anyone confirm whether this is still true in Python 2.6/3.x?

Upvotes: 21

Views: 28383

Answers (5)

tgabb
tgabb

Reputation: 379

I know this post is old, but I recently did a little test myself. The complexity of list.insert() appears to be O(n)

Cost of Insertion. Ignore left plot

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

Upvotes: 4

Gregg Lind
Gregg Lind

Reputation: 21302

Fwiw, there is a faster (for some ops... insert is O(log n)) list implementation called BList if you need it. BList

Upvotes: 2

u0b34a0f6ae
u0b34a0f6ae

Reputation: 49813

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.

Upvotes: 10

ryeguy
ryeguy

Reputation: 66851

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)

Upvotes: 45

RedGlyph
RedGlyph

Reputation: 11579

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.

Upvotes: 4

Related Questions