Python中高效统计字典嵌套列表中元素出现次数的教程

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

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

# 假设的低效实现思路，仅作说明，不推荐
new_dict = {}
for key, values in my_dict.items(): # 外层循环1：遍历my_dict的键值对
    count_for_key = 0
    for list_val in values: # 内层循环2：遍历my_dict值中的列表元素
        for element in my_list: # 最内层循环3：遍历my_list
            if element == list_val:
                count_for_key += 1
    new_dict[key] = count_for_key

# 另一种低效实现思路，使用 `in` 操作符
new_dict = {}
for key, values in my_dict.items(): # 遍历my_dict的键值对
    new_dict[key] = 0
    for val_in_dict_list in values: # 遍历my_dict值中的列表元素
        # 此处隐藏了一个遍历：list_val in my_list
        # Python的 `in` 运算符对于列表的性能是 O(N)，N是列表长度
        new_dict[key] += my_list.count(val_in_dict_list) # my_list.count() 也是 O(N)

def count_nested_values(my_dict: dict, my_list: list) -> dict:
    """
    高效统计字典值中嵌套列表元素在主列表中出现次数的函数。

    参数:
    my_dict (dict): 键为字符串，值为字符串列表的字典。
    my_list (list): 包含字符串的主列表。

    返回:
    dict: 新字典，键为my_dict的键，值为对应元素在my_list中的总出现次数。
    """
    # 步骤1: 预处理 my_list，计算每个元素的出现次数
    # 使用字典存储，查找效率为 O(1)
    counts = {}
    for list_val in my_list:
        if list_val in counts:
            counts[list_val] += 1
        else:
            counts[list_val] = 1
    # 这一步的时间复杂度是 O(len(my_list))

    # 步骤2 & 3: 遍历 my_dict 并累加计数
    new_dict = {}
    for k, dict_val_list in my_dict.items():
        new_dict[k] = 0  # 初始化当前键的计数

        # 遍历 my_dict 值中的每个元素
        for item_in_dict_list in dict_val_list:
            # 在预处理的 counts 字典中查找元素出现次数
            # 字典查找是 O(1)
            if item_in_dict_list in counts:
                new_dict[k] += counts[item_in_dict_list]
            # 如果元素不在 counts 中，说明它在 my_list 中从未出现，计数为0，无需操作

    # 这一步的总时间复杂度是 O(len(my_dict) + 总的嵌套列表元素数量)
    # 因为遍历 my_dict 的键，然后遍历每个键对应的列表

    return new_dict

# 示例数据
my_dict = {'A': ['A', 'B'], 'B': ['C', 'D'], 'C': ['E', 'F']}
my_list = ['A', 'D', 'A', 'C', 'F', 'F']

# 调用函数并打印结果
result_dict = count_nested_values(my_dict, my_list)
print(result_dict)

from collections import Counter

def count_nested_values_with_counter(my_dict: dict, my_list: list) -> dict:
    """
    使用 collections.Counter 高效统计字典值中嵌套列表元素在主列表中出现次数的函数。
    """
    # 步骤1: 使用 Counter 预处理 my_list
    counts = Counter(my_list) # 这一步的时间复杂度是 O(len(my_list))

    new_dict = {}
    for k, dict_val_list in my_dict.items():
        current_key_total_count = 0
        for item_in_dict_list in dict_val_list:
            # Counter 对象可以直接通过键获取计数，如果键不存在则返回 0
            current_key_total_count += counts[item_in_dict_list]
        new_dict[k] = current_key_total_count

    return new_dict

# 示例数据
my_dict = {'A': ['A', 'B'], 'B': ['C', 'D'], 'C': ['E', 'F']}
my_list = ['A', 'D', 'A', 'C', 'F', 'F']

# 调用函数并打印结果
result_dict_counter = count_nested_values_with_counter(my_dict, my_list)
print(result_dict_counter)