Самые быстрые способы по ключу добавить список dicts вместе в Python

Question

Скажите, у меня есть несколько словарей

a = {'x': 1.0, 'y': 0.5, 'z': 0.25 }
b = {'w': 0.5, 'x': 0.2 }

Там только два, но вопрос касается произвольной суммы.

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

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

Редактировать: Я думаю, что я вводил в заблуждение, каким должен быть результат, если значение отсутствует, оно должно действовать как 0.0, поэтому результат для приведенного выше примера будет:

{'w':0.25,'x':0.6,'y':0.25,'z':0.125}

Итак, деление по общему количеству уникальных ключей.

Главное, что мне интересно, есть ли хитрый способ разделить весь dict на длину за один шаг, или сделать сложения за один шаг. В основном очень быстрое векторное сложение и деление. Я кратко рассмотрел массивы numpy, но, похоже, они не применяются к диктам, и если бы я конвертировал дикты в списки, мне пришлось бы удалить свойство sparseness (явно установив отсутствующие значения в 0).

Answer 1

Это работает:

import collections

data= [
    {'x': 1.0, 'y': 0.5, 'z': 0.25 },
    {'w': 0.5, 'x': 0.2 }
    ]

tally = collections.defaultdict(lambda: (0.0, 0))

for d in data:
    for k,v in d.items():
        sum, count = tally[k]
        tally[k] = (sum+v, count+1)

results = {}
for k, v in tally.items():
    t = tally[k]
    results[k] = t[0]/t[1]

print results

Я не знаю, быстрее ли он, чем ваш, поскольку вы не опубликовали свой код.

{'y': 0.5, 'x': 0.59999999999999998, 'z': 0.25, 'w': 0.5}

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

Answer 2

С помощью профилирования можно доказать, что это не совсем быстро, но ...

import collections

a = {'x': 1.0, 'y': 0.5, 'z': 0.25 }
b = {'w': 0.5, 'x': 0.2 }
dicts = [a,b]

totals = collections.defaultdict(list)
avg = {}

for D in dicts:
    for key,value in D.iteritems():
        totals[key].append(value)

for key,values in totals.iteritems():
   avg[key] = sum(values) / len(values)

Я догадываюсь , что разрешение Python использовать встроенные модули sum() и len() даст некоторую производительность по сравнению с вычислением среднего значения при появлении новых значений, но я уверен, неправильно об этом.

Answer 3

>>> def avg(items):
...     return sum(items) / len(items)
... 
>>> hashes = [a, b]
>>> dict([(k, avg([h.get(k) or 0 for h in hashes])) for k in set(sum((h.keys() for h in hashes), []))])
{'y': 0.25, 'x': 0.59999999999999998, 'z': 0.125, 'w': 0.25}

Пояснение:

1. Набор ключей во всех хэшах, без повторов.

   set(sum((h.keys() for h in hashes), []))
   

2. Среднее значение для каждого ключа в указанном выше наборе, с использованием 0, если значение не существует в конкретном хеше.

   (k, avg([h.get(k) or 0 for h in hashes]))
   

Answer 4

Это просто, но это может сработать:

a = { 'x': 1.0, 'y': 0.5, 'z': 0.25 }
b = { 'w': 0.5, 'x': 0.2 }

ds = [a, b]
result = {}

for d in ds:
    for k, v in d.iteritems():
        result[k] = v + result.get(k, 0)

n = len(ds)
result = dict((k, amt/n) for k, amt in result.iteritems())

print result

Понятия не имею, как он соотносится с вашим методом, поскольку вы не опубликовали код.

Answer 5

scipy.sparse поддерживает разреженные матрицы - форма dok_matrix кажется достаточно подходящей для ваших нужд (хотя вам придется использовать целочисленные координаты, поэтому отдельный проход понадобится собрать и поместить в произвольном, но определенном порядке ключи строки, которые у вас есть). Если у вас есть огромное количество очень больших и редких «массивов», выигрыш в производительности может стоить осложнений.

Answer 6

Возможно, что узкое место может быть связано с чрезмерным использованием памяти. Подумайте об использовании iteritems для использования мощности генераторов.

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

dicts = ... #Assume this is your dataset
totals = {}
lengths = {}
means = {}
for d in dicts:
    for key,value in d.iteritems():
        totals.setdefault(key,0)
        lengths.setdefault(key,0)
        totals[key] += value
        length[key] += 1
for key,value in totals.iteritems():
    means[key] = value / lengths[key]

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

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

dicts = ... #Assume this is your dataset
key_set = Set([])
for d in dicts: key_set.update(d.keys())
means = {}
def get_total(dicts, key):
    vals = (dict[key] for dict in dicts if dict.has_key(key))
    return sum(vals)
def get_length(dicts, key):
    vals = (1 for dict in dicts if dict.has_key(key))
    return sum(vals)
def get_mean(dicts,key):
    return get_total(dicts,key)/get_length(dicts,key)
for key in key_set:
    means[key] = get_mean(dicts,key)

В конечном итоге вы дважды просматриваете все словари для каждого ключа, но не нуждаетесь в промежуточных структурах данных, кроме key_set.