Лучший подход для преобразования списка вложенных словарей в один словарь с агрегатными функциями

Question

Я просмотрел множество решений по этой теме c, но я не смог адаптировать свой кейс к высокопроизводительному. Предположим, у меня есть список словарей, хранящийся в виде:

db_data = [
  {
    "start_time": "2020-04-20T17:55:54.000-00:00",
    "results": {
      "key_1": ["a","b","c","d"],
      "key_2": ["a","b","c","d"],
      "key_3": ["a","b","c","d"]
    }
  },
  {
    "start_time": "2020-04-20T18:32:27.000-00:00",
    "results": {
      "key_1": ["a","b","c","d"],
      "key_2": ["a","b","e","f"],
      "key_3": ["a","e","f","g"]
    }
  },
  {
    "start_time": "2020-04-21T17:55:54.000-00:00",
    "results": {
      "key_1": ["a","b","c"],
      "key_2": ["a"],
      "key_3": ["a","b","c","d"]
    }
  },
  {
    "start_time": "2020-04-21T18:32:27.000-00:00",
    "results": {
      "key_1": ["a","b","c"],
      "key_2": ["b"],
      "key_3": ["a"]
    }
  }
]

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

Я пытаюсь объединить данные по значению даты и вывести количество уникальных значений для каждого ключа для каждого дня.

Ожидаемый результат примерно такой:

{
  "key_1": {
    "2020-04-20": 4,
    "2020-04-21": 3
  },
  "key_2": {
    "2020-04-20": 6,
    "2020-04-21": 2
  },
  "key_3": {
    "2020-04-20": 7,
    "2020-04-21": 4
  }
}

До сих пор я пытался использовать defaultdict и циклы для агрегирования данных. К сожалению, это занимает очень много времени:

from datetime import datetime

grouped_data = defaultdict(dict)

for item in db_data:
  group = item['start_time'].strftime('%-b %-d, %Y')
  for k, v in item['results'].items():
    if group not in grouped_data[k].keys():
      grouped_data[k][group] = []
    grouped_data[k][group] = list(set(v + grouped_data[k][group]))
for k, v in grouped_data.items():
  grouped_data[k] = {x:len(y) for x, y in v.items()}

print(grouped_data)

Любая помощь или руководство приветствуются. Я читал, что pandas может помочь здесь, но я не совсем уверен, как адаптировать этот вариант использования.

Редактировать Я не уверен, почему это было закрыто так быстро. Я просто ищу несколько советов о том, как повысить производительность. Буду признателен за повторное открытие.

Answer 1

У приведенного ниже кода есть генератор, назначенный на flat_list, который превращает исходный словарь в список кортежей. Тогда defaultdict устанавливается как словарь с двумя уровнями ключа, key и date, для которых значение равно set. Набор обновляется для каждого ключа / даты, поэтому он содержит список уникальных элементов. Это примерно похоже на пример кода, но он должен быть более эффективным.

>>> from collections import defaultdict
>>> from functools import partial
>>>
>>> flat_list = ((key, db_item['start_time'][:10], results)
...               for db_item in db_data
...               for key, results in db_item['results'].items())
>>> 
>>> d = defaultdict(partial(defaultdict, set))
>>> 
>>> for key, date, li in flat_list:
...     d[key][date].update(li)
...     

Тестируя его, мы получаем то же количество элементов списка на ключ / дату, что и количество в примере:

defaultdict(..., {'key_1': defaultdict(<class 'set'>, {
                           '2020-04-20': {'a', 'd', 'b', 'c'}, 
                           '2020-04-21': {'a', 'b', 'c'}}), 
                  'key_2': defaultdict(<class 'set'>, {
                           '2020-04-20': {'a', 'f', 'd', 'c', 'b', 'e'}, 
                           '2020-04-21': {'a', 'b'}}), 
                  'key_3': defaultdict(<class 'set'>, {
                           '2020-04-20': {'a', 'f', 'd', 'c', 'b', 'g', 'e'}, 
                           '2020-04-21': {'a', 'd', 'b', 'c'}})})

Если вы предпочитаете, чтобы значение было числом элементов списка, вы можете просто сделать len(d[key][date]).

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

[Обновить] Я не вижу увеличения производительности в моей системе с CPython 3.8, указанным в комментариях. Алгоритм здесь лишь немного быстрее, чем в примере, о котором идет речь, после фиксации строки с item['start_time'].strftime('%-b %-d, %Y') до item['start_time'][:10].

С учетом сказанного эффективность решается путем использования преимущества set. Операции над набором выполняются очень быстро, и мы просто обновляем его элементы. Нам не нужно сначала проверять список на членство в группе. Проверка списков на членство - очень медленная операция, которая действительно может сложиться в циклы. Сложность по времени для проверки списка на членство составляет O (n) для каждого добавленного элемента, тогда как для операций над множествами O (1) добавляется для элемента.

Ссылка на временную сложность python типов данных и операций: https://wiki.python.org/moin/TimeComplexity