#!/usr/local/bin/perl -w

use Benchmark qw(cmpthese);
use List::Util qw(shuffle);
use Time::HiRes qw(gettimeofday tv_interval);

@matrix = 1..20_000_000;          # big enough
$t0 = [gettimeofday];
@smatrix = shuffle(@matrix);
$elapsed = tv_interval ( $t0 );
print "El tiempo fijo de sin_r_con_shuffle es $elapsed\n";

cmpthese(-1, {
		 'con_reemplaz' => sub {
		     $x = return $matrix[int rand(@matrix)];
		 },
		 'sin_reemplaz' => sub {
		     $x = return sinreemplazamiento();
		 },
		 'sin_reemp_2' => sub {
		     $x = return sinreemp();
		 },
		 'sin_r_con_shuffle' => sub {
		     $x = return pop(@smatrix); 
		 },
		 'splice' => sub {
		     $x = return extract();
		 },
#		 'extract_r' => sub {   WRONG!
#		     extract_r();
#		 },
	     });

sub sinreemplazamiento{               # WINNER
#    if (@matrix){
	$ind = int rand (@matrix);
	($matrix[$ind],$matrix[-1]) = ($matrix[-1],$matrix[$ind]); 
	return pop @matrix;
#    }else{
#	return undef;
#    }
}

sub sinreemp{
    my $ind = int rand @matrix;
    @matrix[$ind,-1] = @matrix[-1,$ind];
    return pop @matrix;
}

sub extract {                     # too slow
    my $index = int rand(@matrix);
    return splice(@matrix, $index, 1);
}

sub extract_r {                   # WRONG
    my $ind = int rand @matrix;
    my $rv = $matrix[$ind];
    $matrix[$ind] = pop @matrix;             # not valid, $ind could be == $#matrix
    return $rv;
}


__END__
  
Esto es una comparación de cuánto más cuesta extraer aleatorios sin
  posibilidad de repetición sobre el caso normal. La tercera posibilidad
  es hacer la trampa de barajar la matriz entera e ir extrayendo, pero 
  esto sólo merecerá la pena si se van a extraer muchos elementos.

BUGS
No estoy muy seguro de que no haya otros algoritmos mejores o que la
  comparación este bien hecha, dado que depende del % a extraer de la 
  matriz.