Python 字典推导式很慢

Question

我有一个字典 d1 和一个列表 l1。

字典的键是字符串，值是我自己定义的对象。如果需要，我可以更详细地描述这个对象，但现在对象具有列表属性 names，并且name 的一些元素可能会出现或不出现在l1中。

我想做的是丢弃字典d1中的任何元素，其中说过的元素的对象的name属性不包含在l1中出现的任何元素中。

以一个简单的例子为例：

l1 = ['cat', 'dog', 'mouse', 'horse', 'elephant', 
      'zebra', 'lion', 'snake', 'fly']

d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'],
      '2':['apple', 'pear','cat', 'mouse', 'horse'], 
      '3':['kiwi', 'lime','cat', 'dog', 'mouse'], 
      '4':['carrot','potato','cat', 'dog', 'horse'], 
      '5':['chair', 'table', 'knife']}

所以，结果字典大体相同，但是每个列表的元素将是从1到4（不包括水果和蔬菜）的键值对，并且不会包含第五个键值对，因为l1中没有家具值。 为此，我使用了嵌套的列表/字典推导式，如下所示：

d2 = {k: [a for a in l1 if a in d1[k]] for k in d1.keys()}
print(d2)

>>>>{'1': ['dog', 'mouse', 'horse'], 
     '3': ['cat', 'dog', 'mouse'], 
     '2': ['cat', 'mouse', 'horse'], 
     '5': [], 
     '4': ['cat', 'dog', 'horse']}

d2 = {k: v for k,v in d2.iteritems() if len(v)>0}
print(d2)

>>>>{'1': ['dog', 'mouse', 'horse'], 
     '3': ['cat', 'dog', 'mouse'], 
     '2': ['cat', 'mouse', 'horse'],  
     '4': ['cat', 'dog', 'horse'],}

这个方法似乎是有效的，但对于大型字典（7000+条目），需要大约20秒才能完成。这本身并不可怕，但我需要在一个循环内执行此操作，该循环将迭代10000次，因此目前不可行。有什么快速实现的建议吗？

- Davy Kavanagh

---

注意：他使用的是Python 2.7而不是3，因为使用了itertitems，不要被print()所迷惑。 - jamylak

Python 2.7 有字典推导式吗？ - Claudiu

@Claudiu 是的，它们已经被回溯了。 - jamylak

为提供完全可复制的示例点赞 +1。 - soulcheck

这个程序运行缓慢有几个原因，首先是对于像 for k in d1 这样可以迭代的字典。默认情况下，字典会按键进行迭代，在 Python 2.7 中，dict.keys 返回一个列表。另一个原因是你正在检查一个列表的成员资格，你永远不想这样做，因为它的运行时间是 O(N)。然而，检查一个集合的成员资格只需要 O(1) 的时间。 - jamylak

非常感谢大家的帮助，回应非常热烈。这里有很多尝试的事情。我将首先将所有列表更改为集合。从其他语言带来的坏习惯真的会阻碍你的发展。该死的R！ - Davy Kavanagh

Answer 1

你实际上正在计算字典值中出现的每个列表与列表 l1 的交集。使用列表进行交集运算相对低效，因为涉及线性搜索。你应该将 l1 转换为集合并使用 set.intersection() 或集合成员测试代替（取决于结果是否可再次为集合）。

完整代码可能如下所示：

l1 = set(l1)
d2 = {k: [s for s in v if s in l1] for k, v in d1.iteritems()}
d2 = {k: v for k, v in d2.iteritems() if v}

不必使用两个字典推导，这里也可以使用单个for循环更好:

l1 = set(l1)
d2 = {}
for k, v in d1.iteritems():
    v = [s for s in v if s in l1]
    if v:
        d2[k] = v

- Jolly Jumper

---

为了达到最高效率，我会将你的第一段代码改为 `>>> d2 = ((k, [s for s in v if s in l1]) for k, v in d1.iteritems())

d2 = {k: v for k, v in d2 if v}`。

- jamylak

@jamylak: 你认为这比for循环明显更快吗？我个人认为它至少明显更丑陋。 :) - Jolly Jumper

它将比您目前的第一个代码更有效，因为它不会再次运行d2。对于第二个，不太确定，需要使用“timeit”进行测试。 - jamylak

Answer 2

问题不在于字典推导式，而是其中嵌套的列表推导式。每次迭代都会遍历相同的键。这种情况最好使用集合来处理。

s1 = set(l1)
d2 = {k: list(s1.intersection(v)) for k, v in d1.items()}

- Daniel Roseman

---

为了提高效率，请使用 iteritems。 - jamylak

如果允许d1和d2中的值为集合，则效率会更高。 - Steven Rumbalski

Answer 3

l1 = ['cat', 'dog', 'mouse', 'horse', 'elephant', 
      'zebra', 'lion', 'snake', 'fly']

d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'],
      '2':['apple', 'pear','cat', 'mouse', 'horse'], 
      '3':['kiwi', 'lime','cat', 'dog', 'mouse'], 
      '4':['carrot','potato','cat', 'dog', 'horse'], 
      '5':['chair', 'table', 'knife']}

def gen_items(valid_name_set, d):
    for k, v in d.iteritems():
        intersection = valid_name_set.intersection(v)
        if intersection: # not empty
            yield (k, intersection)

print dict(gen_items(set(l1), d1))

输出：

{'1': set(['dog', 'horse', 'mouse']),
 '2': set(['cat', 'horse', 'mouse']),
 '3': set(['cat', 'dog', 'mouse']),
 '4': set(['cat', 'dog', 'horse'])}

或者：

from itertools import ifilter
from operator import itemgetter
set_l1 = set(l1)
d2 = dict(ifilter(itemgetter(1), 
                  ((k, set_l1.intersection(v)) for k, v in d1.iteritems())))

- jamylak

Answer 4

使用 set：

>>> l1 = ['cat', 'dog', 'mouse', 'horse', 'elephant',
      'zebra', 'lion', 'snake', 'fly']
>>> d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'],
      '2':['apple', 'pear','cat', 'mouse', 'horse'],
      '3':['kiwi', 'lime','cat', 'dog', 'mouse'],
      '4':['carrot','potato','cat', 'dog', 'horse'],
      '5':['chair', 'table', 'knife']}
>>> l1_set = set(l1)
>>> d2 = dict((k, set(d1[k]) & l1_set) for k in d1.keys())
>>> d2
{'1': set(['horse', 'mouse', 'dog']), '3': set(['mouse', 'dog', 'cat']), '2': set(['horse', 'mouse', 'cat']), '5': set([]), '4': set(['horse', 'dog', 'cat'])}
>>> d2 = dict((k, v) for k,v in d2.iteritems() if v)
>>> d2
{'1': set(['horse', 'mouse', 'dog']), '3': set(['mouse', 'dog', 'cat']), '2': set(['horse', 'mouse', 'cat']), '4': set(['horse', 'dog', 'cat'])}

- Claudiu

Answer 5

如果你将l1转换为一个set并略微修改字典推导式，你可以使其速度大约快三倍：

l1 = set(['cat', 'dog', 'mouse', 'horse', 'elephant', 
      'zebra', 'lion', 'snake', 'fly'])

d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'],
      '2':['apple', 'pear','cat', 'mouse', 'horse'], 
      '3':['kiwi', 'lime','cat', 'dog', 'mouse'], 
      '4':['carrot','potato','cat', 'dog', 'horse'], 
      '5':['chair', 'table', 'knife']}

d2 = {k: [a for a in d1[k] if a in l1] for k in d1.keys()}
print(d2)

以下是如何对性能进行基准测试的方法：

import timeit

t = timeit.Timer(
    "d2 = {k: [a for a in l1 if a in d1[k]] for k in d1.keys()}",
    "from __main__ import (d1, l1)",
    )
print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)

t = timeit.Timer(
    'd2 = {k: [a for a in d1[k] if a in l1] for k in d1.keys()}',
    "from __main__ import (d1, l1)",
    )
print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)

我在这里假设您无法控制 d1，并且在过滤之前将 d1 的所有值转换为集合的操作速度太慢。

- Daniel Nouri