Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

Re^3: sorting type question- space problems

by BrowserUk (Pope)
on Sep 15, 2013 at 13:55 UTC ( #1054182=note: print w/ replies, xml ) Need Help??

in reply to Re^2: sorting type question- space problems
in thread sorting type question- space problems

Some records are big > 5MB and some are small (5 bytes) so in-memory sort is not an option :(

Actually, it is. Or at least, it may be so ... if the lengths of the keys in your OP is somewhat representative of your real data; and you have a couple of GB of ram available.

The lengths of the records is immaterial; the 5 million records can be represented in memory by the two keys + an (64-bit) integer offset of the start of each record's position within the file. If the two keys are less than ~8 bytes each, then the total memory requirement for 5 million anonymous subs each containing 2 keys + file offet is ~ 1.8GB.

This code builds an index of the two keys + file offset in an AoA; sorts that AoA in memory and then writes the output file by seeking the input file, reading the appropriate record and writing it to the output file. For a 5 million record file it takes a little over 2 minutes on my machine:

#! perl -sw use strict; open IN, '<', $ARGV[0] or die $!; my @index; my $pos = 0; while( <IN> ) { my( $k1, $k2 ) = m[(^\S+)\s+(\S+)]; push @index, [$k1, $k2, $pos]; $pos = tell IN; } @index = sort{ $a->[0] cmp $b->[0] || $a->[1] cmp $b->[1] } @index; open OUT, '>', 'sorted'; for my $r ( @index ) { seek IN, $r->[2], 0; print OUT scalar <IN>; } close OUT; close IN; __END__ C:\test>dir unsorted 15/09/2013 14:40 117,501,066 unsorted C:\test>wc -l unsorted 5000000 unsorted C:\test>head unsorted key25 key15 xxxxxxxxxxx key28 key05 xxxxx key30 key18 xxxxxxxxxxxxxx key24 key03 xxxxxxxxx key41 key01 xxxxxxxxxxxxxx key12 key16 xxxxxxxxxxxx key38 key20 xx key19 key19 xxxxxxxxxxxxxxxxxx key30 key13 xxxxxxxx key16 key19 xxxxxxxxxxxxx [14:41:03.25] C:\test>1054101 unsorted [14:43:19.59] C:\test> [14:44:38.83] C:\test>head sorted key01 key01 xxxxxxxxxxxxx key01 key01 xxxxxxx key01 key01 x key01 key01 xxxxxxxx key01 key01 xxxxx key01 key01 xxxxxx key01 key01 xxxxxxxxxxxxxxxxx key01 key01 xxxxxx key01 key01 xx key01 key01 xxxxxxxxxx

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Science is about questioning the status quo. Questioning authority

Comment on Re^3: sorting type question- space problems
Download Code

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1054182]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (14)
As of 2014-11-26 14:10 GMT
Find Nodes?
    Voting Booth?

    My preferred Perl binaries come from:

    Results (171 votes), past polls