python - Handling complex nested data structures with recursion – performance issues with deep nesting - Stack Overflow

admin管理员组

文章数量:1122846

I’m working on a Python project where I need to process a nested data structure. The structure consists of lists and dictionaries, and the nesting level can vary from a few levels to potentially hundreds. I need to flatten this data structure into a single list while preserving the values. However, I am facing performance issues when dealing with deep nesting.

Here is the simplified data structure I’m working with:

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
            }
        ]
    }
}

I need to create a function that will flatten this structure such that all values are extracted into a single list. The output for the above input would look something like:

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

I’ve tried using recursion, but I’m running into issues with handling very deep structures. Here is my initial attempt:

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)

This works fine for small and medium-sized structures, but when the nesting gets deeper (hundreds of levels deep), I run into recursion depth issues and performance bottlenecks.

What I’ve Tried:

• Increasing the recursion limit with sys.setrecursionlimit() but it only marginally helps and doesn’t fully address the performance concerns.
• Optimizing the recursive function by converting it to an iterative approach, but I’m unsure how to manage the recursion manually for deeply nested structures.

Questions:

1. How can I improve the recursion or refactor this code to handle much deeper structures efficiently?
2. Is there an iterative way to flatten this data structure without running into recursion depth limitations?
3. Are there any known libraries or patterns that can handle very deep and complex data structures like this more efficiently

The structure is dynamic and may not always follow the same pattern (dictionaries may not always contain the same keys, lists may not always contain the same types of data), so the function should be as generic as possible.

I’m working on a Python project where I need to process a nested data structure. The structure consists of lists and dictionaries, and the nesting level can vary from a few levels to potentially hundreds. I need to flatten this data structure into a single list while preserving the values. However, I am facing performance issues when dealing with deep nesting.

Here is the simplified data structure I’m working with:

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
            }
        ]
    }
}

I need to create a function that will flatten this structure such that all values are extracted into a single list. The output for the above input would look something like:

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

I’ve tried using recursion, but I’m running into issues with handling very deep structures. Here is my initial attempt:

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)

This works fine for small and medium-sized structures, but when the nesting gets deeper (hundreds of levels deep), I run into recursion depth issues and performance bottlenecks.

What I’ve Tried:

• Increasing the recursion limit with sys.setrecursionlimit() but it only marginally helps and doesn’t fully address the performance concerns.
• Optimizing the recursive function by converting it to an iterative approach, but I’m unsure how to manage the recursion manually for deeply nested structures.

Questions:

1. How can I improve the recursion or refactor this code to handle much deeper structures efficiently?
2. Is there an iterative way to flatten this data structure without running into recursion depth limitations?
3. Are there any known libraries or patterns that can handle very deep and complex data structures like this more efficiently

The structure is dynamic and may not always follow the same pattern (dictionaries may not always contain the same keys, lists may not always contain the same types of data), so the function should be as generic as possible.

• python
• data-structures

Share Improve this question Follow edited yesterday John Kugelman 361k6969 gold badges546546 silver badges591591 bronze badges asked Jan 4 at 17:30 ahmadahmad 911 silver badge66 bronze badges 8

• 2 What is the deepest level of nesting you have? Are you sure your input does not have circular references? – trincot Commented Jan 4 at 18:28
• 1 How do you get that recursive structure in the first place? If you read it from a sequential file, it would probably be simpler and less resource consuming to directly read it into the final flat list. – Serge Ballesta Commented Jan 4 at 18:42
• Is your data really nested more than hundreds of levels deep? That seems unlikely. – Jeremy Banks Commented yesterday
• 1 @Ahmad, how come you edit your question and shout it is not duplicate, but do not answer comments that have been made 2 days ago? If you don't react to comments, nothing good will happen with your question. – trincot Commented yesterday
• 1 And why do you shout "THERE ARE NO ANSWERS", when there is an answer waiting for you since yesterday? Why is it not an answer to you? – trincot Commented yesterday

 |  Show 3 more comments

2 Answers 2

Sorted by: Reset to default 1

First of all, if you have nested lists with mostly 2 entries, and dicts with mostly 2 keys, and your nesting has an average depth of about one hundred levels deep, you have a number of values in the order of 2¹⁰⁰, i.e. ~10³⁰. Even if we only count 4 bytes per collected (leaf) value, that represents more volume than today's computers can store, and even more than the whole internet holds at the time of writing.

Either your nesting is not really that deep, but your program suffers from infinite recursion because the data has cyclic references, or your hierarchy is really narrow where the number of long root-to-leaf paths is not that huge.

You could avoid some allocation by using generators instead of collecting all values in a list.

If the size of the call stack is still a problem, even when you have ensured your data does not have cyclic references, then you can always go for an iterative version:

# 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()

A problem you're running into is that you're repeatedly making recursive calls and copying the results of those recursive calls. You can avoid all that copying:

def flatten(data):
    flat_list = []

    def inner(data):
        if isinstance(data, dict):
            for _, value in data.items():  # for value in data.values()
                inner(value)
        elif isinstance(data, list):
            for item in data:
                inner(item)
        else:
            flat_list.append(data)
            
    inner(data)
    return flat_list

As you build up the results, they are added once to the outer list.

本文标签：