Custom dict, который позволяет удалять во время итерации

Ответ 1

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

class dd_dict(dict):    # the dd is for "deferred delete"
    _deletes = None
    def __delitem__(self, key):
        if key not in self:
            raise KeyError(str(key))
        dict.__delitem__(self, key) if self._deletes is None else self._deletes.add(key)
    def __enter__(self):
        self._deletes = set()
    def __exit__(self, type, value, tb):
        for key in self._deletes:
            try:
                dict.__delitem__(self, key)
            except KeyError:
                pass
        self._deletes = None

Использование:

# make the dict and do whatever to it
ddd = dd_dict(a=1, b=2, c=3)

# now iterate over it, deferring deletes
with ddd:
    for k, v in ddd.iteritems():
        if k is "a":
            del ddd[k]
            print ddd     # shows that "a" is still there

print ddd                 # shows that "a" has been deleted

Если вы не находитесь в блоке with, конечно, удаление происходит немедленно; поскольку это подкласс dict, он работает так же, как обычный dict вне контекстного менеджера.

Вы также можете реализовать это как класс-оболочку для словаря:

class deferring_delete(object):
    def __init__(self, d):
        self._dict = d
    def __enter__(self):
        self._deletes = set()
        return self
    def __exit__(self, type, value, tb):
        for key in self._deletes:
            try:
                del self._dict[key]
            except KeyError:
                pass
        del self._deletes
    def __delitem__(self, key):
        if key not in self._dict:
            raise KeyError(str(key))
        self._deletes.add(key)

d = dict(a=1, b=2, c=3)

with deferring_delete(d) as dd:
    for k, v in d.iteritems():
        if k is "a":
            del dd[k]    # delete through wrapper

print d

Можно даже сделать класс-оболочку полноценным в качестве словаря, если вы хотите, хотя это справедливый бит больше кода.

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

Ответ 2

Что вам нужно сделать, так это не изменять список ключей, которые вы выполняете. Вы можете сделать это тремя способами:

• Сделайте копию ключей в отдельном списке и повторите это. Затем вы можете безопасно удалить ключи в словаре во время итерации. Это самый простой и быстрый, если словарь не является огромным, и в этом случае вы должны начать думать о использовании базы данных в любом случае. Код:

  for k in list(dict_):
    if condition(k, dict_[k]):
      del dict_[k]
      continue
    # do other things you need to do in this loop
  

• Сделайте копию не из ключей, которые вы выполняете, но копируете ключи, которые вы должны удалить. Другими словами, не удаляйте эти ключи, итерации вместо этого добавляйте их в список, а затем удаляйте ключи в этом списке после завершения итерации. Это немного сложнее, чем 1. но намного меньше 3. Это также быстро. Это то, что вы делаете в первом примере.

  delete_these = []
  for k in dict_:
    if condition(k, dict_[k]):
      delete_these.append(k)
      continue
    # do other things you need to do in this loop
  
  for k in delete_these:
      del dict_[k]
  

• Единственный способ избежать создания какого-либо нового списка - это, как вы полагаете, сделать специальный словарь. Но это требует, когда вы удаляете ключи, он фактически не удаляет ключи, но только помечайте их как удаленные, а затем удалите их по-настоящему только после вызова метода очистки. Для этого требуется довольно большая реализация, и есть крайние случаи, и вы помыслите себя, забыв очистить и т.д. Итерация по словарю должна по-прежнему включать удаленные ключи, которые вас укусят в какой-то момент. Поэтому я бы не рекомендовал этого. Кроме того, однако вы реализуете это в Python, вы, скорее всего, просто получите список вещей для удаления, поэтому он скорее всего будет сложной и подверженной ошибкам версией версии 2. Если вы реализовать его на C, вы, вероятно, могли бы уйти с копированием, добавив флаги непосредственно в структуру хэш-ключа. Но, как уже упоминалось, проблемы действительно затмевают преимущества.

Ответ 3

Вы можете выполнить это путем итерации по статическому списку пар ключ/значение словаря, а не итерации над представлением словаря.

В принципе, будет выполняться итерация list(dict_.items()) вместо dict_.items():

for k, v in list(dict_.items()):
  if condition(k, v):
    del dict_[k]
    continue
  # do other things you need to do in this loop

Вот пример (ideone):

dict_ = {0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f', 6: 'g'}
for k, v in list(dict_.items()):
    if k % 2 == 0:
        print("Deleting  ", (k, v))
        del dict_[k]
        continue
    print("Processing", (k, v))

и вывод:

Deleting   (0, 'a')
Processing (1, 'b')
Deleting   (2, 'c')
Processing (3, 'd')
Deleting   (4, 'e')
Processing (5, 'f')
Deleting   (6, 'g')

Ответ 4

Наивная реализация для Python 2.x и 3.x:

import sys
from collections import deque


def _protect_from_delete(func):
    def wrapper(self, *args, **kwargs):
        try:
            self._iterating += 1
            for item in func(self, *args, **kwargs):
                yield item
        finally:
            self._iterating -= 1
            self._delete_pending()
    return wrapper

class DeletableDict(dict):
    def __init__(self, *args, **kwargs):
        super(DeletableDict, self).__init__(*args, **kwargs)
        self._keys_to_delete = deque()
        self._iterating = 0

    if sys.version_info[0] != 3:
        iterkeys = _protect_from_delete(dict.iterkeys)
        itervalues = _protect_from_delete(dict.itervalues)
        iteritems = _protect_from_delete(dict.iteritems)
    else:
        keys = _protect_from_delete(dict.keys)
        values = _protect_from_delete(dict.values)
        items = _protect_from_delete(dict.items)  
    __iter__ = _protect_from_delete(dict.__iter__)

    def __delitem__(self, key):
        if not self._iterating:
            return super(DeletableDict, self).__delitem__(key)
        self._keys_to_delete.append(key)

    def _delete_pending(self):
        for key in self._keys_to_delete:
            super(DeletableDict, self).__delitem__(key)
        self._keys_to_delete.clear()

if __name__ == '__main__':
    dct = DeletableDict((i, i*2) for i in range(15))
    if sys.version_info[0] != 3:
        for k, v in dct.iteritems():
            if k < 5:
                del dct[k]
        print(dct)
        for k in dct.iterkeys():
            if k > 8:
                del dct[k]
        print(dct)
        for k in dct:
            if k < 8:
                del dct[k]
        print(dct)
    else:
        for k, v in dct.items():
            if k < 5:
                del dct[k]
        print(dct)

При итерации по клавишам, элементам или значениям устанавливается флаг self._iterating. В __delitem__ он проверяет возможность удаления элемента и сохраняет ключи во временной очереди. В конце итераций он удаляет все отложенные ключи.

Это очень наивная реализация, и я бы не рекомендовал ее использовать в производственном коде.

ИЗМЕНИТЬ

Добавлена ​​поддержка Python 3 и улучшения из @jsbueno комментариев.

Python 3 работает на Ideone.com

Ответ 5

Python 3.2 имеет такой dict в stdlib:

#!/usr/bin/env python3
from collections import OrderedDict as odict

d = odict(zip(range(3), "abc"))
print(d)
for k in d:
    if k == 2:
       del d[k]
print(d)

Выход

OrderedDict([(0, 'a'), (1, 'b'), (2, 'c')])
OrderedDict([(0, 'a'), (1, 'b')])

Итерация выполняется по связанному списку, см. __iter__() реализация метода. Удаление безопасно (в Python 3.2), хотя элементы являются слабыми ссылками.

Ответ 6

• Вы можете сделать копию списка ключей (вам не нужно копировать те значения) в начале итерации и перебрать их (проверяя, что ключ есть). Это неэффективно, если имеется много ключей.
• Вы можете организовать встроенный код первого примера внутри класса. __iter__ и __delitem__, а другие специальные методы должны сотрудничать, чтобы сохранить список элементов, которые нужно удалить во время итерации. Когда нет текущих итераций, __delitem__ может просто удалить элемент, но когда происходит хотя бы одна итерация, он должен просто добавить ключ, который нужно удалить в список. Когда последняя активная итерация заканчивается, она должна фактически удалить вещи. Это несколько неэффективно, если есть много ключей для удаления и, конечно, взорвется, если будет продолжаться хотя бы одна итерация.

Ответ 7

Это может работать как компромисс между двумя примерами - две строки длиннее второй, но короче и немного быстрее, чем первая. Python 2:

dict_ = {k : random.randint(0, 40000) for k in range(0,200000)}

dict_remove = [k for k,v in dict_.iteritems() if v < 3000]
for k in dict_remove:
    del dict_[k]

Разделить на функцию и до одной строки каждый вызов (независимо от того, является ли это более читаемым или нет вашим вызовом):

def dict_remove(dict_, keys):
    for k in keys:
        del dict_[k]

dict_remove(dict_, [k for k,v in dict_.iteritems() if v < 3000])

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