Почему интерпретатор в первом случае убирает только 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)
Оба цикла одинаковые. Только входные списки разные. Вы удаляете элементы из списка, одновременно обходя его.
При обходе списка, цикл 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/
Различие состоит в количестве элементов в контейнерах и количестве нулей в каждом из них.
Когда вы удаляете 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 удалений.
Это схематическое объяснение работы цикла. Реализация цикла может быть иной, но тем не менее данная модель демонстрирует, что используемый подход к удалению элементов из последовательности некорректен и ведет к непредсказуемому результату.
