Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

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?

share|improve this question
    
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 at 10:55
    
Imagine a very long list of any text words. –  Alexander Solovets Jan 13 at 2:55

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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