use warnings; use strict; use Benchmark ":all"; use IO::Handle; my %shuffle; use List::Util; $shuffle{"xs"} = \&List::Util::shuffle; $shuffle{"swap"} = sub { my @p = @_; my $k; $k = $_ + int(rand(@p - $_)), @p[$_, $k] = @p[$k, $_] for 0 .. @p - 1; @p; }; $shuffle{"map"} = sub { my @p = @_; map { splice @p, $_ + rand(@p - $_), 1, $p[$_] } 0 .. @p - 1; }; $shuffle{"shift"} = sub { my @p = @_; my $t; map { $t = splice @p, rand(@p), 1, $p[0]; shift @p; $t } 0 .. @p - 1; }; $shuffle{"weight"} = sub { my @w = map { rand } @_; @_[sort { $w[$a] <=> $w[$b] } 0 .. @_ - 1]; }; $shuffle{"schwartzian"} = sub { map { $$_[1] } sort { $$a[0] <=> $$b[0] } map { [rand, $_] } @_; }; if (0) { $shuffle{"bless"} = sub { map { $$_[0] } sort { ref $a <=> ref $b } map { bless [$_], rand } @_; }; } if (0) { my $N = 0 + ($ARGV[0] || 20); my $T = 0 + ($ARGV[1] || 1000); for my $n (keys(%shuffle)) { my %f; print $n; my $a = $shuffle{$n}; for (1 .. $T) { my @a = 1 .. $N; $f{join(" ", &$a(@a))}++; } for (sort keys(%f)) { printf "%5d: %s\n", $f{$_}, $_; } print 0+keys(%f), "\n\n"; } } my @sd; my %shtest = map { my($n, $a) = ($_, $shuffle{$_}); $n, sub { my @r = &$a(@sd); } } keys(%shuffle); for my $N (map { 1 + 2 * 3**$_ } 0 .. 8) { print "testing on $N elements\n"; @sd = my @sd0 = map { rand } 1 .. $N; cmpthese(-5, \%shtest); join(";", @sd) eq join(";", @sd0) or die "error: some of the shuffle functions have changed the array"; flush STDOUT; } print "done\n"; __END__ #### testing on 3 elements Rate schwartzian swap weight shift map xs schwartzian 131923/s -- -1% -15% -20% -23% -88% swap 133815/s 1% -- -13% -19% -22% -88% weight 154592/s 17% 16% -- -6% -10% -86% shift 165196/s 25% 23% 7% -- -4% -86% map 172130/s 30% 29% 11% 4% -- -85% xs 1140464/s 764% 752% 638% 590% 563% -- testing on 7 elements Rate schwartzian weight swap shift map xs schwartzian 61200/s -- -15% -20% -27% -29% -90% weight 72048/s 18% -- -5% -13% -17% -88% swap 76058/s 24% 6% -- -9% -12% -87% shift 83283/s 36% 16% 10% -- -4% -86% map 86718/s 42% 20% 14% 4% -- -85% xs 592396/s 868% 722% 679% 611% 583% -- testing on 19 elements Rate schwartzian weight swap shift map xs schwartzian 21339/s -- -15% -32% -33% -43% -91% weight 25214/s 18% -- -20% -21% -32% -90% swap 31452/s 47% 25% -- -2% -16% -87% shift 31957/s 50% 27% 2% -- -14% -87% map 37239/s 75% 48% 18% 17% -- -85% xs 243980/s 1043% 868% 676% 663% 555% -- testing on 55 elements Rate schwartzian weight swap shift map xs schwartzian 6790/s -- -17% -41% -42% -49% -92% weight 8154/s 20% -- -29% -30% -39% -90% swap 11492/s 69% 41% -- -1% -14% -86% shift 11650/s 72% 43% 1% -- -13% -86% map 13400/s 97% 64% 17% 15% -- -84% xs 83719/s 1133% 927% 628% 619% 525% -- testing on 163 elements Rate schwartzian weight shift swap map xs schwartzian 1902/s -- -19% -52% -52% -58% -93% weight 2356/s 24% -- -41% -41% -48% -92% shift 3982/s 109% 69% -- -0% -13% -86% swap 3998/s 110% 70% 0% -- -12% -86% map 4559/s 140% 93% 14% 14% -- -84% xs 28869/s 1418% 1125% 625% 622% 533% -- testing on 487 elements Rate schwartzian weight shift swap map xs schwartzian 515/s -- -20% -60% -61% -65% -95% weight 644/s 25% -- -50% -51% -56% -93% shift 1292/s 151% 101% -- -2% -12% -86% swap 1321/s 157% 105% 2% -- -10% -86% map 1467/s 185% 128% 14% 11% -- -84% xs 9413/s 1728% 1363% 629% 612% 542% -- testing on 1459 elements Rate schwartzian weight shift swap map xs schwartzian 121/s -- -28% -69% -70% -71% -95% weight 168/s 39% -- -57% -58% -59% -94% shift 396/s 226% 135% -- -1% -4% -85% swap 401/s 230% 138% 1% -- -3% -85% map 414/s 241% 146% 4% 3% -- -84% xs 2656/s 2088% 1477% 570% 563% 542% -- testing on 4375 elements Rate schwartzian weight map shift swap xs schwartzian 20.8/s -- -33% -71% -75% -76% -94% weight 31.1/s 50% -- -57% -63% -64% -92% map 72.6/s 249% 133% -- -14% -16% -81% shift 84.7/s 307% 172% 17% -- -2% -77% swap 86.6/s 317% 178% 19% 2% -- -77% xs 376/s 1709% 1108% 418% 344% 334% -- testing on 13123 elements Rate schwartzian weight map shift swap xs schwartzian 4.46/s -- -28% -72% -73% -76% -95% weight 6.18/s 39% -- -61% -63% -67% -92% map 15.7/s 252% 154% -- -6% -16% -81% shift 16.8/s 277% 172% 7% -- -10% -80% swap 18.7/s 319% 203% 19% 11% -- -77% xs 82.0/s 1739% 1227% 422% 388% 339% -- done