Does reusing a list fragment to get length require extra memory?

Question

I suggested something in the comment in this answer . Martijn Pieters said that my proposal will be intense in memory, and he is usually right, but I like to see things for myself, so I tried to comment on it. Here is what I got:

#!/usr/bin/env python """ interpolate.py """ from memory_profiler import profile @profile def interpolate1(alist): length = (1 + len(alist)) // 2 alist[::2] = [0] * length @profile def interpolate2(alist): length = len(alist[::2]) alist[::2] = [0] * length a = [] b = [] for i in range(5, 9): print i exp = 10**i a[:] = range(exp) b[:] = range(exp) interpolate1(a) interpolate2(b) 

I do not see any gradual difference in the cost of memory for solving a slice, but sometimes I see one for an arithmetic solution. Take the results at exp = 7 , for example:

 7 Filename: interpolate.py Line # Mem usage Increment Line Contents ================================================ 5 750.1 MiB 0.0 MiB @profile 6 def interpolate1(alist): 7 750.1 MiB 0.0 MiB length = (1 + len(alist)) // 2 8 826.4 MiB 76.3 MiB alist[::2] = [0] * length Filename: interpolate.py Line # Mem usage Increment Line Contents ================================================ 10 826.4 MiB 0.0 MiB @profile 11 def interpolate2(alist): 12 826.4 MiB 0.0 MiB length = len(alist[::2]) 13 826.4 MiB 0.0 MiB alist[::2] = [0] * length 

I tried several other profiling approaches, including running interpolate2 to interpolate1 , randomizing the order of execution, and significantly smaller lists, but the results are pretty consistent.

I can postulate that the results are that the memory is allocated to slice the list in any case, regardless of whether it is on the right or left side of the job, but no matter how you cut it, it looks like the slice solution is torn with arithmetic solution. Am I interpreting these results correctly?

Answer 1

Yes, additional memory will be reserved for a new list object that is created only for slice.

However, the request object is discarded again after the length request. You simply created a list object to calculate how much half the list will be.

Memory allocation is relatively expensive, even if you drop the object again. This is what I had in mind while you are looking for a steady increase in memory. However, a transition list object may be, you still need to allocate memory for this object.

The cost immediately manifests itself when you use timeit to compare two approaches:

 >>> import timeit >>> def calculate(alist): ... (1 + len(alist)) // 2 ... >>> def allocate(alist): ... len(alist[::2]) ... >>> testlist = range(10**5) >>> timeit.timeit('f(testlist)', 'from __main__ import testlist, calculate as f', number=10000) 0.003368854522705078 >>> timeit.timeit('f(testlist)', 'from __main__ import testlist, allocate as f', number=10000) 2.7687110900878906 

A slice should only create a list object and copy half the links, but this operation takes 800 times longer, simply calculating the length from the existing list.

Note that I really had to reduce the number of timeit repetitions; by default, 1 million reps will take an additional 4.5 minutes. I was not going to wait so long, while the direct calculation took only 0.18 seconds.