面试题：Python函数返回字典：动态生成与性能优化

Question

设计一个Python函数，该函数接受一个复杂的数据结构，可能是多层嵌套的字典、列表或元组。函数需要遍历这个数据结构，提取出所有叶子节点（即不再包含嵌套结构的值），并根据叶子节点的值动态生成一个字典。字典的键是叶子节点值的类型（用type函数获取），值是一个列表，包含所有该类型的叶子节点值。此外，要考虑函数的性能优化，避免重复计算和不必要的内存占用。请说明你的设计思路，并编写实现代码。

Answer 1

设计思路

1. 遍历数据结构：使用递归方法来遍历多层嵌套的字典、列表或元组。这样可以处理任意深度的嵌套结构。
2. 判断叶子节点：当遇到不再是字典、列表或元组的元素时，认为它是叶子节点。
3. 动态生成字典：使用一个字典来存储结果，键是叶子节点值的类型，值是包含该类型叶子节点值的列表。
4. 性能优化：
   • 避免重复计算：在递归过程中，每次处理的数据都是新的子结构，没有重复计算。
   • 减少不必要的内存占用：在递归过程中，只在找到叶子节点时才将其添加到结果字典中，不会存储中间过程的大量数据。

实现代码

def extract_leaf_nodes(data):
    result = {}
    def recursive_traverse(sub_data):
        if isinstance(sub_data, dict):
            for value in sub_data.values():
                recursive_traverse(value)
        elif isinstance(sub_data, (list, tuple)):
            for item in sub_data:
                recursive_traverse(item)
        else:
            data_type = type(sub_data)
            if data_type not in result:
                result[data_type] = []
            result[data_type].append(sub_data)
    recursive_traverse(data)
    return result