CODEWITHSUNDEEP
pythoncomplexity-theory
Marquis Wang
Marquis Wang

Reputation: 11118

What is the runtime complexity of python list functions?

I was writing a python function that looked something like this

def foo(some_list):
   for i in range(0, len(some_list)):
       bar(some_list[i], i)

so that it was called with

x = [0, 1, 2, 3, ... ]
foo(x)

I had assumed that index access of lists was O(1), but was surprised to find that for large lists this was significantly slower than I expected.

My question, then, is how are python lists are implemented, and what is the runtime complexity of the following

For extra credit, splicing or arbitrary pops.

Upvotes: 43

Views: 42252

Answers (5)

Maxim Kim
Maxim Kim

Reputation: 6412

if you need index and value then use enumerate:

for idx, item in enumerate(range(10, 100, 10)):
    print idx, item

Upvotes: 3

codersofthedark
codersofthedark

Reputation: 9665

Python list actually nothing but arrays. Thus,

indexing takes O(1)

for pop and append again it should be O(1) as per the docs

Check out following link for details:

http://dustycodes.wordpress.com/2012/03/31/pythons-data-structures-complexity-analysis/

Upvotes: 1

Brian
Brian

Reputation: 119361

Lists are indeed O(1) to index - they are implemented as a vector with proportional overallocation, so perform much as you'd expect. The likely reason you were finding this code slower than you expected is the call to "range(0, len(some_list))".

range() creates a new list of the specified size, so if some_list has 1,000,000 items, you will create a new million item list up front. This behaviour changes in python3 (range is an iterator), to which the python2 equivalent is xrange, or even better for your case, enumerate

Upvotes: 6

SilentGhost
SilentGhost

Reputation: 319949

there is a very detailed table on python wiki which answers your question.

However, in your particular example you should use enumerate to get an index of an iterable within a loop. like so:

for i, item in enumerate(some_seq):
    bar(item, i)

Upvotes: 37

anthony
anthony

Reputation: 41118

The answer is "undefined". The Python language doesn't define the underlying implementation. Here are some links to a mailing list thread you might be interested in.

Also, the more Pythonic way of writing your loop would be this:

def foo(some_list):
   for item in some_list:
       bar(item)

Upvotes: 8

Related Questions