Python: Использование памяти и оптимизация при изменении списков
Проблема
Мое беспокойство следующее: Я храню относительность большой набор данных в классическом списке Python и для обработки данных, которых я должен несколько раз выполнять итерации по списку, выполнить некоторые операции на элементах и часто высовывать объект из списка.
Кажется, что удаление одного объекта из списка Python стоит O (N), так как Python должен скопировать все объекты выше элемента под рукой вниз одно место. Кроме того, так как количество объектов для удаления приблизительно пропорционально числу элементов в списке, это приводит к O (N^2) алгоритм.
Я надеюсь найти решение, которое экономически эффективно (время и мудро памятью). Я изучил то, что я мог найти в Интернете и суммировал свои различные варианты ниже. Какой является лучшим кандидатом?
Хранение локального индекса:
while processingdata:
index = 0
while index < len(somelist):
item = somelist[index]
dosomestuff(item)
if somecondition(item):
del somelist[index]
else:
index += 1
Это - исходное решение, которое я предложил. Мало того, что это не очень изящно, но и я надеюсь, что существует лучший способ сделать это, который остается временем и эффективной памятью.
Обход списка назад:
while processingdata:
for i in xrange(len(somelist) - 1, -1, -1):
dosomestuff(item)
if somecondition(somelist, i):
somelist.pop(i)
Это старается не увеличивать индексную переменную, но в конечном счете имеет ту же стоимость как исходная версия. Это также повреждает логику dosomestuff (объект), который хочет обработать их в том же порядке, как они появляются в исходном списке.
Вхождение в новый список:
while processingdata:
for i, item in enumerate(somelist):
dosomestuff(item)
newlist = []
for item in somelist:
if somecondition(item):
newlist.append(item)
somelist = newlist
gc.collect()
Это - очень наивная стратегия устранения элементов из списка и требует большой памяти, так как почти полная копия списка должна быть сделана.
Используя понимания списка:
while processingdata:
for i, item in enumerate(somelist):
dosomestuff(item)
somelist[:] = [x for x in somelist if somecondition(x)]
Это очень изящно, но под покрытием, это обходит целый список еще раз и должно скопировать большинство элементов в нем. Моя интуиция - то, что эта операция, вероятно, стоит больше, чем исходный del оператор, по крайней мере, мудрая память. Следует иметь в виду, что somelist может быть огромным и что любое решение, которое выполнит итерации через него только однажды на выполнение, будет, вероятно, всегда побеждать.
Используя функцию фильтра:
while processingdata:
for i, item in enumerate(somelist):
dosomestuff(item)
somelist = filter(lambda x: not subtle_condition(x), somelist)
Это также создает новый список, занимающий много RAM.
Используя функцию фильтра itertool:
from itertools import ifilterfalse
while processingdata:
for item in itertools.ifilterfalse(somecondtion, somelist):
dosomestuff(item)
Эта версия вызова фильтра не создает новый список, но не назовет dosomestuff на каждом объекте, повреждающем логику алгоритма. Я включаю этот пример только в целях создания исчерпывающего списка.
Движущиеся объекты список при обходе
while processingdata:
index = 0
for item in somelist:
dosomestuff(item)
if not somecondition(item):
somelist[index] = item
index += 1
del somelist[index:]
Это - тонкий метод, который кажется экономически эффективным. Я думаю, что это переместит каждый объект (или указатель на каждый объект?) точно однажды приводящий к O (N) алгоритм. Наконец, я надеюсь, что Python будет достаточно интеллектуален для изменения размеров списка в конце, не выделяя память для новой копии списка. Не уверенный все же.
Отказ от списков Python:
class Doubly_Linked_List:
def __init__(self):
self.first = None
self.last = None
self.n = 0
def __len__(self):
return self.n
def __iter__(self):
return DLLIter(self)
def iterator(self):
return self.__iter__()
def append(self, x):
x = DLLElement(x)
x.next = None
if self.last is None:
x.prev = None
self.last = x
self.first = x
self.n = 1
else:
x.prev = self.last
x.prev.next = x
self.last = x
self.n += 1
class DLLElement:
def __init__(self, x):
self.next = None
self.data = x
self.prev = None
class DLLIter:
etc...
Этот тип объекта напоминает список Python ограниченным способом. Однако удалению элемента гарантируют O (1). Я не хотел бы идти сюда, так как это потребует значительных объемов кода, осуществляющих рефакторинг почти везде.
7 ответов
A set (или даже dict) может быть тем, что вы ищете. Это та же базовая структура, что и словарь (без связанных значений), но ваши объекты должны быть хэшируемыми.
Если для вашего списка/набора важен порядок, вы можете сделать упорядоченный набор. На сайте activestate есть хороший рецепт OrderedSet. Есть еще одно хорошее предложение в этом ответе. В Python 2.7 и 3.1 также есть OrderedDict Вы должны протестировать реализацию самостоятельно, чтобы понять, как накладные расходы повлияют на вас, но прирост скорости от хэш-таблицы может стоить того.
В зависимости от того, какого рода сравнения вы делаете с объектами в списке, куча (модуль heapq) также может подойти для вашей проблемы. Куча минимизирует количество операций, необходимых для вставки и удаления элементов в базовом списке.
Вы не предоставляете достаточно информации, которую я могу найти, чтобы действительно хорошо ответить на этот вопрос. Я недостаточно хорошо знаю ваш вариант использования, чтобы сказать вам, какие структуры данных дадут вам желаемые временные сложности, если вам нужно оптимизировать по времени. Типичным решением является создание нового списка, а не повторных удалений, но, очевидно, это удваивает использование памяти.
Если у вас есть проблемы с использованием памяти, вы можете отказаться от использования конструкций Python в памяти и перейти к базе данных на диске. Доступно множество баз данных, и sqlite поставляется с Python. В зависимости от вашего использования и того, насколько жесткими являются ваши требования к памяти, вам могут помочь array.array или numpy, но это сильно зависит от того, что вам нужно делать. array.array будет иметь все те же временные сложности, что и list и numpy массивы вроде как будут, но работать по-разному. Использование ленивых итераторов (таких как генераторы и прочее в модуле itertools ) часто может уменьшить использование памяти в n раз.
Использование базы данных сократит время удаления элементов из произвольных мест (хотя порядок будет потерян, если это важно).Использование dict будет делать то же самое, но потенциально при высоком использовании памяти.
Вы также можете рассмотреть blist как замену для списка, который может получить некоторые из желаемых вами компромиссов. Я не верю, что это резко увеличит использование памяти, но изменит удаление элемента на O (log n). Конечно, это происходит за счет удорожания других операций.
Мне нужно было пройти тестирование, чтобы поверить в то, что постоянный коэффициент использования памяти для вашей реализации двусвязного списка будет меньше двух, которые вы получите, просто создав новый список. Я действительно в этом сомневаюсь.
Я думаю, вам придется больше рассказать о своем классе проблемы, чтобы получить более конкретный ответ, но общий совет таков:
- Перебирайте список, создавая новый список по мере продвижения (или используя генератор, чтобы получить предметы, когда они вам нужны). Если вам действительно нужен список, у него будет коэффициент памяти 2, который отлично масштабируется, но не помогает, если у вас мало периода памяти.
- Если вам не хватает памяти, вместо микрооптимизации вам, вероятно, понадобится база данных на диске или хранение ваших данных в файле.
Брэндон Крейг Роудс предлагает использовать collections.deque , который может решить эту проблему: для операции не требуется дополнительной памяти, и она хранится O (n). Я не знаю общее использование памяти и его сравнение со списком; Стоит отметить, что двухсторонняя очередь должна хранить намного больше ссылок, и я не удивлюсь, если она не будет такой интенсивной по памяти, как использование двух списков. Вам придется проверить или изучить его, чтобы познать себя.
Если бы вы использовали двухстороннюю очередь, я бы развернул ее немного иначе, чем предлагает Роудс:
from collections import deque
d = deque(range(30))
n = deque()
print d
while True:
try:
item = d.popleft()
except IndexError:
break
if item % 3 != 0:
n.append(item)
print n
При этом нет существенной разницы в памяти, но вероятность ошибиться гораздо меньше, чем изменение той же двухсторонней очереди, что и Ваш ход.
Судя по вашему описанию, deque («колода») будет именно тем, что вы ищете:
http://docs.python.org/library/collections.html#deque-objects
«Итерируйте» по нему, многократно вызывая pop (), а затем, если вы хотите сохранить всплывающий элемент в двухсторонней очереди, возвращая этот элемент на передний план с помощью appendleft (item). Чтобы не отставать от того, когда вы закончили итерацию и увидели все в двухсторонней очереди, либо вставьте объект-маркер, например None, за которым вы следите, либо просто запросите функцию len () двухсторонней очереди, когда вы запустите определенный цикл и используете range ( ) для pop () именно такого количества элементов.
Я думаю, вы обнаружите, что все необходимые вам операции равны O (1).
Двусвязный список хуже, чем просто перераспределение списка. В списке Python используется 5 слов + одно слово на элемент. В двусвязном списке будет использоваться 5 слов на элемент. Даже если вы используете односвязный список, он все равно будет состоять из 4 слов на элемент - что намного хуже, чем при перестроении списка менее 2 слов на элемент.
С точки зрения использования памяти наилучшим подходом является перемещение элементов вверх по списку и удаление резервов в конце. Python освободит память, если список заполнится менее чем наполовину. Вопрос, который стоит задать себе, действительно ли это имеет значение. Записи списка, вероятно, указывают на некоторые данные, если у вас нет большого количества повторяющихся объектов в списке, память, используемая для списка, незначительна по сравнению с данными. Учитывая это, вы можете просто создать новый список.
Для построения нового списка предложенный вами подход не очень хорош. Нет никакой очевидной причины, по которой вы не могли бы просто просмотреть список один раз. Кроме того, вызов gc.collect () не нужен и на самом деле вреден - подсчет ссылок CPython в любом случае немедленно освободит старый список, и даже другим сборщикам мусора лучше собирать, когда они сталкиваются с нехваткой памяти. Таким образом, будет работать что-то вроде этого:
while processingdata:
retained = []
for item in somelist:
dosomething(item)
if not somecondition(item):
retained.append(item)
somelist = retained
Если вы не возражаете против использования побочных эффектов в составлении списков, то также можно использовать следующие варианты:
def process_and_decide(item):
dosomething(item)
return not somecondition(item)
while processingdata:
somelist = [item for item in somelist if process_and_decide(item)]
Метод inplace также можно реорганизовать, чтобы разделить механизм и бизнес-логику:
def inplace_filter(func, list_):
pos = 0
for item in list_:
if func(item):
list_[pos] = item
pos += 1
del list_[pos:]
while processingdata:
inplace_filter(process_and_decide, somelist)
Не зная подробностей того, что вы делаете с этим списком, трудно точно сказать, что было бы лучше в этом случае. Если ваш этап обработки зависит от текущего индекса элемента списка, это не сработает, но если нет, похоже, вы отказались от самого Pythonic (и во многих отношениях самого простого) подхода: генераторы.
Если все, что вы делаете, - это итерация по каждому элементу, его обработка каким-либо образом, а затем включение этого элемента в список или нет, используйте генератор. Тогда вам никогда не придется хранить в памяти всю итерацию.
def process_and_generate_data(source_iterable):
for item in source_iterable:
dosomestuff(item)
if not somecondition(item):
yield item
Вам понадобится цикл обработки, который будет иметь дело с сохранением обработанного итеративного объекта (записывая его обратно в файл или что-то еще), или, если у вас есть несколько этапов обработки, которые вы бы предпочли разделить на разные генераторы, вы могли бы цикл обработки передает один генератор следующему.
Python хранит только ссылки на объекты в списке, но не сами элементы. Если вы увеличиваете список элемент за элементом, список (то есть список ссылок на объекты) будет расти один за другим, в конечном итоге достигая конца избыточной памяти, которую Python предварительно выделил в конце список литературы!). Затем он копирует список (ссылок!) В новое место большего размера, в то время как элементы списка остаются на своем старом месте. Поскольку ваш код в любом случае посещает все элементы в старом списке, копирование ссылок в новый список с помощью new_list [i] = old_list [i] почти не будет обременительным. Единственный совет по производительности - выделить все новые элементы сразу, а не добавлять их (OTOH в документах Python говорится, что амортизируемое добавление по-прежнему равно O (1), поскольку количество лишних элементов растет с размером списка). Если вам не хватает места для нового списка (ссылок), то я боюсь, что вам не повезло - любая структура данных, которая уклоняется от O (n) вставки / удаления на месте, вероятно, будет больше, чем простой массив из 4 - или 8-байтовые записи.