Генератор для объединения отсортированных словарных итераций

Это вариант генератора для получения кортежей пробелов из заархивированных итераций.

Я хочу разработать функцию генератора, которая:

  • Принимает произвольное количество итераций
  • Каждая итерация ввода дает ноль или более (k, v), k не обязательно уникально
  • Предполагается, что входные ключи отсортированы в порядке возрастания.
  • Результат должен дать (k, (v1, v2, ...))
  • Ключи вывода являются уникальными и отображаются в том же порядке, что и ввод
  • Количество выходных кортежей равно количеству уникальных ключей во входных данных.
  • Выходные значения соответствуют всем входным кортежам, соответствующим выходному ключу.
  • Поскольку входы и выходы потенциально велики, их следует рассматривать как итерации, а не загружать как словарь или список в памяти.

В качестве примера,

i1 = ((2, 'a'), (3, 'b'), (5, 'c'))
i2 = ((1, 'd'), (2, 'e'), (3, 'f'))
i3 = ((1, 'g'), (3, 'h'), (5, 'i'), (5, 'j'))
result = sorted_merge(i1, i2, i3)
print [result]

Это выведет:

[(1, ('d', 'g')), (2, ('a', 'e')), (3, ('b', 'f', 'h')), (5, ('c', 'i', 'j'))]

Если я не ошибаюсь, в стандартной библиотеке Python нет ничего, что могло бы сделать это из коробки.


python dictionary sorting iterator python-2.6
person Reinderien    schedule 11.09.2014    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Хотя не существует единой стандартной библиотечной функции, которая бы делала то, что вы хотите, есть достаточно строительства блоки, которые помогут вам в большинстве случаев:

from heapq import merge
from itertools import groupby
from operator import itemgetter

def sorted_merge(*iterables):
    for key, group in groupby(merge(*iterables), itemgetter(0)):
        yield key, [pair[1] for pair in group]

Пример:

>>> i1 = ((2, 'a'), (3, 'b'), (5, 'c'))
>>> i2 = ((1, 'd'), (2, 'e'), (3, 'f'))
>>> i3 = ((1, 'g'), (3, 'h'), (5, 'i'), (5, 'j'))
>>> result = sorted_merge(i1, i2, i3)
>>> list(result)
[(1, ['d', 'g']), (2, ['a', 'e']), (3, ['b', 'f', 'h']), (5, ['c', 'i', 'j'])]

Обратите внимание, что в приведенной выше версии sorted_merge мы получаем пары int, list для получения читаемого вывода. Вам ничего не мешает изменить соответствующую строку на

        yield key, (pair[1] for pair in group)

если вы хотите получить вместо этого int, <generator> пар.

person Zero Piraeus    schedule 11.09.2014
comment
Я думаю, что единственная модификация, которую я бы сделал для этого (в дополнение к предложенному вами изменению генератора), - это заменить itemgetter простой лямбдой. - person Reinderien; 12.09.2014
comment
@Reinderien, конечно, твой выбор, но почему? Это именно то, для чего itemgetter ... и он короче, IMO более читабелен и, вероятно, быстрее. - person Zero Piraeus; 12.09.2014
comment
На один импорт меньше, на одну функцию меньше, для которой необходимо прочитать документы, и альтернатива достаточно проста. Но лишь незначительно. - person Reinderien; 12.09.2014
comment
Достаточно справедливо ... Я буду придерживаться своих предпочтений, но вам может быть интересно узнать, что другие согласны с вами < / а>. - person Zero Piraeus; 12.09.2014
comment
При этом wiki.python.org/moin/PythonSpeed ​​, по-видимому, предпочитает operator для скорости. - person Reinderien; 12.09.2014

arrow_upward
0
arrow_downward

Что-то немного другое:

from collections import defaultdict

def sorted_merged(*items):
    result = defaultdict(list)
    for t in items:
        for k, v in t:
           result[k].append(v)
    return sorted(list(result.items()))

i1 = ((2, 'a'), (3, 'b'), (5, 'c'))
i2 = ((1, 'd'), (2, 'e'), (3, 'f'))
i3 = ((1, 'g'), (3, 'h'), (5, 'i'), (5, 'j'))

result = sorted_merged(i1, i2, i3)
person monkut    schedule 11.09.2014
comment
К сожалению, dict по умолчанию съест мою память. - person Reinderien; 11.09.2014