python - 允许在迭代期间删除的自定义字典

Question

根据 Lennart Regebro 的回答更新

假设你遍历一个字典，有时需要删除一个元素。以下是非常有效的:

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

这里唯一的开销是构建要删除的键列表；除非它与字典大小相比变大，否则这不是问题。但是，这种方法需要一些额外的编码，所以不是很流行。

流行的字典理解方法:

dict_ = {k : v for k, v in dict_ if not condition(k, v)}
for k, v in dict_.items():
  # do other things you need to do in this loop

会产生完整的字典副本，因此如果字典变大或经常调用包含函数，则可能会出现愚蠢的性能损失。

更好的方法是只复制键而不是整个字典:

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

(请注意，所有代码示例都在 Python 3 中，因此 keys()、items() 返回的是 View ，而不是副本。)

在大多数情况下，它不会对性能造成太大影响，因为检查最简单的条件(更不用说您在循环中执行的其他操作)的时间通常比添加一个键的时间要长一个列表。

不过，我想知道是否可以使用允许在迭代时删除的自定义字典来避免这种情况:

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

也许迭代器总是可以向前看，这样当 __next__ 被调用时，迭代器甚至不用看当前元素就知道去哪里(它只需要在它首先到达它)。如果没有下一个元素，迭代器可以设置一个标志，当再次调用 __next__ 时会引发 StopIteration 异常。

如果迭代器尝试前进的元素被删除，则可以引发异常；当多个迭代同时进行时，不需要支持删除。

这种方法有什么问题吗？

一个问题是，与现有的 dict 相比，我不确定它是否可以在没有 Material 开销的情况下完成；否则，使用 list(dict_) 方法会更快!

更新:

我尝试了所有版本。我没有报告时间，因为它们显然非常依赖于确切的情况。但可以肯定地说，在许多情况下，最快的方法可能是 list(dict_)。毕竟，如果你想一想，复制是最快的操作，它会随着列表的大小线性增长；几乎任何其他开销，只要它也与列表大小成正比，都可能更大。

我真的很喜欢所有的想法，但由于我只能选择一个，我接受上下文管理器解决方案，因为它允许使用字典作为正常或“增强”，只需非常小的代码更改。

Answer 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 block 中，当然，删除是立即的；由于这是一个 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

如果您愿意，甚至可以将包装类完全用作字典，尽管这需要更多代码。

在性能方面，诚然这不是一场胜利，但从程序员友好的角度来看，我喜欢它。第二种方法应该会稍微快一些，因为它不会在每次删除时测试一个标志。