Удалять элементы из списка во время итерации без использования дополнительной памяти в Python

Question

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

Я прочитал несколько других тем по этому вопросу. Два решения шва будут предложены. Либо сделайте словарь из списка (что подразумевает создание копии всех данных, которые уже заполняют всю оперативную память в моем случае). Либо пройтись по списку в обратном порядке (что нарушает концепцию алогрита, который я хочу реализовать).

Есть ли лучший или более элегантный способ сделать это?

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

Answer 1

li = [ x for x in li if condition(x)]

, а также

li = filter(condition,li) 

Спасибо Дэйву Кирби

Answer 2

Вот альтернативный ответ, если вам абсолютно необходимо удалить элементы из исходного списка, и у вас недостаточно памяти для копирования - переместите элементы вниз по списку самостоятельно:

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 достаточно умен, чтобы изменить размер списка без выделения памяти для новой копии списка.

Answer 3

удаление элементов из списка стоит дорого, так как 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

Answer 4

Встроенная функция фильтра сделана именно для этого:

list_of_g = filter(lambda x: not subtle_condition(x), list_of_g)

Answer 5

Звучит как хороший пример использования функции фильтра.

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

Answer 6

Для простоты используйте понимание списка:

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]

Answer 7

Как насчет этого?

[x for x in list_of_g if not subtle_condition(x)]

возвращает новый список за исключением условия subtle_condition

Answer 8

Если вы выполняете обратную итерацию, вы можете удалять элементы на лету, не затрагивая следующие посещаемые вами индексы:

numbers = range(20)

# remove all numbers that are multiples of 3
l = len(numbers)
for i, n in enumerate(reversed(numbers)):
    if n % 3 == 0:
        del numbers[l - i - 1]

print numbers

enumerate(reversed(numbers)) - это просто стилистический выбор. Вы можете использовать диапазон, если он вам более понятен:

l = len(numbers)
for i in range(l-1, -1, -1):
    n = numbers[i]
    if n % 3 == 0:
        del numbers[i]

Если вам нужно перемещаться по списку по порядку, вы можете поменять его местами с помощью .reverse() до и после обратной итерации. Это также не дублирует ваш список.