自定义dict,允许在迭代期间删除

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__调用它时,迭代器知道去哪里甚至没有查看当前元素(它只需要在第一次到达它时查看元素).如果没有下一个元素,迭代器可以设置标志,StopIteration只要__next__再次调用就会引发异常.

如果迭代器尝试前进的元素结果被删除,那么引发异常就可以了; 在多次迭代同时进行时,不需要支持删除.

这种方法有什么问题吗？

一个问题是,与现有技术相比,我不确定它是否可以在没有任何实质性开销的情况下完成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. 在单独的列表中复制密钥并对其进行迭代.然后,您可以在迭代期间安全地删除字典中的键.这是最简单,最快速的,除非字典很大,在这种情况下你应该开始考虑在任何情况下使用数据库.码:

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

2. 复制不是您正在迭代的键,而是要删除的键的副本.换句话说,在迭代时不要删除这些键而是将它们添加到列表中,然后在完成迭代后删除该列表中的键.这比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]
   

3. 正如你的建议,避免制作某种新列表的唯一方法是制作一个特殊字典.但是,这需要在删除密钥时实际上不删除密钥,而只是将其标记为已删除,然后只有在调用清除方法后才将其删除.这需要相当多的实现,并且存在边缘情况,并且你将通过忘记清除等来捏造自己.并且迭代字典必须仍然包括已删除的密钥,这将在某些时候咬你.所以我不推荐这个.另外,无论你是用Python实现的,你都可能再一次得到一个要删除的东西列表,所以它可能只是一个复杂且容易出错的版本2.如果你用C实现它,你可以可能通过将标志直接添加到哈希键结构中来逃避复制.但如上所述,问题确实掩盖了这些好处.