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:

  1. Map each value from the list to a tuple (value, 1).
  2. Group same values summing up their counts.
  3. 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?

  • The actual problem you want to solve is 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
  • Imagine a very long list of any text words. – Alexander Solovets Jan 13 '14 at 2:55

GNU sort would benefit from a --range function to support this common operation: http://lists.gnu.org/archive/html/bug-coreutils/2009-07/msg00019.html

So I'd suggest to implement that in a local version of sort(1), and we'll merge it upstream too to make it generally available

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.