Выражение генератора Python для накопления значений словаря

Question

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

pairs = [(3, 47), (6, 47), (9, 47), (6, 27), (11, 27), (23, 27), (41, 27), (4, 67), (9, 67), (11, 67), (33, 67)]

Для каждой пары в парах, с ключом = пара [0] и значением = пара [1], я хочу передать этот поток пар в словарь, чтобы кумулятивно добавить значениядля соответствующих ключей.Очевидное решение:

dict_k_v = {}
for pair in pairs:
    try:
        dict_k_v[pair[0]] += pair[1]
    except:
        dict_k_v[pair[0]] = pair[1]

>>> dict_k_v
{33: 67, 3: 47, 4: 67, 6: 74, 9: 114, 11: 94, 41: 27, 23: 27}

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

EDIT

Чтобы уточнить, выражение генератора отбрасывает большое количество пар кортежей:

(3, 47), (6, 47), (9, 47), (6, 27), (11,27), (23, 27), (41, 27), (4, 67), (9, 67), (11, 67), (33, 67) ...

и я хочунакапливать каждую пару ключ-значение в словаре (см. ответ Пола Макгуайра) по мере генерирования каждой пары.Оператор пар = список [] не нужен, и извините за это.Для каждой пары (x, y) x является целым числом, а y может быть целым числом или десятичным / с плавающей точкой.

Выражение моего генератора имеет вид:

((x,y) for y in something() for x in somethingelse())

и хочу накапливать каждую (x, y) пару в defaultdict.Hth.

Answer 1

Для обсуждения вот простая функция генератора, которая дает нам некоторые данные:

from random import randint
def generator1():
    for i in range(10000):
        yield (randint(1,10), randint(1,100))

А вот базовое решение, которое использует цикл Python for для потребления генератора и подсчета количества для каждогопара ключ-значение

from collections import defaultdict

tally = defaultdict(int)
for k,v in generator1():
    tally[k] += v

for k in sorted(tally):
    print k, tally[k]

напечатает что-то вроде:

1 49030
2 51963
3 51396
4 49292
5 51908
6 49481
7 49645
8 49149
9 48523
10 50722

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

# define coroutine to update defaultdict for every
# key,value pair sent to it
def tallyAccumulator(t):
    try:
        while True:
            k,v = (yield)
            t[k] += v
    except GeneratorExit:
        pass

Мы инициализируем сопрограмму с tally defaultdict и подготовим ее к принятию значений, отправив ей значение None:

# init coroutine
tally = defaultdict(int)
c = tallyAccumulator(tally)
c.send(None)

Мы могли бы использовать цикл for или понимание списка, чтобы отправить все значения генератора в сопрограмму:

for val in generator1():
    c.send(val)

или

[c.send(val) for val in generator1()]

Но вместо этого мы будем использовать ноль-size deque для обработки всех значений выражения генератора без создания ненужного временного списка None:

# create generator expression consumer
from collections import deque
do_all = deque(maxlen=0).extend

# loop thru generator at C speed, instead of Python for-loop speed
do_all(c.send(val) for val in generator1())

Теперь мы снова посмотрим на значения:

for k in sorted(tally):
    print k, tally[k]

И мы получим другой список, аналогичныйк первому наe:

1 52236
2 49139
3 51848
4 51194
5 51275
6 50012
7 51875
8 46013
9 50955
10 52192

Подробнее о сопрограммах на странице Дэвида Бизли: http://www.dabeaz.com/coroutines/

Answer 2

Вы можете использовать деструктуризацию кортежей и defaultdict, чтобы сократить этот цикл:

from collections import defaultdict
d = defaultdict(int)
for k,v in pairs: d[k] += v

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

Подтверждение концепции с использованием groupby

Тем не менее, вы могли бы сделать это, используя itertools.groupby, но это что-то вроде хака:

import itertools
dict((k, sum(v for k,v in group)) for k, group 
     in itertools.groupby(sorted(pairs), lambda (k,v): k))

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

Answer 3

>>> dict((x[0], sum(y[1] for y in x[1])) for x in itertools.groupby(sorted(pairs, key=operator.itemgetter(0)), key=operator.itemgetter(0)))
{33: 67, 3: 47, 4: 67, 6: 74, 9: 114, 11: 94, 41: 27, 23: 27}

Answer 4

У Haskell есть очень хороший универсальный помощник для этого: Data.Map 's fromListWith.

fromListWith аналогичен конструкторам dict Python, но также принимает дополнительную функцию объединения для объединения повторяющихся значений ключей. Перевод на Python:

def dict_fromitems(items, combine):
    d = dict()
    for (k, v) in items:
        if k in d:
            d[k] = combine(d[k], v)
        else:
            d[k] = v
    return d

Используя этот помощник, легко выразить множество комбинаций:

>>> import operator
>>> dict_fromitems(pairs, combine=operator.add)
{33: 67, 3: 47, 4: 67, 6: 74, 9: 114, 11: 94, 41: 27, 23: 27}

>>> dict_fromitems(pairs, combine=min)
{33: 67, 3: 47, 4: 67, 6: 27, 9: 47, 11: 27, 41: 27, 23: 27}

>>> dict_fromitems(pairs, combine=max)
{33: 67, 3: 47, 4: 67, 6: 47, 9: 67, 11: 67, 41: 27, 23: 27}

>>> dict_fromitems(((k, [v]) for (k, v) in pairs), combine=operator.add)
{33: [67], 3: [47], 4: [67], 6: [47, 27], 9: [47, 67], 11: [27, 67], 41: [27], 2
3: [27]}

Обратите внимание, что в отличие от решений, использующих defaultdict(int), этот подход не ограничивается числовыми значениями, как показано в примере списка выше. (В общем, любой моноид является полезной возможностью: наборы с объединением / пересечением, логические значения с и / или, строки с конкатенацией и т. Д.)

Добавление

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

Answer 5

Нет, вы не можете сделать это без использования некоторой формы цикла. И использование цикла for на самом деле является наиболее разумной вещью, потому что вы изменяете что-то в теле цикла (а не, например, создаете новый итерируемый список). Однако вы можете упростить код, используя collections.defaultdict, вот так:

import collections
dict_k_v = collections.defaultdict(int)
for k, v in pairs:
    dict_k_v[k] += v

Answer 6

почему бы вам не использовать цикл for?

pairs = [(3, 47), (6, 47), (9, 47), (6, 27), (11, 27), (23, 27), (41, 27), (4, 67), (9, 67), (11, 67), (33, 67)]
result={}
def add(pair):
    k,v=pair
    result[k]=result.get(k,0)+v
map(add,pairs)
print result

Answer 7

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

import operator as o
def dict_sum(pairs, totals={}):
  k, v = pairs.pop()
  o.setitem(sum, k, totals.get(k, 0) + v)
  if not pairs:
    return totals
  else:
    return dict_sum(pairs, totals)

Я бы реализовал это в цикле for:

import operator as o
totals={}
for k, v in pairs:
   o.setitem(totals, k, totals.get(k, 0) + v)

Answer 8

Что-то вроде:

dict_k_v = dict(pairs)