0

(Assuming you know the size of the list beforehand)

Comparing these two functions:

def foo_1(size=1000):
    res = []
    for i in range(size):
        res.append(i)

def foo_2(size=1000):
    res = [0]*size
    for i in range(size):
        res[i] = i


%timeit foo_1(5000)
290 µs ± 54.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit foo_2(5000)
207 µs ± 4.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit foo_1(1000000)
84.5 ms ± 1.76 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit foo_2(1000000)
52 ms ± 365 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

At a few thousand elements the difference is not that significant. At around a million elements there's a 30ms difference in performance.

Questions

  1. In foo_1, we are appending elements one by one to the list and hence traversing the list once, but in foo_2 we are traversing the list twice (once to initiate, and once to fill the correct values) Shouldn't foo_1 be faster?

I may be getting confused because I'm thinking of linked list type implementation for lists in Python (where there is a pointer which knows the current last position of the list) but I'm sure since lists allow index-based access, it is more complicated than a simple linked list

  1. Given I know that foo_2 is faster, is there any situation/use-case where foo_1 approach (appending rather than filling up) is the way to go?
Ambareesh
  • 324
  • 1
  • 4
  • 18
  • 1
    Python lists are implemented as C dynamic arrays, it resizes if it runs out of space: https://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented – brokenfoot Nov 16 '19 at 23:54
  • 1
    Pre-allocation is always faster when the list grows since python has to dynamically allocate memory to increase the list size dynamically. See here (not explicitly related, but explains the behavior: https://stackoverflow.com/questions/40018398/list-uses-slightly-more-memory-than-list-comprehension/40018719#40018719 ). Python optimizes this by over-allocating space in the list so the amortized cost is low, but its still sub-optimal if you know the list size in advance. – Reut Sharabani Nov 17 '19 at 00:06

0 Answers0