В чем разница между двумя циклами for: при удалении элементов во время обхода списка

#python #циклы #list #список #python_internals

Почему интерпретатор в первом случае убирает только 3 нуля ['1', '0', '0', '0'],
а во втором удаляет полностью, в чем разница? For - работает с каждым итерируемым объектом
по очереди, почему он пропускает 3 нуля?

list1 = ['1', '0', '0', '0', '0', '0', '0', '0', '0', '1']
for _ in list1:
    list1.remove('0') 
print(list1)

nuly = ['3', '2', '0', '0', '3', '5', '0', '0', '0', '8', '0'] 
for _ in nuly:
    nuly.remove('0')
print(nuly)

    

Ответы

Ответ 1

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

При обходе списка, цикл for не копирует его, а создаёт итератор, который элементы
из списка по одному возвращает. Поэтому когда вы удаляете элемент (.remove('0') ищет
один '0' в списке и удаляет его), то список изменяется и эти изменения видны в итераторе. 

В текущей реализации СPython, итератор списка хранит ссылку на сам список и текущий
индекс в нём. Элементы возвращаются пока длина списка больше текущего индекса. Вот
суть next(list_iterator) вызова, возвращающего следующий элемент на каждой итерации:

listiter_next(listiterobject *it)
{
    ... 
    if (it->it_index < PyList_GET_SIZE(it->it_seq)) {
        item = PyList_GET_ITEM(seq, it->it_index);
        ++it->it_index;
        return item;
    }
    ...
}


Что на Питоне выглядит как:

if i < len(lst):
    item = lst[i]
    i += 1
    return item


Если по шагам выполнить код на pythontutor.com:

#XXX BROKEN
lst = [0, '0', '0', '0', '0', '0', '0', '0', '0', 9]
for i, x in enumerate(lst):
    lst.remove('0') 
    size = len(lst)
print(lst) # -> [0, '0', '0', '0', 9]


Можно увидеть, что цикл продолжается до тех пор пока i < size. Поэтому цикл может
завершиться до того как все '0' элементы удалены.



Если вы хотите удалить '0' из списка, то обычный способ:

lst[:] = [x for x in lst if x != '0']


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

def remove_all(seq, value):
    pos = 0
    for item in seq:
        if item != value:
           seq[pos] = item
           pos += 1
    del seq[pos:]

remove_all(lst, '0')


Оба решения линейные—O(n). Первое решение требует O(n-k) дополнительной памяти, где
k = lst.count('0').

Если известно, что в большом списке, только несколько значений нужно удалить (k маленькое
и не зависит от n), то можно использовать удаление del lst[i], обходя список в обратном
порядке  (так как удаление не влияет на элементы в начале списка):

for i in reversed(range(len(lst))):
    if lst[i] == '0':
        del lst[i] # O(n) * k == O(n * k)


В общем случае это квадратичный алгоритм O(n**2). 

Чем плохи квадратичные алгоритмы

Квадратичные решения могут быть заметно медленнее для больших n, чем линейные.

К примеру, линейный алгоритм для списка с миллионом элементов требует не больше чем
C1 * 1000_000 шагов (инструкций), в то время как квадратичный алгоритм C2 * 1000_000_000_000,
где C1, C2 константы, не зависящие от размера входного списка. C1, C2 примерно (по
порядку величины) равны в этом случае, поэтому линейный алгоритм гораздо более предпочтителен,
если k ~ n.

Если миллион инструкций выполняются примерно за миллисекунду (даже моргнуть не успеете),
то квадратичный алгоритм займёт целый день, если у кого-то терпения хватит ждать или
батарейка не сядет пока закончится выполнение.

Миллион элементов не является каким-то большим вводом в современных условиях (телефоны
гигабайты памяти имеют).

Как правило можно игнорировать константы (C1, C2 в примере) вне горячих точек (hot
spots), к примеру, если константа на порядок изменится (в 10 раз), то миллион инструкций
линейного алгоритма займёт в 10 раз дольше: ~10 миллисекунд (всё равно быстрее чем
моргнуть успеете) и гораздо меньше многих часов для квадратичного алгоритма с ~1012
операций.

Подытоживая: записывая алгоритм, стоит ориентироваться на простоту, читаемость и
может ли он в принципе выполнить поставленную задачу. Микро-оптимизациями, которые
уродуют код, улучшая только константу (C1, C2 в примере), лучше не заниматься, если
profiler не говорит обратного. Если заранее не известно, что ввод ограничен по размеру,
то стоит обратить внимание на порядок роста (big O) используемого алгоритма. В частности,
если это заметно не затрудняет реализацию, то линейные алгоритмы (O(n)) гораздо более
предпочтительны по сравнению с квадратичными (O(n*n)). Примеры из реального мира: https://accidentallyquadratic.tumblr.com/


Ответ 2

Различие состоит в количестве элементов в контейнерах и количестве нулей в каждом из них.

Когда вы удаляете 0, то размер контейнера уменьшается. Например, для первого случая
это можно представить следующим образом.

Пусть идентификатор i является индексом элементов последовательности, а идентификатор
n  - общим количеством элементов в последовательности. После каждой итерации цикла
индекс увеличивается на единицу, чтобы обратиться к следующему элементу.

Итак, для первого цикла начальные значения i = 0, n = 10. Теперь пройдемся по итерациям
цикла 

i = 0; remove( 0 ); n = 9
i = 1; remove( 0 ); n = 8
i = 2; remove( 0 ); n = 7
i = 3; remove( 0 ); n = 6
i = 4; remove( 0 ); n = 5
i = 5; n <= i итерация не выполняется.


В результате имеем, что было выполнено 5 удалений.

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