14

我有一本字典d1和一个清单l1。

字典键是字符串，值是我自己定义的对象。如果有帮助，我可以更详细地描述 Object 但现在，这些对象有一个 list 属性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排除水果和蔬菜，并且不会包含第 5 个键值对，因为没有家具值出现在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 秒才能完成。就其本身而言，并不可怕，但我需要在一个循环中执行此操作，该循环将迭代 10,000 次，因此目前它不可行。关于如何快速做到这一点的任何建议？

4

5 回答 5

14

您正在有效地计算字典值中出现的每个列表与 list 的集合交集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
于 2012-08-10T14:08:51.847 回答
4

问题不是字典理解，而是其中的嵌套列表理解。您每次都在迭代相同的键。这种事情最好用套装来完成。

s1 = set(l1)
d2 = {k: list(s1.intersection(v)) for k, v in d1.items()}
于 2012-08-10T14:11:43.480 回答
1 
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())))
于 2012-08-10T14:27:56.200 回答
0

使用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'])}
于 2012-08-10T14:12:34.353 回答
0

如果你转换l1为 aset并稍微修改 dict 理解，你可以让它工作大约快三倍：

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为集合太慢了。

于 2012-08-10T14:17:41.350 回答