Removing from a list while iterating over it

Следующий код:

a = list(range(10))
remove = False
for b in a:
    if remove:
        a.remove(b)
    remove = not remove
print(a)

Выводит [0, 2, 3, 5, 6, 8, 9]вместо [0, 2, 4, 6, 8] при использовании Python 3.2.

1. Почему он выводит именно эти значения?


2. Почему не выдается ошибка, указывающая на изменение базового итератора?


3. Изменилась ли механика по сравнению с более ранними версиями Python в отношении такого поведения?

Обратите внимание, что я не пытаюсь обойти поведение, а пытаюсь понять его.

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

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]       <-  b = 0; remove? no
 ^
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]       <-  b = 1; remove? yes
    ^
[0, 2, 3, 4, 5, 6, 7, 8, 9]          <-  b = 3; remove? no
       ^
[0, 2, 3, 4, 5, 6, 7, 8, 9]          <-  b = 4; remove? yes
          ^
[0, 2, 3, 5, 6, 7, 8, 9]             <-  b = 6; remove? no
             ^
[0, 2, 3, 5, 6, 7, 8, 9]             <-  b = 7; remove? yes
                ^
[0, 2, 3, 5, 6, 8, 9]                <-  b = 9; remove? no
                   ^

Поскольку никто другой этого не делал, я попытаюсь ответить на другие ваши вопросы:

Почему не выдается ошибка, указывающая на изменение базового итератора?

Чтобы выдать ошибку, не запрещая множество совершенно допустимых конструкций циклов, Python должен был бы много знать о том, что происходит, и, вероятно, ему пришлось бы получать эту информацию во время выполнения. Для обработки всей этой информации потребовалось бы время. Это сделало бы Python намного медленнее, как раз в том месте, где скорость действительно важна - в цикле.

Изменилась ли механика по сравнению с более ранними версиями Python в отношении такого поведения?

Короче говоря, нет. Или, по крайней мере, я сильно сомневаюсь в этом, и, конечно, он ведет себя таким образом с тех пор, как я изучил Python (2.4). Честно говоря, я ожидал бы, что любая простая реализация изменяемой последовательности будет вести себя именно таким образом. Любой, кто знает лучше, пожалуйста, поправьте меня. (На самом деле, быстрый поиск в документе подтверждает, что текст, который цитировал Микола, был в руководстве с версии 1.4!)

Как объяснил Микола, фактический результат, который вы наблюдаете, вызван тем фактом, что удаление записи из списка сдвигает весь список на одно место, в результате чего вы пропускаете элементы.

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

1. Dict являются сложными внутренне, в то время как списки - нет. Списки по сути представляют собой просто массивы. dict должен определять, когда он изменяется во время итерации, чтобы избежать сбоя при изменении внутренней структуры dict. Список может быть удален без выполнения этой проверки, потому что он просто проверяет, что его текущий индекс все еще находится в диапазоне.




2. Исторически (сейчас я не уверен) списки python повторялись с помощью оператора []. Python будет оценивать list[0], list[1], list[2], пока не получит IndexError . В этом случае python не отслеживал размер списка до его начала, поэтому у него не было метода определения того, что размер списка был изменен.

Конечно, небезопасно изменять массив во время итерации по нему. В спецификации сказано, что это плохая идея, и поведение не определено:

http://docs.python.org/tutorial/controlflow.html#for-statements

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

for(int i=0; i<len(array); ++i)
{
   do_loop_body(i);
}

Если вы предполагаете, что это действительно то, что происходит, то это полностью объясняет наблюдаемое поведение. Когда вы удаляете элемент рядом с текущим указателем или перед ним, вы сдвигаете весь список на 1 влево. В первый раз вы удаляете 1 - как обычно, - но теперь список сдвигается в обратном направлении. На следующей итерации вместо 2 вы нажимаете 3. Затем вы удаляете 4, и список сдвигается в обратном направлении. Следующая итерация 7 и так далее.

Если вы добавите reversed() в цикл for, вы можете перемещаться по массиву в обратном направлении, удаляя элементы, и получить ожидаемый результат. Положение элемента в массиве зависит от предыдущих элементов, а не от следующих элементов:

Поэтому код:

a = list(range(10))
remove = True
for b in reversed(a):
    if remove:
        a.remove(b)
    remove = not remove
print(a)

производит ожидаемое: [0, 2, 4, 6, 8]