Иерархическая суммирующий в питона

Question

Учитывая следующий массив:

a = [] 
a.append({'c': 1, 'v': 10, 'p': 4}) 
a.append({'c': 2, 'v': 10, 'p': 4}) 
a.append({'c': 3, 'v': 10, 'p': None}) 
a.append({'c': 4, 'v': 0, 'p': None}) 
a.append({'c': 5, 'v': 10, 'p': 1}) 
a.append({'c': 6, 'v': 10, 'p': 1}) 

где с = код, v = значение и р = Родитель таблица выглядит следующим образом:

c v p 
1  4 
2 10 4 
3 10 
4 
5 10 1 
6 10 1 

Я должен суммировать каждый родитель со значениями это дети Ожидаемый результат таблица будет:

c v p 
1 20 4 
2 10 4 
3 10 
4 30 
5 10 1 
6 10 1 

Как это сделать?

Answer 1

Во-первых, вы должны получить другой словарь, сопоставляя родителей с списками своих детей, а не детей с родителями. Вы можете использовать для этого collections.defaultdict.

from collections import defaultdict 
children = defaultdict(list) 
for d in a: 
    children[d["p"]].append(d["c"]) 

Кроме того, я предлагаю другой словарь, картографирования коды к их значениям, так что вам не придется искать весь список каждый раз:

values = {} 
for d in a: 
    values[d["c"]] = d["v"] 

Теперь вы можете очень легко определить рекурсивную функцию для вычисления общей стоимости. Обратите внимание, однако, что это сделает некоторые избыточные вычисления. Если ваши данные намного больше, вы можете обойти это, используя немного воспоминаний.

def total_value(x): 
    v = values[x] 
    for c in children[x]: 
     v += total_value(c) 
    return v 

Наконец, используя эту функцию в Словаре понимания дает суммарные значения для каждого кода:

>>> {x: total_value(x) for x in values} 
{1: 30, 2: 10, 3: 10, 4: 40, 5: 10, 6: 10}