Re^7: Strategy for randomizing large files via sysseek

I guess the size of your file is imiting. I wrote the code below, and got much better times than the sarcastic guy, but still much too slow for you I think. I based mine on sorting the indexes only, not the entire content of the line. However this does not address your problem of also removing duplicates. I'd be interested in testing what I can up with for your data file. If you want to post it somewhere let me know, and I'll see if I can beat your 4 hour mark.

use strict;
use Tie::File;
use Benchmark::Timer;

our $N ||= 100000;

sub shuffle {
    my $shuffled = ();
    my $numlines = scalar @{$_[0]};
    while ($numlines > 0) {
        my $randomLineNum = int rand $numlines;
        push(@$shuffled, $randomLineNum);
        splice(@{$_[0]}, $randomLineNum, 1);
        $numlines--;
    }
    return $shuffled;
}

open OUT, '>', 'junk.dat' or die $!;
printf OUT "%030d\n", $_ for 0 .. $N;
close OUT;

my @lines;
tie @lines, 'Tie::File', 'junk.dat';
my @indexList = (0..scalar @lines);
my $T = new Benchmark::Timer;

$T->start( "shuffling $N lines" );
my $newOrder = shuffle scalar \@indexList;
$T->stop( "shuffling $N lines" );

$T->start( "Writing New ordered File" );
open NEW, ">sortedJunk.dat";
foreach my $lineNum(@$newOrder){
    print NEW $lines[$lineNum],"\n";
}
$T->stop( "Writing New ordered File" );

$T->report();
[download]

and my results are pretty fast:
numLines,time,writingTime
100,281us total,15.222ms total
1000,1.480ms total,57.048ms total
10000,29.017ms total,559.466ms total
100000,1.922s total,5.969s total
1000000,256.212s total,154.443s total

Comment on Re^7: Strategy for randomizing large files via sysseek Download Code

Replies are listed 'Best First'.
Re^8: Strategy for randomizing large files via sysseek by BrowserUk (Patriarch) on Sep 16, 2004 at 08:34 UTC
Okay. You've avoided the major slowdown by not using Tie::File for both reading and writing--but there are still a problems with your approach. The first is that your shuffle is memory-based. That means that it will not scale beyond the point were your array of indexes is larger than memory. You probably think that by using an array of indices rather than an array of lines, you are saving large amounts of memory. This is not the case. A perl array uses at least 24 bytes of memory for every element of the array before you actually store anything in those elements. So, your array of indexes saves very little memory compared to storing the lines of the file. In the OP's case of at least 20 million lines, that is at least 20 million indexes x 24 bytes 480 MB. The second problem is your use of splice in your shuffle. As was brought home to me very clearly by Abigail in his post Be aware of splice, using splice in a shuffle endows it with quadratic performance at the C level. Being in C, it doesn't show up when dealing with smallish numbers (< 100_000) because the C code is so fast relative to the perl code that calls it, but; Once the numbers move above 100_000 that quadratic performance really begins to bite. See Abigail's post for the full SP on that one. I'd be interested in testing what I can up with for your data file. If you want to post it somewhere let me know, and I'll see if I can beat your 4 hour mark. The data file I used for the 1 billion lines test was a simple extension of that used above: `my $n=0; printf "%030d\n", $n++ while $n < 1E9;` [download] To test your code, just substitute that line into your program above; but be prepared for a looong wait :) The first long wait will come when the line: `my @indexList = (0..scalar @lines);` [download] is executed. In order for Tie::File to determine the size of the array (`scalar @lines`), it will have to read every line in the file. Whilst `wc -l` will do this for a 32 GB file in say 10 minutes, it will take Tie::File a great deal longer. This is because as well as reading every line of the file sequentially and discarding it--as wc -l would--, it also builds a hash of the offset of the start of each line. Each element of a hash is 21 bytes for each line. For 1 billion lines that amounts to at least 19.5 GB!. Examine what is said, not who speaks. "Efficiency is intelligent laziness." -David Dunham "Think for yourself!" - Abigail "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^8: Strategy for randomizing large files via sysseek
by BrowserUk (Patriarch) on Sep 16, 2004 at 08:34 UTC

Okay. You've avoided the major slowdown by not using Tie::File for both reading and writing--but there are still a problems with your approach.

The first is that your shuffle is memory-based. That means that it will not scale beyond the point were your array of indexes is larger than memory.
You probably think that by using an array of indices rather than an array of lines, you are saving large amounts of memory. This is not the case.
A perl array uses at least 24 bytes of memory for every element of the array before you actually store anything in those elements. So, your array of indexes saves very little memory compared to storing the lines of the file.
In the OP's case of at least 20 million lines, that is at least 20 million indexes x 24 bytes 480 MB.
The second problem is your use of splice in your shuffle. As was brought home to me very clearly by Abigail in his post Be aware of splice, using splice in a shuffle endows it with quadratic performance at the C level. Being in C, it doesn't show up when dealing with smallish numbers (< 100_000) because the C code is so fast relative to the perl code that calls it, but; Once the numbers move above 100_000 that quadratic performance really begins to bite. See Abigail's post for the full SP on that one.

I'd be interested in testing what I can up with for your data file. If you want to post it somewhere let me know, and I'll see if I can beat your 4 hour mark.

The data file I used for the 1 billion lines test was a simple extension of that used above:

my $n=0; printf "%030d\n", $n++ while $n < 1E9;
[download]

To test your code, just substitute that line into your program above; but be prepared for a looong wait :)

The first long wait will come when the line:

my @indexList = (0..scalar @lines);
[download]

is executed. In order for Tie::File to determine the size of the array (scalar @lines), it will have to read every line in the file. Whilst wc -l will do this for a 32 GB file in say 10 minutes, it will take Tie::File a great deal longer. This is because as well as reading every line of the file sequentially and discarding it--as wc -l would--, it also builds a hash of the offset of the start of each line.

Each element of a hash is 21 bytes for each line. For 1 billion lines that amounts to at least 19.5 GB!.

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

[reply]
[d/l]
[select]