#! perl -slw
use strict;
use Math::Random::Mt qw[ rand ];

our $N ||= 40e6;
our $K ||= $N / 2;

## In-place FY shuffle of a packed ULONG array
sub shuffle {
    my $ref = shift;
    my $n = length( $$ref ) >> 2;
    for( 0 .. $n ) {
        my $p = $_ + int( rand $n - $_ );
        my $tmp = substr $$ref, $_*4, 4;
        substr $$ref, $_*4, 4, substr $$ref, $p*4, 4;
        substr $$ref, $p*4, 4, $tmp;
    }
    return;
}

## Allocate a packed array of $N Ulongs
my $index = \ (chr(0) x ( 4 * $N ));

## Populate it
substr $$index, $_*4, 4, pack 'V', $_  for 0 .. $N - 1;

## Shuffle in place
shuffle $index;

## Allocate a bit-vector for linear sort
my $ordered = chr(0) x int( ( $N +7 ) / 8 );

## Linear sort
vec( $ordered, unpack( 'V', substr $$index, $_*4, 4 ), 1 ) = 1
    for 0 .. $K - 1;

## Read the file line by line
while( <> ) {
    ## print it if it was picked
    print if vec( $ordered, $., 1 );
}