0

Всем привет!

Помогите пожалуйста разработать алгоритм.

Есть исходный список, состоящий из словарей:

[

   {
       'A':'string1',
       'B':'string_5',
       'C':'string_9,
        ...
       'N':'stringN',
       'metric1':5,
       'metric2':7
    },

    {
      'A':'string1',
      'B':'string_5',
      'C':'string_11,...
      'N':'stringN',
      'metric1':10,
      'metric2':45
    },

    {
      'A':'string2',
      'B':'string_7',
      'C':'string_15,
       ...
      'N':'stringN',
      'metric1':234,
      'metric2':78
    },

    .......
 ]

На выходе нужно получить такой список:

       [

           {
            'A':'string1', 'metric1':sum(all metric1 where 'A'='string1'), 
            'metric2':sum(all metric2 where 'A'='string1'), 
            'B': [

                   {
                  'B':'string_5',
                  'metric1':sum(all metric1 for combination where 'A' in 
                                          'string1' and 'B' in string_5), 
                   'metric2':sum(all metric2 , where combination Similarly 'metric1'), 
                   'C':[

                         {
                           'C':'string_9', 'metric1':sum(all metric_1 for 
                     combination where 'A' in` 'string1' and 'B' in string_5 and 'C' is 'string_9'),
                           'metric2':sum(...)
                          }, 
                          {
                            'C':'string_11',
                            'metric1':sum(...)
                            'metric2':sum(..)
                          }
                       ]

                   }
                 ]
             },
             {
               'A':'string_2', 'metric1':sum(all metric1 where 'A'='string2'),
              'metric2':sum(...), 
              'B': [

                      {
                        'B':'string_7','metric1':sum(all metric1 for   
                  combination where 'A'='string_2' and 'B'='string_7'), 
                        'metric2':'sum(...),
                        'C': [
                               {
                                 'C':'string_15', 
                                  'metric1' :sum(...), 
                                 'metric2':'sum(...)
                               }
                             ]
                       }
                    ]
               },

         ....

            .....
        ]  

Т.е. алгоритм должен делать следующее: обходим по порядку весь список словарей, и группируем по первому ключу (в нашем случае "А", суммируя при этом каждую из метрик, и на выходе получая словарь с ключами: - Название уровня - Сумма каждой из метрик -Пустой список, с названием следующего уровня. ("B":[])

Затем проходим по второму уровню ("B"), группируем их по второму ключу, и те элементы, у которых первый уровень "А" - их заносим в созданный ранее массив "B", опять таки суммируя все метрики, и на выходе получая аналогичный словарь как выше, где есть пустой список с название следующего уровня ("С"). И так далее, до последнего уровня.

Пробовал использовать рекурсивную функцию, которая вызывала себя для каждого элемента на нижнем уровне, но в итоге получил словарь, в который входили только первые элементы на каждом из уровней, и не допёр, как сделать рекурсию для каждой полученной ветки в результате группировки.

4
  • А как порядок ключей A,B,C определяется? лексикографически? То есть как узнать, что B должен быть вложен в A, а не наоборот?
    – jfs
    11 сен 2016 в 14:53
  • @jfs А они изначально упорядочены, т.е. именно таков порядок их вложенности.
    – SmartSt
    11 сен 2016 в 18:37
  • порядок ключей в dict неопределён (и даже если порядок известен для выбранной версии/реализации Питона, не следует на него полагаться, иначе могут возникнуть скрытые баги, если вашу программу на другой версии/реализации Питона запустить).
    – jfs
    11 сен 2016 в 18:40
  • @jfs Понял что не совсем верно ответил - есть дополнительный список, который как раз содержит порядок ключей. order=['A','B','C']
    – SmartSt
    11 сен 2016 в 19:16

1 ответ 1

3

Достаточно простой код получается, если сгруппировать словари по их значению текущего уровня (такого как 'string1') и просто суммировать значения соответствующих метрик для выбранных словарей, вызывая функцию рекурсивно, чтобы получить значения для нижних уровней:

#!/usr/bin/env python3
from collections import defaultdict

def sum_metrics(dicts, metric_names=('metric1', 'metric2')):
    return {metric: sum(d[metric] for d in dicts) for metric in metric_names}

def generate_level_simple(dicts, levels):
    if not levels: # no levels
        return {}  # nothing to generate

    level, *levels = levels # pop level
    level2dicts = defaultdict(list)  # level value -> dicts
    for d in dicts:
        level2dicts[d[level]].append(d)

    return {level: [{level: level_value,
                     **sum_metrics(level_dicts),
                     **generate_level_simple(level_dicts,  levels)}
                    for level_value, level_dicts in level2dicts.items()]}

print(generate_level_simple(dicts, order)[order[0]])

где dicts—это исходный список словарей из вопроса, а order—это список, определяющий порядок вложенности уровней.

Результат

[{'A': 'string1',
  'B': [{'B': 'string_5',
         'C': [{'C': 'string_9', 'metric1': 5, 'metric2': 7},
               {'C': 'string_11', 'metric1': 10, 'metric2': 45}],
         'metric1': 15,
         'metric2': 52}],
  'metric1': 15,
  'metric2': 52},
 {'A': 'string2',
  'B': [{'B': 'string_7',
         'C': [{'C': 'string_15', 'metric1': 234, 'metric2': 78}],
         'metric1': 234,
         'metric2': 78}],
  'metric1': 234,
  'metric2': 78}]

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

def generate_level(dicts, level, levels):
    level2dicts = defaultdict(list)  # level value -> dicts
    for d in dicts:
        level2dicts[d[level]].append(d)

    if not levels:  # the deepest level
        return {level: [{level: level_value, **sum_metrics(level_dicts)}
                        for level_value, level_dicts in level2dicts.items()]}

    inner_level, *levels = levels  # pop level
    inner_dicts = (generate_level(level_dicts, inner_level, levels)
                   for level_dicts in level2dicts.values())
    return {level: [{level: level_value,
                     **sum_metrics(level_dict[inner_level]),
                     **level_dict}
                    for level_value, level_dict in zip(level2dicts, inner_dicts)]}

level, *nested_levels = order
print(generate_level(dicts, level, nested_levels)[level])

В данном случае суммируются метрики для словарей только с непосредственно прилегающего уровня (без ненужного дублирования). Результат тот же.

Код использует Питон 3 синтаксис для разложения/распаковки списков и словарей, введённый в PEP 3132 и PEP 448 (последнее доступно начиная с Python 3.5).

1
  • Вы просто гений, уровень python - Бог !) Спасибо)) @jfs
    – SmartSt
    11 сен 2016 в 20:42

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.