43

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

  • Indexing: list[x]
  • Popping from the end: list.pop()
  • Popping from the beginning: list.pop(0)
  • Extending the list: list.append(x)

For extra credit, splicing or arbitrary pops.

Marquis Wang
  • 10,878
  • 5
  • 30
  • 25
  • Are you using pop or append anywhere? I don't see it. Indexing is O(1) so your code is already optimally efficient. What is `bar` doing? – ggorlen Jan 11 '23 at 18:19

5 Answers5

37

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)
SilentGhost
  • 307,395
  • 66
  • 306
  • 293
  • 1
    Forgive my ignorance, but where is the complexity for `pop()` on that page? – Zaz Oct 03 '15 at 23:20
  • 2
    @Zaz, pop() with no index is O(1), with index, e.g. the first on list, it is O(n). since you need to get the item O(1) and then delete it. The latter takes O(n) time in order to arrange all the other items on the list. More on that here: https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt – ofer.sheffer Oct 16 '15 at 16:32
  • 1
    Indexing is O(1) so this answer is no more efficient from a complexity standpoint than OP's original code, although it's certainly cleaner. If OP has an efficiency problem, it's in the code they didn't show. – ggorlen Jan 11 '23 at 18:19
8

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)
anthony
  • 40,424
  • 5
  • 55
  • 128
  • Oops, I'm aware that my method was somewhat less than Pythonic. For my loop, I needed the item, as well as the index. Is there a good way to do that? (Editing my question) – Marquis Wang Jun 17 '09 at 07:45
6

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

Brian
  • 116,865
  • 28
  • 107
  • 112
3

if you need index and value then use enumerate:

for idx, item in enumerate(range(10, 100, 10)):
    print idx, item
Bhargav Rao
  • 50,140
  • 28
  • 121
  • 140
Maxim Kim
  • 6,192
  • 2
  • 29
  • 28
1

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/

codersofthedark
  • 9,183
  • 8
  • 45
  • 70