choose one millon random lines from a file containing one billion lines

This is an interesting problem and I can imagine lots of data intensive companies must be facing these types of challeges where they need to analyse the weblogs. So let me write down the problem statement and look at various available solutions

"Given an apache webserver logfile containing appx 1 billion entries, write an algorithm to select 1 million entries randomly from this file"

Solution:

Here are a few assumptions

1) Because the problem states that the file has appx 1 billion lines, I will assume that we don't know the exact number of lines in the files
2) I will assume that I don't have enough memory in my computer to hold all 1 billion lines. But I do have memory to hold 1 million lines and also I do have a data-structure that can count untill 1 million (longint ?)


Here is an algorithm I propose
$N=1000000
for (1..$N)
{
push @lines, scalar <>;
}


while(<>){
#Generate a random number between 0 and the current line number
$no = $.*(rand());
if($no < $N) { $line[rand $N] = $_; #Now if the random number generated is less than 1,000,000 then randomly select a lines to be replaced from already selected 1m lines and then replace that with the current line } } print @lines; Here two things happen - First as we progress through the file, we generate a random no between 0 & line# and if this random number is <>

Comments

Post a Comment

Popular posts from this blog

Pioneers! O Pioneers! COME, my tan-faced children, Follow well in order, get your weapons ready, Have you your pistols? Have you your sharp-edged axes? Pioneers! O pioneers! For we cannot tarry here, We must march my darlings, we must bear the brunt of danger, We the youthful sinewy races, all the rest on us depend, Pioneers! O pioneers! O you youths, Western youths, So impatient, full of action, full of manly pride and friendship, Plain I see you Western youths, see you tramping with the foremost, Pioneers! O pioneers! Have the elder races halted? Do they droop and end their lesson, wearied over there beyond the seas? We take up the task eternal, and the burden and the lesson, Pioneers! O pioneers! All the past we leave behind, We debouch upon a newer mightier world, varied world, Fresh and strong the world we seize, world of labor and the march, Pioneers! O pioneers! We detachments steady throwing, Down the edges, through the passes, up the mountains steep, Conquering, holding, dari
Read more

Impossible

Impossible is just a big word thrown around by small men who find it easier to live in the world they’ve been given than to explore the power they have to change it. Impossible is not a fact. It’s an opinion. Impossible is not a declaration. It’s a dare. Impossible is potential. Impossible is temporary. Impossible is nothing.
Read more