从Counter中删除最不常见的元素

Question

如果值小于某个值，有没有"更快的方法"从Counter中删除键值对？

我做了以下工作：

counter_dict = {k:v for k, v in counter_dict.items() if v > 5}

Answer 1

当前代码的主要问题是对.items的调用，它将创建所有项目的列表：

一种优化可以是使用Counter.iteritems而不是.items，以节省创建列表并再次迭代的代价。

>>> from collections import Counter
>>> cnt = Counter("asbdasdbasdbadaasasdasadsa")
>>> {k:v for k,v in cnt.iteritems() if v > 5}
{'a': 10, 's': 7, 'd': 6}

另一个优化可以是不调用.items方法，而是迭代密钥并使用密钥访问值：

>>> from collections import Counter
>>> cnt = Counter("asbdasdbasdbadaasasdasadsa")
>>> {k:cnt[k] for k in cnt if cnt[k] > 5}
{'a': 10, 's': 7, 'd': 6}

---

如果我们试图在ipython中测量%timeit的差异，使用具有您提到的If条件的样本计数器，iteritems轻而易举地获胜:

In [1]: import random
In [2]: from collections import Counter
In [3]: MILLION = 10**6
In [4]: cnt = Counter(random.randint(0, MILLION) for _ in xrange(MILLION))
In [5]: %timeit {k:v for k, v in cnt.iteritems() if v < 5}
10 loops, best of 3: 140 ms per loop
In [6]: %timeit {k:v for k, v in cnt.items() if v**2 < 5}
1 loops, best of 3: 290 ms per loop
In [7]: %timeit {k:cnt[k] for k in cnt if cnt[k] < 5}
1 loops, best of 3: 272 ms per loop

随条件变化：

In [8]: %timeit {k:v for k, v in cnt.iteritems() if v > 5}
10 loops, best of 3: 87 ms per loop
In [9]: %timeit {k:v for k, v in cnt.items() if v > 5}
1 loops, best of 3: 186 ms per loop
In [10]: %timeit {k:cnt[k] for k in cnt if cnt[k] > 5}
10 loops, best of 3: 153 ms per loop

Answer 2

所以你最好不要每次都重新创建整个字典：

to_remove = set()
for key, value in counter_dict.viewitems():
   if value <= 5:
      to_remove.add(key)
for key in to_remove:
    del counter_dict[key]

将"for"语句展开成更多的行并不一定意味着更少的性能。尽管在这种情况下可能没有太大的性能提升，但内存消耗至少应该会下降。

另一种选择是让你的"counter_dict"成为一个更智能的对象知道当计数为<=时不产生其值5-那会让这一步变得"懒惰"。

正确的做法是实现使用ABC元类-集合。可变映射

class MyDict(dict):
   def __init__(*args, **kw):
       self.threshold = None
       super(MyDict,self).__init__(*args, **kw)
   def __getitem__(self, key):
       value = super(MyDict, self).__getitem__(key)
       if self.threshold is None or key > self.threshold:
          return value
       raise ItemError
   # the same for __contains__ and other interesting methods

当dict应该开始过滤时，您可以更改dict中的"threshold"属性对象。这或多或少有些过头了——因为你的检查仍然会完成，只是时间会被稀释——但在消费对象时，你可能处于异步/多线程工作负载上，可以并行进行——但如果你在代码的不同部分需要不同的阈值，这可能是一件好事。