Удалите объекты из списка при итерации, не используя дополнительную память в Python
Моя проблема проста: у Меня есть длинный список элементов, которых я хочу выполнить итерации через и проверить каждый элемент по условию. В зависимости от результата условия я хотел бы удалить элемент тока списка и продолжить выполнять итерации по нему, как обычно.
Я считал несколько других потоков по этому вопросу. Два шва решений, которые будут предложены. Любой делает словарь из списка (который подразумевает создание копии всех данных, которые уже заполняют всю RAM в моем случае). Любой обход список наоборот (который повреждает понятие алгоритма, который я хочу реализовать).
Есть ли какой-либо лучше или более изящный путь, чем это, чтобы сделать это?
def walk_list(list_of_g):
g_index = 0
while g_index < len(list_of_g):
g_current = list_of_g[g_index]
if subtle_condition(g_current):
list_of_g.pop(g_index)
else:
g_index = g_index + 1
7 ответов
Вот альтернативный ответ, если вам абсолютно необходимо удалить элементы f из исходного списка, а у вас недостаточно памяти для создания копии - переместите элементы вниз по списку самостоятельно:
def walk_list(list_of_g):
to_idx = 0
for g_current in list_of_g:
if not subtle_condition(g_current):
list_of_g[to_idx] = g_current
to_idx += 1
del list_of_g[to_idx:]
Это переместит каждый элемент (фактически указатель на каждый элемент) ровно один раз, поэтому будет O (N ). Оператор del в конце функции удалит все нежелательные элементы в конце списка, и я думаю, что Python достаточно умен, чтобы изменять размер списка без выделения памяти для новой копии списка.
удаление элементов из списка является дорогостоящим, поскольку python должен скопировать все элементы выше g_index на одно место. Если количество элементов, которые вы хотите удалить, пропорционально длине списка N, тогда ваш алгоритм будет O (N ** 2). Если список достаточно длинный, чтобы заполнить вашу оперативную память, вам придется очень долго ждать его завершения.
Более эффективно создать отфильтрованную копию списка либо с использованием понимания списка, как показал Марсело, либо с использованием функций filter или itertools.ifilter:
g_list = filter(not_subtle_condition, g_list)
Если вам не нужно использовать новый список и только хотите выполнить итерацию по нему один раз, тогда лучше использовать ifilter, поскольку это не создаст второй список:
for g_current in itertools.ifilter(not_subtle_condtion, g_list):
# do stuff with g_current
Встроенная функция фильтра предназначена только для этого:
list_of_g = filter(lambda x: not subtle_condition(x), list_of_g)
Как насчет этого?
[x for x in list_of_g if not subtle_condition(x)]
он возвращает новый список с исключением из subtle_condition
Для простоты используйте понимание списка:
def walk_list(list_of_g):
return [g for g in list_of_g if not subtle_condition(g)]
Конечно , это не меняет исходный список, поэтому код вызова должен быть другим.
Если вы действительно хотите изменить список (редко лучший вариант), вернуться назад проще:
def walk_list(list_of_g):
for i in xrange(len(list_of_g), -1, -1):
if subtle_condition(list_of_g[i]):
del list_of_g[i]
Похоже, это действительно хороший вариант использования функции filter.
def should_be_removed(element):
return element > 5
a = range(10)
a = filter(should_be_removed, a)
Однако, это не удалит список во время итерации (и я не рекомендую этого делать). Если для экономии места в памяти (или по другим причинам производительности) вам это действительно необходимо, вы можете сделать следующее:
i = 0
while i < len(a):
if should_be_removed(a[i]):
a.remove(a[i])
else:
i+=1
print a