从列表中计算某个键的值的数量

Question

我有一个字典，其中键对应一个列表作为值。我想创建一个新的字典，它将存储原始字典的键，但其值是与 my_list 相关联的字母出现次数。例如，如果键 'A' 对应值为 'A' 和 'B'，那么我希望统计在 my_list 中找到的 'A' 或 'B' 的数量。

另外，我还想了解如何使用纯Python（即不使用列表推导式）通过嵌套循环来实现这一目标，因为我看到有些人使用了以下代码：

new_dict = [my_dict[x] for x in my_list if x in my_dict]

这段代码我并未完全理解透彻。希望我已经表达清楚了我的需求。

my_dict = {'A': ['A', 'B'], 'B': ['C', 'D'], 'C': ['E', 'F']}
my_list = ['A', 'D', 'A', 'C', 'F', 'F']
new_dict = {}

期望输出：

{'A': 2, 'B': 2, 'C': 2}

由于键 'A' 对应的值为 'A' 和 'B'，而在 my_list 中仅有两个 'A' 出现且没有 'B'，所以在这种情况下，计数结果为2，这就是键 'A' 在新字典中的值。

new_dict = [my_dict[x] for x in my_list if x in my_dict]

并且我尝试过使用嵌套循环来解决这个问题，但是在处理嵌套循环时遇到了困难。

Nathan Fellman · Answer

你可以预先使用 Counter来获取元素的出现次数，这样就不必在每次循环中都计算每个元素的计数；只需查询已计算好的计数即可。

from collections import Counter

# 计算my_list中所有元素的出现次数
counts = Counter(my_list)

# 根据my_dict的键值对构建新的字典，键不变，值为相应列表中元素在my_list中出现次数之和
new_dict = {k: sum(counts[e] for e in v) for k, v in my_dict.items()}

# 输出结果：
# {'A': 2, 'B': 2, 'C': 2}

Ferruccio · Answer

使用嵌套循环和计数变量的方法：

for key, values in my_dict.items():  # 遍历原字典中的每一对键值
    count = 0  # 初始化计数器为0
    for element in my_list:  # 遍历列表中的每一个元素
        if element in values:  # 如果列表中的元素存在于当前键对应的值列表中
            count += 1  # 计数器加1
    new_dict[key] = count  # 当完成对当前键对应的列表中元素的计数后，将计数值存入新字典中对应的键下

Alnitak · Answer

这里有一个替代解决方案，它既不使用Counter库，也避免了上述嵌套循环。该解决方案通过使用字典作为中间数据结构提高了时间性能，代价是需要额外的内存来存储该字典以换取时间效率的提升（具体取决于您更看重哪一点）。显然，这个方案在代码实现上更为详尽。

def count_nested_values(my_dict: dict, my_list: list):
    counts = {}
    for list_val in my_list:
        if list_val in counts:
            counts[list_val] += 1
        else:
            counts[list_val] = 1

    new_dict = {}
    for k, dict_val in my_dict.items():
        new_dict[k] = 0

        # the following loop could be shortened to this line with
        # list comprehension, a ternary, and sum()
        # new_dict[k] = sum(counts[v] if v in counts else 0 for v in dict_val)
        for list_val in dict_val:
            if list_val in counts:
                new_dict[k] += counts[list_val]

    return new_dict

我想强调的是，这个方法其实与wjandrea在上面提供的解决方案本质上相同，只是将Counter库以及字典推导式替换为了中间字典和循环。这样做有什么好处呢？

在你的解决方案中，你对my_dict中的每个键执行了循环for element in my_list，这意味着你在多次不必要的重复处理这些值。另外，在Python中，对于列表来说，使用in运算符的时间复杂度为O(n)，而对于字典和集合则是O(1)。因此，当你执行element in values时，你会针对my_list中的每一个元素重新遍历每一个values列表。

总的来说，这会导致O(n³)的性能表现，通常这是不可取的。其时间复杂度的计算因素如下：

外层循环：my_dict中的键的数量
内层循环：my_list中的值的数量
if块中的in表达式：嵌套列表中值的数量（对于my_dict中的每一对键值，嵌套列表大小可能会变化，所以它会随着最大的值列表规模而扩展）

因此，总的迭代次数将是(my_dict中的键数) * (my_list中的值数) * (嵌套列表中的值数)。在给定的输入示例中，它是3 * 6 * 2 = 36次迭代。

Counter方案以及我上面提到的解决方案通过以下算法改进了性能：

预处理my_list以统计my_list中每个值出现的次数——生成Counter对象或构建普通的counts字典的第一层循环。由于字典读写操作是常数时间O(1)，预处理的成本是O(n)，其中n是my_list的大小。
遍历my_dict中的键值对，通过my_dict.items()实现——在Counter解决方案中是字典推导式的可迭代部分，在我的方案中是第二个循环。这一遍历的成本是O(n)，其中n是my_dict中键的数量，因此到目前为止，我们的解决方案总体上是O(n)，其中n是my_list的大小或my_dict中键的数量，取两者较大者。
对于my_dict中的每一组键值对，遍历嵌套的列表值——在Counter解决方案中作为sum()函数的输入，在我的方案中是第二层循环内的嵌套循环。这意味着，包括嵌套循环在内的第二层循环的整体迭代次数现在是my_dict中的嵌套值总数。因此，现在我们算法的总体性能是O(n)，其中n是my_list的大小或my_dict中的嵌套值数量，取两者较大者。
必须在counts字典中查找嵌套值以避免KeyError。由于counts是一个字典，查找示例的时间复杂度为O(1)，所以不会影响整体效率。

综上所述，最终的性能优化为O(n)，而不是O(n³)。

总之，如果你不在乎解决方案的时间效率——比如你知道输入永远不会很大——那么你的解决方案是正确的，并且能够完成任务。但如果你关心解决方案的性能或者出于教育目的，这种实现方式会更加高效一些，同时也大致展示了Counter解决方案背后的原理（尽管可能在那里还有进一步的优化）。