in reply to Re^2: Pick k numbers at random
in thread Pick k numbers at random

Hello haukex,

just for fun a solution exploiting the randomness of hash keys.

   hkey => sub{
        my @range = (keys %{+{map {($_ => 1)}0 .. $N-1}})[0 .. $K-1];
   }

[download]

It is slightly faster than samp for very small sets..

perl randomshuffle.pl 10 5
          Rate  samp  hkey  shuf   mpu
samp  108393/s    --  -13%  -88%  -92%
hkey  124178/s   15%    --  -87%  -90%
shuf  934174/s  762%  652%    --  -27%
mpu  1275273/s 1077%  927%   37%    --

[download]
..but becomes fastly slower ;) for bigger ones. 
 
perl randomshuffle.pl 100 5
          Rate  hkey  samp  shuf   mpu
hkey   15844/s    --  -46%  -93%  -99%
samp   29546/s   86%    --  -86%  -98%
shuf  212991/s 1244%  621%    --  -86%
mpu  1519656/s 9491% 5043%  613%    --

[download]

The only thing to note is the %{+{ LIST }} syntax, where + is used to disambiguate a hashref from a block (credit: perl IRC channel) because you can't dereference a map as a hash.

PS: your hardware is ~3 times faster than mine ;)

PPS: "randperm" is not exported by the Math::Prime::Util module in 0.60 so i upgraded to 0.73

L*

There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

Replies are listed 'Best First'.
Re^4: Pick k numbers at random -- hash keys
by AnomalousMonk (Archbishop) on Nov 12, 2019 at 23:16 UTC

    For small hashes, ordering isn't necessarily "random" from one hash to the next: 

    c:\@Work\Perl\monks>perl -wMstrict -le
"for (1 .. 8) {
   my @k = keys %{ { map { $_ => 1 } 0 .. 8 } };
   print qq{@k};
   }
"
6 3 7 2 8 1 4 0 5
6 3 7 2 8 1 4 0 5
6 3 7 2 8 1 4 0 5
6 3 7 2 8 1 4 0 5
6 3 7 2 8 1 4 0 5
6 3 7 2 8 1 4 0 5
6 3 7 2 8 1 4 0 5
6 3 7 2 8 1 4 0 5

    [download]
    Same results under ActiveState 5.8.9 and Strawberry 5.14.4.1.

    Give a man a fish:  <%-{-{-{-<

[reply]
[d/l]
[select]
      For small hashes, ordering isn't necessarily "random" from one hash to the next

      I believe it's the version of perl that's important here.
      IIRC, with perl-5.16 and earlier the order was always repeated, but for later versions of perl the order varies at random (for some meaning of "at random").
      For example, with Strawberry Perl 5.18.2.1 your one liner produces for me: 
      0 4 5 3 2 8 1 7 6
3 5 0 4 6 7 1 8 2
7 6 2 8 1 5 3 0 4
6 7 8 1 2 5 3 0 4
7 6 2 8 1 5 3 4 0
3 5 0 4 6 7 1 8 2
7 6 2 1 8 5 3 0 4
3 5 4 0 7 6 2 1 8

      [download]
      and the output changes again when I re-run it.

      Interestingly, it's not strictly random - 0, 3, 4 and 5 always appear (in varying orders) either at the beginning or the end of the sequence.

      (I think it's still possible, via Configure args, to build perl with the pre-5.18 behaviour, though this is rarely done.)

      Cheers,
      Rob
[reply]
[d/l]
        Hello,

        also hash key randomness can be influenced (I don mean this is a wise thing to do..) by ENV vars, specifically PERL_PERTURB_KEYS and PERL_HASH_SEED

        perl -v

This is perl 5, version 26, subversion 0 (v5.26.0) built for MSWin32-x
+64-multi-thread

perl -wMstrict -le "for (1 .. 8) {my @k = keys %{ { map { $_ => 1 } 0 
+.. 8 } };print qq{@k};}"

2 8 5 3 0 1 4 6 7
2 0 8 5 3 1 6 4 7
2 4 7 6 1 3 8 5 0
1 4 7 6 0 8 5 3 2
2 0 8 5 3 1 7 6 4
4 7 6 1 3 5 8 0 2
3 8 5 0 6 4 7 1 2
0 5 8 3 1 6 4 7 2


set PERL_PERTURB_KEYS=0
set PERL_HASH_SEED=0x0


perl -wMstrict -le "for (1 .. 8) {my @k = keys %{ { map { $_ => 1 } 0 
+.. 8 } };print qq{@k};}"

6 7 5 2 3 1 0 8 4
6 7 5 2 3 1 0 8 4
6 7 5 2 3 1 0 8 4
6 7 5 2 3 1 0 8 4
6 7 5 2 3 1 0 8 4
6 7 5 2 3 1 0 8 4
6 7 5 2 3 1 0 8 4
6 7 5 2 3 1 0 8 4


set PERL_PERTURB_KEYS=
set PERL_HASH_SEED=

perl -wMstrict -le "for (1 .. 8) {my @k = keys %{ { map { $_ => 1 } 0 
+.. 8 } };print qq{@k};}"

2 8 4 1 6 0 3 5 7
3 5 7 8 2 4 1 6 0
5 3 7 4 1 2 8 0 6
4 1 2 8 0 6 5 3 7
7 3 5 6 0 2 8 4 1
5 3 7 1 4 2 8 0 6
7 5 3 0 6 4 1 8 2
7 3 5 6 0 8 2 1 4

        [download]

        see also PERL_HASH_SEED and PERL_PERTURB_KEYS both on perlrun and Algorithmic-Complexity-Attacks and order of hash and setting PERL_PERTURB_KEYS & PERL_HASH_SEED in a perl file

        L*

        There are no rules, there are no thumbs..
        Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.
[reply]
[d/l]
[select]
        > 0, 3, 4 and 5 always appear (in varying orders) either at the beginning or the end of the sequence.

        My guess: they all fall into the same bucket, so must be grouped together. But why is the bucketting always the same?

        map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
[reply]
[d/l]

In Section Seekers of Perl Wisdom