字典查找效率

Question

我有一个列表列表，我想向其中添加一个列表，其中包含基于查找的字典中的求和值。

下面的代码可以工作，但速度不够快，无法处理我拥有的数据量，所以问题是如何更有效地执行此操作。我正在使用 Python 2.7.

people = [
            [['A'], ['B']], 
            [['B'], ['A', 'C', 'E', 'D']], 
            [['C'], ['B']], 
            [['D'], ['B', 'E']], 
            [['E'], ['H', 'B', 'D']], 
            [['F']], 
            [['G']], 
            [['H'], ['E']], 
            [['I']]
        ]

 dollars = {'A': 575, 'B': 628, 'C': 693, 'D': 456, 'E': 1595, 'F': 1366, 'G': 1596, 'H': 2667, 'I': 2145}

我尝试了以下（变化）：

num_dos = 2 # a placeholder, will be user input

for groups in people:
    groups.append([])
    for i in range(min(len(groups), num_dos)):
        groups[-1].extend([v for k, v in dollars.items() if k in groups[i]])
    groups[-1] = sum(groups[-1])   

people.sort(key = lambda x: x[-1], reverse = True)

给出了想要的结果：

[
    [['E'], ['H', 'B', 'D'], 5346], 
    [['H'], ['E'], 4262], 
    [['B'], ['A', 'C', 'E', 'D'], 3947], 
    [['D'], ['B', 'E'], 2679], 
    [['I'], 2145], 
    [['G'], 1596], 
    [['F'], 1366], 
    [['C'], ['B'], 1321], 
    [['A'], ['B'], 1203]
]

Answer 1

与其迭代字典中的项目并测试它们是否在列表中，您应该以相反的方式进行：迭代列表中的项目并从字典中获取它们的值（如果有的话）。这样，它要快得多，因为在列表中查找是 O(n)，而它更像是在字典中的 O(1)。此外，似乎不需要所有这些中间数字列表；只需将总和添加到最后的列表即可。

for groups in people:
    s = 0
    for i in range(min(len(groups), num_dos)):
        s += sum(dollars.get(x, 0) for x in groups[i])
    groups.append(s)

字典查找效率

Dictionary lookup efficiency

python

optimization

dictionary

lookup