Hey group,
This is kind of a cliched question but given a file with billion numbers
and the task is to compute 'k' largest numbers from this file, what
approach is preferred?
1) Using heaps
2) Using Median-of-median algorithm.
Have read few links which prefer heaps but clearly median of median
Using Median-of-median algorithm is not a practical approch bcozz as you
have mentioned it has billion of data.
so even if we ignore constant but when we implement is practically then
constant matters and value of constant would be very large to make it work
for O(n).
so heap would me much better
hey here how will you find the median over the billions of numbers when all
data doesnt fit at the same time in memory??
On Mon, Dec 12, 2011 at 6:41 AM, bharath sriram bharath.sri...@gmail.comwrote:
Hey group,
This is kind of a cliched question but given a file with billion numbers
and the