Python tuple assignment vs list appending

Question

Which one of the following code is more effcient when considering runtime(Big O) and memory usage?

Code 1:

a = []

for item in some_data:
   a.append(item.id)
   # some other code

print(a)

Case 2:

a = tuple()

for item in some_data:
   a += (item.id,)
   # some other code

print(a)

Here:some_data can be 1 or n data.

My guess is that the Code 2 is efficient because it use less memory and probably pusing and poping data in/out from stack memeory for the assignment operation.

I think Code 1 is less efficient because usually list over allocate memory and while appending data it have to find new memory address when allocated memeory exceeds.

BTW, I am just a beginner in data Structures and algorithms and no idea how python manages variable in memory.

Answer 1

I wrote simple script for benchmark time and memory usage.

import time
import functools
from memory_profiler import profile


def timer(func):
    @functools.wraps(func)
    def wrapper_timer(*args, **kwargs):
        start_time = time.perf_counter()

        value = func(*args, **kwargs)

        end_time = time.perf_counter()

        run_time = end_time - start_time

        print(f"Finished {func.__name__!r} in {run_time:.4f} seconds")

        return value

    return wrapper_timer


LOOPS = 100000


@timer
def test_append():
    sample = []
    for i in range(LOOPS):
        sample.append(i)


@timer
def test_tuple():
    sample = tuple()
    for i in range(LOOPS):
        sample += (i, )


@profile(precision=2)
def main():
    test_append()
    test_tuple()


if __name__ == '__main__':
    main()

When LOOPS is 100000

Finished 'test_append' in 0.0745 seconds
Finished 'test_tuple' in 22.3031 seconds

Line #    Mem usage    Increment   Line Contents
================================================
73    38.00 MiB    38.00 MiB   @profile(precision=2)
74                             def main():
75    38.96 MiB     0.97 MiB       test_append()
76    39.10 MiB     0.13 MiB       test_tuple()

When LOOPS is 1000

Finished 'test_append' in 0.0007 seconds
Finished 'test_tuple' in 0.0019 seconds

Line #    Mem usage    Increment   Line Contents
================================================
73    38.04 MiB    38.04 MiB   @profile(precision=2)
74                             def main():
75    38.04 MiB     0.00 MiB       test_append()
76    38.04 MiB     0.00 MiB       test_tuple()

So append is faster than tuple but occupies more memory

Answer 2

Considerind memory usage, i would say the list is better.

On the line

a += (item.id,)

what you are basically doing is a = a + (item.id,) (im doing shortcut, but there is some little differences.)

For this, there is 4 operations :

• creating a tuple =>(item.id,)
• merging 2 tuples => a + (item.id,)
  • create a bigger tuple
  • insert a inside
  • insert (item.id,) inside

Creation of new object (here tuple) is what takes most time. And it is done 2 times each iterations.

On the other side, appending a list != creating a new list. So in the example with list, there is no creation (except for a = [])

Considering execution time :

In [1]: some_data = list(range(10000))                                                                                                                                                                                 

In [2]: %%timeit
        a = tuple()

        for item in some_data:
            a += (item,)                                                                                                                                                                                             
Out[2]: 151 ms ± 1.49 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)



In [3]: %%timeit
        a = []

        for item in some_data:
            a.append(item)                                                                                                                                                                                            
Out[3]: 406 µs ± 3.39 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)


In [4]: %%timeit
        a = [item for item in some_data]  
                                                                                                                                                                                      
Out[4]: 154 µs ± 392 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

So list comprehension is 1000x faster than tuple.