Space Complexity of Python List Slices

Question

I'm having difficulty understanding the Space Complexity of Python List Slices.

For something like

arr[2:] = arr[2:][::-1]

is new space being allocated for the slice (like done in Strings since they are immutable) or is the operation done on the same array?

For something like:

ans = [i+1 for i in range(n)]

for i in range(k):
    ans[i:] = ans[i:][::-1]

What will be the space complexity? Will it be different or same than when ans is a string, something like ans = '12345...n'?

To answer your first question, [this might help](https://stackoverflow.com/questions/5131538/slicing-a-list-in-python-without-generating-a-copy). — Matthew Cassell, Jun 23 '18 at 16:44
assign the slice to a variable, check and compare `id(...)`s. — Patrick Artner, Jun 23 '18 at 17:13
@Matos cool find, the "Short answer" to the other Q answers this one fully. Voting to close. — Patrick Artner, Jun 23 '18 at 17:16
The linked question is not concerned with space complexity or inplace mutation at all. Vote for reopen. — MisterMiyagi, Jun 24 '18 at 21:16

MisterMiyagi · Accepted Answer · 2018-06-23T17:55:29.023

Python is strict about adhering to possible side effects. As far as the language is concerned, it is incorrect to perform any of your operations inplace.

Your operation

 arr[2:] = arr[2:][::-1]

are three separate slice operations:

arr[2:] creates a new list from all elements (but the first two) of arr.
...[::-1] creates a new, reversed list from all elements of ....
arr[2:] = ... replaces all elements (but the first two) of arr with ....

Each slice operation basically amounts to a primitive O(n) copy operation. Since only references are copied, the size or type of elements does not matter.

In your complete example, that amounts to three O(n) slice operations in an O(k) loop:

ans = [i+1 for i in range(n)]   # O(n)
for i in range(k):              # O(k)
    ans[i:] = ans[i:][::-1]     # O(n)

In total, the time complexity amounts to O(nk). Space complexity is only O(n), since the temporary slices are reclaimable immediately. You basically end up with the initial list, plus some temporary copies.

Will it be different or same than when ans is a string, something like ans = '12345...n'?

The complexity of the operations does not change - they are still the same primitive operations.

Practically, the CPython implementation cheats with certain objects. For example, += is inplace mutation for strings with refcount 1 even though strings are immutable. However, this does not apply to your slice usage.

In general, relying on inbuilt optimisations is a bad idea with Python.

If you are worried about space, start with writing lean code. For example, ans[i:][::-1] should simply be ans[i::-1]. That alone halves the temporary space required.

score 2 · Answer 2 · answered Jun 23 '18 at 17:15

In a nutshell, every list slicing operation involves making a copy of the relevant object references (but not the objects themselves).

In your example:

arr[2:] makes a copy of the object references stored in arr starting at index 2, and places them into an unnamed new list (which I'll refer to as L1).
[::-1] makes a copy of the object references in L1 and places them, in reverse order, into an unnamed new list (which I'll refer to as L2).
arr[2:] = ... replaces object references stored in arr with those stored in L2.

It's worth noting that none of this is guaranteed. This is just what CPython does currently.

Some relevant functions are:

list_slice - simple slice (no stride)
list_subscript - subscript, inc. extended slice (with stride)
list_ass_slice - simple slice assignment (no stride)
list_ass_subscript - subscript assignment, inc. using an extended slice

Take a look at the implementation of list: https://github.com/python/cpython/blob/master/Objects/listobject.c

There are some fun tidbits to be found there, such as code that protects against a[::-1] = a.

Space Complexity of Python List Slices

2 Answers2