Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re: Random sampling a variable record-length file.

by pajout (Curate)
on Dec 30, 2009 at 13:35 UTC ( #814938=note: print w/ replies, xml ) Need Help??


in reply to Random sampling a variable record-length file.

I see following algorithm, assuming ~10G file of records of 50-150 bytes, which ordering/length can be somehow dependent:

1. Estimate count of records in result sample: $n = 1000; 2. Estimate count of records in "primar" sample: $p = $n * 100; 3. Generate array of byte positions @pos, uniformly distributed in int +erval [1, length of file], satisfying condition $p == @pos; 4. If it is worth for seeking in the file, sort @pos. 5. my @res; my %res; 6. foreach @pos 6.1 read the record starting behind $_-th byte and remember $start, wh +ich is position of the first byte of the record in the file 6.2 next if exists $res{$start}; 6.3 $res{$start} = 1; 6.4 my $rand = some_uniform_rand()/($start - $_). It is crucial step - + IF ordering of records is somehow dependent on record length, it can + normalize it. Records following longer records have lowered probabil +ity to be inserted into @res. 6.5 if $n < @res insert {weight => $rand, rec => $record} into @res, keeping asc +ending order by weight 6.6 elsif $rand > $rec[0]{weight} shift @rec and insert {weight => $rand, rec => $record} into @r +es, keeping ascending order by weight 7. you have @res
UPDATE: 6.5 if $n > @res


Comment on Re: Random sampling a variable record-length file.
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (6)
As of 2015-07-07 09:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (88 votes), past polls