I would like to implement a very popular MapReduce example using only existing programs operating in a UNIX way. The problem is to find N most frequent values in an enormous amount of data. The generic solution on any general-purpose programming language is:
- Map each value from the list to a tuple (value, 1).
- Group same values summing up their counts.
- Sort values by counts keeping top N frequent items.
For efficiency each step should fit into memory and be parallelized if possible. Thus I can use split
, paste
, xargs
and sort
from "core utils" and parallel
from "more utils" for the first two steps still satisfying problem constraints. But in order to implement the last step I need always keep not more than N values simultaneously or else I will quickly run out of memory, so obviously I cannot use sort
piped to head
. A common approach is to use "priority queue" data structure, but is there a program for that?
sort|uniq -c|sort -n|head -n $N
- only in a more efficient way, right? Can you give some (small) example input and the expected output? – michas Jan 12 '14 at 10:55