[ python-Bugs-1185121 ] itertools.imerge: merge sequences
SourceForge.net
noreply at sourceforge.net
Mon Apr 18 14:11:24 CEST 2005
Bugs item #1185121, was opened at 2005-04-18 12:11
Message generated for change (Tracker Item Submitted) made by Item Submitter
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1185121&group_id=5470
Category: Python Library
Group: Feature Request
Status: Open
Resolution: None
Priority: 5
Submitted By: Jurjen N.E. Bos (jneb)
Assigned to: Nobody/Anonymous (nobody)
Summary: itertools.imerge: merge sequences
Initial Comment:
(For the itertools library, so Python 2.2 and up)
This is a suggested addition to itertools, proposed name imerge.
usage: imerge(seq0, seq1, ..., [key=<key function>])
result: imerge assumes the sequences are all in sorted order, and
produces a iterator that returns pairs of the form (value, index),
where value is a value of one of the sequences, and index is the
index number of the given sequence.
The output the imerge is in sorted order (taking into account the
key function), so that identical values in the sequences will be
produced from left to right.
The code is surprisingly short, making use of the builtin heap
module.
(You may disagree with my style of argument handling; feel free to
optimize it.)
def imerge(*iterlist, **key):
"""Merge a sequence of sorted iterables.
Returns pairs [value, index] where each value comes from
iterlist[index], and the pairs are sorted
if each of the iterators is sorted.
Hint use groupby(imerge(...), operator.itemgetter(0)) to get
the items one by one.
"""
if key.keys() not in ([], ["key"]): raise TypeError, "Excess
keyword arguments for imerge"
key = key.get("key", lambda x:x)
from heapq import heapreplace, heappop
#initialize the heap containing (inited, value, index,
currentItem, iterator)
#this automatically makes sure all iterators are initialized,
then run, and finally emptied
heap = [(False, None, index, None, iter(iterator)) for index,
iterator in enumerate(iterlist)]
while heap:
inited, item, index, value, iterator = heap[0]
if inited: yield value, index
try: item = iterator.next()
except StopIteration: heappop(heap)
else: heapreplace(heap, (True, key(item), index, item,
iterator))
If you find this little routine worth its size, please put it into
itertools.
- Jurjen
----------------------------------------------------------------------
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1185121&group_id=5470
More information about the Python-bugs-list
mailing list