Нарезка списка в Python без генерации копии - PullRequest
61 голосов
/ 27 февраля 2011

У меня следующая проблема.

Учитывая список целых чисел L, мне нужно создать все подсписки L[k:] for k in [0, len(L) - 1], без генерации копий .

Как мне это сделать в Python?С буферным объектом как-нибудь?

Ответы [ 2 ]

95 голосов
/ 27 февраля 2011

Краткий ответ

Список списков не создает копии объектов в списке;он просто копирует ссылки на них.Это ответ на заданный вопрос.

Длинный ответ

Тестирование на изменяемые и неизменяемые значения

Сначала давайте проверим основное утверждение.Мы можем показать, что даже в случае неизменяемых объектов, таких как целые числа, копируется только ссылка.Вот три разных целочисленных объекта, каждый из которых имеет одно и то же значение:

>>> a = [1000 + 1, 1000 + 1, 1000 + 1]

Они имеют одинаковое значение, но вы можете видеть, что это три разных объекта, потому что они имеют разные id s:

>>> map(id, a)
[140502922988976, 140502922988952, 140502922988928]

Когда вы их нарезаете, ссылки остаются прежними.Новые объекты не созданы:

>>> b = a[1:3]
>>> map(id, b)
[140502922988952, 140502922988928]

Использование разных объектов с одинаковым значением показывает, что процесс копирования не беспокоит interning - он просто напрямую копирует ссылки.

Тестирование с изменяемыми значениями дает тот же результат:

>>> a = [{0: 'zero', 1: 'one'}, ['foo', 'bar']]
>>> map(id, a)
[4380777000, 4380712040]
>>> map(id, a[1:]
... )
[4380712040]

Изучение оставшихся накладных расходов памяти

Конечно, ссылки сами копируются.Каждый из них стоит 8 байтов на 64-битной машине.И каждый список имеет свою собственную служебную память 72 байта:

>>> for i in range(len(a)):
...     x = a[:i]
...     print('len: {}'.format(len(x)))
...     print('size: {}'.format(sys.getsizeof(x)))
... 
len: 0
size: 72
len: 1
size: 80
len: 2
size: 88

Поскольку Джо Пинсоно напоминает нам , эта дополнительная нагрузка складывается.А сами целочисленные объекты не очень большие - они в три раза больше, чем ссылки.Так что это экономит память в абсолютном смысле, но асимптотически было бы неплохо иметь возможность иметь несколько списков, которые являются «представлениями» в одной и той же памяти.

Экономия памяти с использованием представлений

К сожалению, в Python нет простого способа создания объектов, которые являются «представлениями» в списках.Или, может быть, я должен сказать «к счастью»!Это означает, что вам не нужно беспокоиться о том, откуда взялся ломтик;изменения оригинала не повлияют на срез.В целом, это значительно упрощает рассуждения о поведении программы.

Если вы действительно хотите сэкономить память, работая с представлениями, рассмотрите возможность использования numpy массивов.Когда вы срезаете массив numpy, память распределяется между срезом и оригиналом:

>>> a = numpy.arange(3)
>>> a
array([0, 1, 2])
>>> b = a[1:3]
>>> b
array([1, 2])

Что происходит, когда мы изменяем a и снова смотрим на b?

>>> a[2] = 1001
>>> b
array([   1, 1001])

Но это означает, что вы должны быть уверены, что когда вы изменяете один объект, вы случайно не модифицируете другой.Это компромисс при использовании numpy: меньше работы для компьютера и больше работы для программиста!

20 голосов
/ 27 февраля 2011

В зависимости от того, что вы делаете, вы можете использовать islice.

Так как он работает через итерацию, он не будет создавать новые списки, но вместо этого просто создаст итераторы, которые yield элементов из исходного списка, как запрошено для их диапазонов.

...