Erik wrote:
> Hi Peter,
>
> On 12/04/17 23:42, Peter Otten wrote:
>> Erik wrote:
>>
>>> I need to be able to lazily merge a variable number of already-sorted(*)
>>> variable-length sequences into a single sorted sequence.
>>
>> https://docs.python.org/dev/library/heapq.html#heapq.merge
>
> AFAICT (looking at the Python 3.5 heapq implementation, albeit very
> briefly), it seems like that is a greedy algorithm. Am I missing
> something?
>
> Thanks, E.
Watching it at work:
>>> import heapq
>>> def noisy(items, source):
... for item in items:
... print("fetching", item, "from", source)
... yield item
...
>>> a = noisy(range(0, 10, 2), "a")
>>> b = noisy(range(1, 10, 2), "b")
>>> c = noisy([3.5, 3.6, 5.5], "c")
>>> abc = heapq.merge(a, b, c)
>>> next(abc)
fetching 0 from a
fetching 1 from b
fetching 3.5 from c
0
>>> next(abc)
fetching 2 from a
1
>>> next(abc)
fetching 3 from b
2
>>> next(abc)
fetching 4 from a
3
>>> next(abc)
fetching 5 from b
3.5
>>> next(abc)
fetching 3.6 from c
3.6
Verdict: not greedy ;)
--
https://mail.python.org/mailman/listinfo/python-list
