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