通过递归处理复杂的嵌套数据结构——深度嵌套的性能问题

Question

我正在开发一个 Python 项目，需要处理嵌套数据结构。该结构由列表和字典组成，嵌套级别可以从几级到数百级不等。我需要将此数据结构展平为单个列表，同时保留值。但是，在处理深层嵌套时，我遇到了性能问题。

这是我正在使用的简化数据结构：

data = {
    "name": "John",
    "contacts": [
        {
            "type": "email",
            "value": "[email protected]",
        },
        {
            "type": "phone",
            "value": [
                {
                    "country": "US",
                    "number": "123-456-7890"
                },
                {
                    "country": "UK",
                    "number": "987-654-3210"
                }
            ]
        }
    ],
    "address": {
        "city": "New York",
        "postal_code": "10001",
        "coordinates": [
            {
                "lat": 40.7128,
                "lon": -74.0060
            }
        ]
    }
}

我需要创建一个函数来展平此结构，以便将所有值提取到单个列表中。上述输入的输出类似于：

["John", "email", "[email protected]", "phone", "123-456-7890", "US", "987-654-3210", "UK", "New York", "10001", 40.7128, -74.0060]

我尝试过使用递归，但在处理非常深层的结构时遇到了问题。这是我最初的尝试：

def flatten(data):
    flat_list = []
    
    if isinstance(data, dict):
        for key, value in data.items():
            flat_list.extend(flatten(value))
    elif isinstance(data, list):
        for item in data:
            flat_list.extend(flatten(item))
    else:
        flat_list.append(data)
    
    return flat_list

flattened_data = flatten(data)
print(flattened_data)

这对于中小型结构来说效果很好，但是当嵌套更深（数百层深）时，我会遇到递归深度问题和性能瓶颈。

我尝试过的：

• 使用 sys.setrecursionlimit() 增加递归限制，但效果有限，并不能完全解决性能问题。
• 通过将递归函数转换为迭代方法来优化递归函数，但我不确定如何手动管理深层嵌套结构的递归。

问题：

1. 如何改进递归或重构此代码以有效处理更深层次的结构？
2. 是否有一种迭代方法可以扁平化此数据结构而不遇到递归深度限制？
3. 是否有任何已知的库或模式可以更有效地处理非常深入和复杂的数据结构

结构是动态的，可能并不总是遵循相同的模式（字典可能并不总是包含相同的键，列表可能并不总是包含相同类型的数据），因此函数应该尽可能通用。

Answer 1

首先，如果您的嵌套列表主要有 2 个条目，而字典主要有 2 个键，并且您的嵌套平均深度约为一百层，则您的值数量约为 2¹⁰⁰ ，即~10³⁰。即使我们只计算每个收集（叶）值的 4 个字节，这也代表着比当今计算机可以存储的容量还要多，甚至比撰写本文时整个互联网所能容纳的容量还要多。

要么你的嵌套并不是那么深，但你的程序会遭受无限递归，因为数据具有循环引用，或者你的层次结构真的很窄，其中长根到叶路径的数量不是那么深巨大的。

您可以通过使用生成器而不是收集列表中的所有值来避免一些分配。

如果调用堆栈的大小仍然是一个问题，即使您已确保数据没有循环引用，那么您始终可以选择迭代版本：

# helper function
def get_iterator(data):
    if isinstance(data, list):
        return iter(data)
    elif isinstance(data, dict):
        return iter(data.values())

def flatten(data):
    stack = [iter([data])]
    while stack:
        try:
            value = next(stack[-1])
            iterator = get_iterator(value)
            if iterator:
                stack.append(iterator)
            else:
                yield value
        except StopIteration:
            stack.pop()