Космическая сложность фрагментов списка Python

Мне трудно понять пространственную сложность фрагментов списка Python.

Для чего-то вроде

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

новое пространство выделяется для среза (например, сделано в Строках, поскольку они являются неизменяемыми) или операция выполняется в одном массиве?

Для чего-то вроде:

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

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

Какова будет сложность пространства? Будет ли это иначе или так же, как когда ans является строкой, что-то вроде ans = '12345...n'?

2 ответа

Python строго придерживается возможных побочных эффектов. Что касается языка, то некорректно выполнять какие-либо операции на месте.

Ваша операция

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

три отдельных операции среза:

  • arr[2:] создает новый список из всех элементов (но первых двух) arr.
  • ...[::-1] создает новый, перевернутый список из всех элементов ...
  • arr[2:] =... заменяет все элементы (но первые два) из arr с ...

Каждая операция среза в основном сводится к операции копирования примитива O (n). Поскольку копируются только ссылки, размер или тип элементов не имеет значения.

В вашем полном примере это три операции O (n) среза в цикле O (k):

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

В целом, временная сложность составляет O (nk). Космическая сложность - это только O (n), так как временные срезы немедленно восстанавливаются. В основном вы получаете исходный список, а также несколько временных копий.

Будет ли это иначе или так же, как когда <code>ans</code> является строкой, что-то вроде <code>ans = '12345...n'</code>?

Сложность операций не меняется - они все еще являются одними и теми же примитивными операциями.

Практически, реализация CPython обманывает определенные объекты. Например, += - мутация inplace для строк с refcount 1, хотя строки неизменяемы. Однако это не относится к использованию вашего среза.

В целом, полагаясь на встроенные оптимизации, это плохая идея с Python.

Если вы беспокоитесь о пространстве, начните с написания скудного кода. Например, ans[i:][::-1] должен просто быть ans[i::-1]. Это само по себе уменьшает временное пространство.


Вкратце, каждая операция разрезания списков включает в себя создание копии соответствующих ссылок на объекты (но не самих объектов).

В вашем примере:

  • arr[2:] делает копию ссылок на объекты, хранящихся в arr начиная с индекса 2, и помещает их в неназванный новый список (который я буду называть L1).
  • [::-1] делает копию ссылок на объекты в L1 и помещает их в обратном порядке в неназванный новый список (который я буду называть L2).
  • arr[2:] =... заменяет ссылки на объекты, хранящиеся в arr на те, которые хранятся в L2.

Стоит отметить, что ничто из этого не гарантировано. Это именно то, что сейчас делает CPython.

Некоторые соответствующие функции:

  • list_slice - простой срез (без шага)
  • list_subscript - индекс, вкл. расширенный срез (с шагом)
  • list_ass_slice - простое назначение среза (без шага)
  • list_ass_subscript - присвоение индекса, вкл. используя расширенный срез

Взгляните на реализацию list: https://github.com/python/cpython/blob/master/Objects/listobject.c

Там есть некоторые интересные лакомые кусочки, такие как код, который защищает от a[::-1] = a.

licensed under cc by-sa 3.0 with attribution.