Проблема
Моя забота заключается в следующем: я храню большой набор данных относительности в классическом списке 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 (item), который хочет обработать их в том же порядке, что и в исходном списке.
Создание нового списка:
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)
Это также создает новый список, занимающий много ОЗУ.
Использование функции фильтрации itertools:
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). Мне бы не хотелось идти сюда, так как это потребовало бы большого количества рефакторинга кода почти везде.
