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