Почему изменение dict во время итерации не всегда вызывает исключение?

Question

Удаление элемента из во время прохода через него, как правило, приводит к RuntimeError: dictionary changed size during iteration исключения:

d = {1: 2} 
# exception raised 
for k in d: 
    del d[k] 

Чтобы быть более точным, то само удаление будет успешным. Однако, чтобы ввести следующий раунд итерации, интерпретатор должен вызвать next(it), где it является итератором через словарь, полученный ранее. В этот момент next() заметят, что размер словаря изменился и жалуются.

Пока все хорошо. Но что, если мы оба удалить и добавить элемент в словарь:

d = {1: 1} 
# no exception raised 
for k in d: 
    # order of next two lines doesn't matter 
    d[k*10] = k*10 
    del d[k] 

Я почти уверен, что это не безопасно (Документы подразумевают ни вставки не стирают допускаются в течение итерации). Почему интерпретатор разрешает запуск этого кода без ошибок?

Мое единственное предположение, что слишком дорого проверять, какие итераторы являются недействительными всякий раз, когда вызывается метод вставки или удаления. Таким образом, dict не пытается быть идеальным в том, чтобы поднимать это исключение. Вместо этого он просто отслеживает размер словаря внутри каждого итератора и проверяет, что он не изменился всякий раз, когда итератору на самом деле предлагается перейти к следующему элементу. Нет ли такого подхода, который позволил бы провести полную проверку с низкой стоимостью?

Answer 1

Нет ли подхода, который позволил бы провести полную проверку по низкой цене?

comment from Alex Martelli по теме.

because a container doesn't even keep track of iterators that are out on it, much less hook even altering-method to loop over every such iterator and somehow magically let each iterator know about the alterations. It would be a lot subtle, complex code, and checks slowing down very frequent operations

Таким образом, по крайней мере, согласно ядру Python dev, мы не можем иметь полную проверку при низкой стоимости.

Answer 2

Самый простой ответ, потому что вы удалить 1 пункт и добавить 1 пункт поэтому тот факт, что размер изменился на самом деле не никогда попадается; RuntimeError возникает, когда существует разница между размером итератора и словаря для этого итератора:

if (di->di_used != d->ma_used) { 
    PyErr_SetString(PyExc_RuntimeError, 
        "dictionary changed size during iteration"); 
    di->di_used = -1; /* Make this state sticky */ 
    return NULL; 
} 

когда вы добавляете один и удалить один, di->di_used остается неизменным на d->ma_used (который получает приращение на единицу и уменьшается на единицу). Операции (del и добавление ключа) выполняются на объекте dictd, и из-за баланса этих операций в предыдущем if не было обнаружено несоответствия.

Но, если добавить две клавиши, к примеру, вы получите ту же ошибку:

d = {1: 1} 
for k in d: 
    del d[k] 
    d[1] = 1 
    d[2] = 2 

RuntimeErrorTraceback (most recent call last) 
<ipython-input-113-462571d7e0df> in <module>() 
     1 d = {1: 1} 
     2 # no exception raised 
----> 3 for k in d: 
     4 # order of next two lines doesn't matter 
     5 del d[k] 

RuntimeError: dictionary changed size during iteration 

потому понимая, что размер изменился ловится здесь. Если, конечно, вы уменьшаетесь дважды, происходит такое же поведение, как и раньше, оно уравновешивается.

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

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

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

Как взрослые, мы должны понимать, что Python не должен проверять все для нас и вместо этого просто не делать ничего, когда они знают нежелательные эффекты.

Answer 3

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

Этот код будет делать это. Использование SafeDict или его keys()/items()/values() прокси, петли становятся безопасными от случайного вставки/удаления:

class SafeKeyIter: 
    def __init__(self, iterator, container): 
     self.iterator = iterator 
     self.container = container 
     try: 
      self.n_modifications = container.n_modifications 
     except AttributeError: 
      raise RuntimeError('container does not support safe iteration') 

    def __next__(self): 
     if self.n_modifications != self.container.n_modifications: 
      raise RuntimeError('container modified duration iteration') 
     return next(self.iterator) 

    def __iter__(self): 
     return self 


class SafeView: 
    def __init__(self, view, container): 
     self.view = view 
     self.container = container 

    def __iter__(self): 
     return SafeKeyIter(self.view.__iter__(), self.container) 

class SafeDict(dict): 
    def __init__(self, *args, **kwargs): 
     self.n_modifications = 0 
     super().__init__(*args, **kwargs) 

    def __setitem__(self, key, value): 
     if key not in self: 
      self.n_modifications += 1 
     super().__setitem__(key, value) 

    def __delitem__(self, key): 
     self.n_modifications += 1 
     super().__delitem__(key) 

    def __iter__(self): 
     return SafeKeyIter(super().__iter__(), self) 

    def keys(self): 
     return SafeView(super().keys(), self) 

    def values(self): 
     return SafeView(super().values(), self) 

    def items(self): 
     return SafeView(super().items(), self) 

# this now raises RuntimeError: 
d = SafeDict({1: 2}) 
for k in d: 
    d[k * 100] = 100 
    del d[k] 

Это не кажется слишком дорогим, так что я не знаю, почему это не реализовано в CPython dict , Возможно, дополнительная стоимость обновления n_modifications на словаре была оценена слишком высоко.