6

Почему интерпретатор в первом случае убирает только 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

2 ответа 2

13

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

При обходе списка, цикл 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/

1
  • Спасибо за подробное объяснение! 27 ноя 2016 в 15:51
7

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

Когда вы удаляете 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 удалений.

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.