Stream merge: Difference between revisions
Content added Content deleted
(→Shell) |
No edit summary |
||
Line 14: | Line 14: | ||
Common solution: same as above, but keep buffered items and their source descriptors in a [[heap]]. |
Common solution: same as above, but keep buffered items and their source descriptors in a [[heap]]. |
||
== Python == |
|||
<lang python>import heapq |
|||
import sys |
|||
sources = sys.argv[1:] |
|||
for item in heapq.merge(open(source) for source in sources): |
|||
print(item)</lang> |
|||
== Shell == |
== Shell == |
Revision as of 09:11, 15 June 2016
Stream merge
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
Description
2-stream merge
Read two sorted streams of items from external source (e.g. disk, or network), and write one stream of sorted items to external sink.
Common algorithm: keep 1 buffered item from each source, select minimal of them, write it, fetch another item from that stream from which the written item was.
N-stream merge
The same as above, but reading from N sources.
Common solution: same as above, but keep buffered items and their source descriptors in a heap.
Python
<lang python>import heapq import sys
sources = sys.argv[1:] for item in heapq.merge(open(source) for source in sources):
print(item)</lang>
Shell
sort --merge source1 source2 sourceN > sink