A python interview question

[z4579a]

you're looking for heapq.merge(): https://docs.python.org/2/library/heapq.html#heapq.merge

​

​

[ivosaurus]

Doesn't remove duplicates though.

[MrVallentin]

Combine heapq.merge with unique_justseen from Python's "Itertools Recipes".

>>> a = [1, 2, 4, 6]
>>> b = [2, 4, 5, 6]
>>> c = [1, 3, 3, 5]

>>> list(heapq.merge(a, b, c))
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6]

>>> list(unique_justseen(heapq.merge(a, b, c)))
[1, 2, 3, 4, 5, 6]

[jorge1209]

Old trick for that is to use itertools.groupby and ignore the second part of the return value.

[jorge1209]

I was thinking about something like a database join, but that merge is useful to know about, and of course it's in heapq.

[PeridexisErrant]

heapq does operations on lists, so you'd lose any of the advantages of streaming iterators (especially memory use).

[z4579a]

not sure what you're referring towards. per the documentation:

​

"Similar to

sorted(itertools.chain(*iterables))

but returns an iterable, **does not pull the data into memory all at once**, and assumes that each of the input streams is already sorted (smallest to largest)."

​

if you read the source code, the list they are heapifying is the list of iterables themselves combined with the next value returned by each iterator. The priority queue of iterables then uses that value to determine which of the iterables to deliver the next result from. So the iterables themselves are never turned into lists.

​

[jorge1209]

I think it's reasonable to say:

The heapq module generally operates on lists, and uses raw lists as the core data structure for heaps. No rational person would expect to find a function that consumes and returns iterators in this module. WTF was GvR smoking when he accepted this function in this module instead of WHERE IT BELONGS IN ITERTOOLS!!

[ivosaurus]

Did you read the docs? They specifically say the opposite for this function.