Соединение нескольких итераторов ключом
Дано: n итераторов и функция для получения ключа для элемента для каждого из них
Предполагая, что:
- Итераторы предоставляют элементы, отсортированные по ключу
- Ключи от любого итератора уникальны
Я хочу перебрать их, соединенные ключами. Например, учитывая следующие 2 списка:
[('a', {type:'x', mtime:Datetime()}), ('b', {type='y', mtime:Datetime()})]
[('b', Datetime()), ('c', Datetime())]
Используя первый элемент в каждом кортеже в качестве ключа, я хочу получить:
(('a', {type:'x', mtime:Datetime()}), None)
(('b', {type:'y', mtime:Datetime()}), ('b', Datetime()),)
(None, ('c', Datetime()),)
Итак, я взломал этот метод:
def iter_join(*iterables_and_key_funcs):
iterables_len = len(iterables_and_key_funcs)
keys_funcs = tuple(key_func for iterable, key_func in iterables_and_key_funcs)
iters = tuple(iterable.__iter__() for iterable, key_func in iterables_and_key_funcs)
current_values = [None] * iterables_len
current_keys= [None] * iterables_len
iters_stoped = [False] * iterables_len
def get_nexts(iters_needing_fetch):
for i, fetch in enumerate(iters_needing_fetch):
if fetch and not iters_stoped[i]:
try:
current_values[i] = iters[i].next()
current_keys[i] = keys_funcs[i](current_values[i])
except StopIteration:
iters_stoped[i] = True
current_values[i] = None
current_keys[i] = None
get_nexts([True] * iterables_len)
while not all(iters_stoped):
min_key = min(key
for key, iter_stoped in zip(current_keys, iters_stoped)
if not iter_stoped)
keys_equal_to_min = tuple(key == min_key for key in current_keys)
yield tuple(value if key_eq_min else None
for key_eq_min, value in zip(keys_equal_to_min, current_values))
get_nexts(keys_equal_to_min)
и проверить это:
key_is_value = lambda v: v
a = ( 2, 3, 4, )
b = (1, )
c = ( 5,)
d = (1, 3, 5,)
l = list(iter_join(
(a, key_is_value),
(b, key_is_value),
(c, key_is_value),
(d, key_is_value),
))
import pprint; pprint.pprint(l)
какие выводы:
[(None, 1, None, 1),
(2, None, None, None),
(3, None, None, 3),
(4, None, None, None),
(None, None, 5, 5)]
Есть ли существующий способ сделать это? Я заказал itertools, но ничего не смог найти.
Есть ли способы улучшить мой метод? Сделайте это проще, быстрее и т.д..
Обновление: решение используется
Я решил упростить контракт для этой функции, требуя, чтобы итераторы выдавали кортеж (ключ, значение) или кортеж (ключ, * значения). Используя ответ agf в качестве отправной точки, я придумал это:
def join_items(*iterables):
iters = tuple(iter(iterable) for iterable in iterables)
current_items = [next(itr, None) for itr in iters]
while True:
try:
key = min(item[0] for item in current_items if item != None)
except ValueError:
break
yield tuple(item if item != None and item[0]==key else None
for item in current_items)
for i, (item, itr) in enumerate(zip(current_items, iters)):
if item != None and item[0] == key:
current_items[i] = next(itr, None)
a = ( (2,), (3,), (4,), )
b = ((1,), )
c = ( (5,),)
d = ((1,), (3,), (5,),)
e = ( )
import pprint; pprint.pprint(list(join_items(a, b, c, d, e)))
[(None, (1,), None, (1,), None),
((2,), None, None, None, None),
((3,), None, None, (3,), None),
((4,), None, None, None, None),
(None, None, (5,), (5,), None)]
4 ответа
a = ( 2, 3, 4, )
b = (1, )
c = ( 5,)
d = (1, 3, 5,)
iters = [iter(x) for x in (a, b, c, d)]
this = [next(i) for i in iters]
while True:
try:
key = min(i for i in this if i != None)
except ValueError:
break
for i, val in enumerate(this):
if val == key:
print val,
this[i] = next(iters[i], None)
else:
print None,
print
Пример в начале вашего вопроса отличается от конца.
Для первого примера я бы сделал это:
x = [('a', {}), ('b', {})]
y = [('b', {}), ('c', {})]
xd, yd = dict(x), dict(y)
combined = []
for k in sorted(set(xd.keys()+yd.keys())):
row = []
for d in (xd, yd):
row.append((k, d[k]) if k in d else None)
combined.append(tuple(row))
for row in combined:
print row
дает
(('a', {}), None)
(('b', {}), ('b', {}))
(None, ('c', {}))
Для второго примера
a = ( 2, 3, 4, )
b = (1, )
c = ( 5,)
d = (1, 3, 5,)
abcd = map(set, [a,b,c,d])
values = sorted(set(a+b+c+d))
print [tuple(v if v in row else None for row in abcd) for v in values]
дает
[(None, 1, None, 1),
(2, None, None, None),
(3, None, None, 3),
(4, None, None, None),
(None, None, 5, 5)]
Но что вы пытаетесь достичь? Возможно, вам нужны разные структуры данных.
import itertools as it
import heapq
import pprint
def imerge(*iterables):
'''
http://code.activestate.com/recipes/491285-iterator-merge/
Author: Raymond Hettinger
Merge multiple sorted inputs into a single sorted output.
Equivalent to: sorted(itertools.chain(*iterables))
>>> list(imerge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25]))
[0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25]
'''
heappop, siftup, _StopIteration = heapq.heappop, heapq._siftup, StopIteration
h = []
h_append = h.append
for it in map(iter, iterables):
try:
next = it.next
h_append([next(), next])
except _StopIteration:
pass
heapq.heapify(h)
while 1:
try:
while 1:
v, next = s = h[0] # raises IndexError when h is empty
yield v
s[0] = next() # raises StopIteration when exhausted
siftup(h, 0) # restore heap condition
except _StopIteration:
heappop(h) # remove empty iterator
except IndexError:
return
a = ( 2, 3, 4, )
b = (1, )
c = ( 5,)
d = (1, 3, 5,)
def tag(iterator,val):
for elt in iterator:
yield elt,val
def expand(group):
dct=dict((tag,val)for val,tag in group)
result=[dct.get(tag,None) for tag in range(4)]
return result
pprint.pprint(
[ expand(group)
for key,group in it.groupby(
imerge(*it.imap(tag,(a,b,c,d),it.count())),
key=lambda x:x[0]
)])
Объяснение:
- Жизнь была бы проще, если бы мы слили итераторы. Это может быть сделано с
imerge
itertools.groupby
дает нам желаемую группировку, если мы будем кормить его
результат отimerge
, Все остальное просто суетящиеся детали.pprint.pprint( [ list(group) for key,group in it.groupby( imerge(a,b,c,d)) ] ) # [[1, 1], [2], [3, 3], [4], [5, 5]]
- Из приведенного выше вывода ясно, что нам нужно отслеживать источник каждого значения - (получено ли значение из
a
, или жеb
, так далее.). Таким образом, мы можем дополнить выводNone
с в нужных местах. Для этого я использовал
it.imap(tag,(a,b,c,d),it.count())
,tag(a)
возвращает итератор, который возвращает значения изa
вместе со значением счетчика.>>> list(tag(a,0)) # [(2, 0), (3, 0), (4, 0)]
Вывод теперь выглядит так:
pprint.pprint( [ list(group) for key,group in it.groupby( imerge(*it.imap(tag,(a,b,c,d),it.count())), key=lambda x:x[0] )]) # [[(1, 1), (1, 3)], [(2, 0)], [(3, 0), (3, 3)], [(4, 0)], [(5, 2), (5, 3)]]
- Наконец, мы используем
expand(group)
изменить[(1, 1), (1, 3)]
в[None, 1, None, 1]
,
Я понимаю, что ответ уже был решен. Однако я думаю, что более чистый способ может быть написан с использованием объекта defaultdict из библиотеки коллекций.
Вот пример из http://docs.python.org/release/2.6.7/library/collections.html
>>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
>>> d = defaultdict(list)
>>> for k, v in s:
... d[k].append(v)
>>>>d.items()
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]