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
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