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

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() 返回视图，而不是副本。）

在大多数情况下，它不会对性能造成太大影响，因为即使是检查最简单的条件（更不用说您在循环中执行的其他操作）的时间通常也比检查的时间长将一把钥匙添加到列表中。

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

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 相比，我不确定它是否可以在没有任何材料开销的情况下完成；否则，使用 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 块中，当然，删除是立即的；由于这是一个 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

如果您愿意，甚至可以使包装类完全发挥字典的功能，尽管这会增加相当多的代码。

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

Answer 2

您需要做的是不要修改您迭代的键列表。您可以通过三种方式执行此操作：

1. 在单独的列表中创建键的副本并对其进行迭代。然后，您可以在迭代期间安全地删除字典中的键。这是最简单、最快的，除非字典很大，在这种情况下您应该开始考虑在任何情况下使用数据库。代码：

   对于列表（dict_）中的 k：
     如果条件（k，dict_[k]）：
       删除 dict_[k]
       继续
     # 在这个循环中做你需要做的其他事情
   

2. 不要复制您正在迭代的键，而是复制要删除的键。换句话说，不要在迭代时删除这些键，而是将它们添加到列表中，然后在完成迭代后删除该列表中的键。这比 1. 稍微复杂一些，但比 3. 少得多。它也很快。这就是您在第一个示例中所做的事情。

   <前><代码>delete_these = []
   对于 dict_ 中的 k：
   如果条件（k，dict_[k]）：
   删除_这些.append(k)
   继续
   # 在这个循环中做你需要做的其他事情

   对于delete_these中的k：
   删除 dict_[k]

3. 避免创建某种新列表的唯一方法是，正如您所建议的，创建一个特殊的字典。但这要求当您删除键时，它实际上不会删除键，而只是删除键将它们标记为已删除，然后仅在调用清除方法后才真正删除它们。这需要大量的实现，并且存在边缘情况，您会因为忘记清除等而欺骗自己。并且迭代字典必须仍然包含已删除的键，这在某些时候会困扰您。所以我不会推荐这个。 此外，无论您如何在 Python 中实现此功能，您都可能会再次得到要删除的内容列表，因此它可能只是 2 的复杂且容易出错的版本。如果您在 C 中实现它，您可能可以通过将标志直接添加到散列键结构中来摆脱复制。但正如前面提到的，问题确实掩盖了好处。

Answer 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')

Answer 4

Python 3.2 在 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 中）项目是弱引用。

Answer 5

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._iteating。在 __delitem__ 中，它检查删除项目的能力，并将密钥存储在临时队列中。在迭代结束时，它会删除所有待处理的键。

这是非常幼稚的实现，我不建议在生产代码中使用它。

编辑

添加了对 Python 3 的支持以及 @jsbueno 评论的改进。

Python 3 在 Ideone.com 上运行

Answer 6

1. 您可以在迭代开始时复制键列表（不需要复制值），然后迭代这些键（检查键是否存在）。如果有很多键，这是低效的。
2. 您可以安排将第一个示例代码嵌入到类中。 __iter__ 和 __delitem__ 以及其他特殊方法需要协作以在迭代发生时保留要删除的项目列表。当没有当前迭代时，__delitem__ 可以只删除一项，但是当至少发生一次迭代时，它应该只将要删除的键添加到列表中。当最后一个活动迭代完成时，它实际上应该删除一些东西。如果有很多键需要删除，这有点低效，并且如果总是至少进行一次迭代，当然会崩溃。

Answer 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])

无论代码存储在哪里，您都必须将需要删除的键存储在某个地方。解决这个问题的唯一方法是使用生成器表达式，它会在您第一次删除键时爆炸。

Answer 8

略有不同的方法；有时删除被高估了。迭代时，您可以覆盖字典中的值并将其分配给 None。这不会“改变”整体结构，它只是将一个元素重新指向 None。这可以在迭代时安全地完成。如果确实必须，您可以随后删除 None（假设您以前从未存储过 None），或者只是让您的代码容忍检索 None就好像钥匙一开始就不存在一样。

这里的整个对话实际上围绕着字典的大小和要删除的元素的预期比例。对此持平态度，这些答案中提出的解决方案之一将是适合您的特定用例的“正确的解决方案”。