I have a list of complex dictionaries like this:

data = [
  {
    "l_1_k": 1,
    "l_1_ch": [
      {
        "l_2_k": 2,
        "l_2_ch": [...more levels]
      },
      {
        "l_2_k": 3,
        "l_2_ch": [...more levels]
      }
    ]
  },
  ...more items
]

I'm trying to flatten this structure to a list of rows like this:

list = [
  { "l_1_k": 1, "l_2_k": 2, ... },
  { "l_1_k": 1, "l_2_k": 3, ... },
]

I need this list to build a pandas data frame.

So, I'm doing a recursion for each nesting level, and at the last level I'm trying to append to rows list.

def build_dict(d, row_dict, rows):
    # d is the data dictionary at each nesting level
    # row_dict is the final row dictionary
    # rows is the final list of rows
    for key, value in d.items():
        if not isinstance(value, list):
            row_dict[key] = value
        else:
            for child in value:
                build_dict(child, row_dict, rows)
    rows.append(row_dict) # <- How to detect the last recursion and call the append

I'm calling this function like this:

rows = []
for row in data:
    build_dict(d=row, row_dict={}, rows=rows)

My question is how to detect the last call of this recursive function if I do not know how many nesting levels there are. With the current code, the row is duplicated at each nesting level.

Or, is there a better approach to obtain the final result?

CodePudding user response：

After looking up some ideas, the solution I have in mind is this:

1. Declare the following function, taken from here:

def find_depth(d):
    if isinstance(d, dict):
        return 1   (max(map(find_depth, d.values())) if d else 0)
    return 0

2. In your function, increment every time you go deeper as follows:

def build_dict(d, row_dict, rows, depth=0):
    # depth = 1 for the beginning
    for key, value in d.items():
        if not isinstance(value, list):
            row_dict[key] = value
        else:
            for child in value:
                build_dict(child, row_dict, rows, depth   1)

3. Finally, test if you reach the maximum depth, if so, at the end of your function you can append it. You will need to add an extra variable which you will call:

def build_dict(d, row_dict, rows, max_depth, depth=0):
    # depth = 1 for the beginning
    for key, value in d.items():
        if not isinstance(value, list):
            row_dict[key] = value
        else:
            for child in value:
                build_dict(child, row_dict, rows,max_depth, depth   1)
    if depth == max_depth:
        rows.append(row_dict)

4. Call the function as:

    build_dict(d=row, row_dict={}, rows=rows, max_depth=find_depth(data))

Do keep in mind since I don't have a data-set I can use, there might be a syntax error or two in there, but the approach should be fine.

CodePudding user response：

I don't think it is good practice to try to play with mutable default argument in function prototype.

Also, I think that the function in the recursion loop should never be aware of the level it is in. That's the point of the recursion. Instead, you need to think about what the function should return, and when it should exit the recursion loop to climb back to the zeroth level. On the climb back, higher level function calls handle the return value of lower level function calls.

Here is the code that I think will work. I am not sure it is optimal, in term of computing time.

edit: fixed return list of dicts instead of dict only

def build_dict(d):
    """
    returns a list when there is no lowerlevel list of dicts.
    """
    lst = []

    for key, value in d.items():
        if not isinstance(value, list):
            lst.append([{key: value}])
        else:
            lst_lower_levels = []
            for child in value:
                lst_lower_levels.extend(build_dict(child))

            new_lst = []
            for elm in lst:
                for elm_ll in lst_lower_levels:
                    lst_of_dct = elm   elm_ll
                    new_lst.append([{k: v for d in lst_of_dct for k, v in d.items()}])
            lst = new_lst
    return lst

rows = []
for row in data:
    rows.extend(build_dict(d=row))