in reply to Fastest way to "pick without replacement"

Thank you for the replies everyone! I've put all the solutions together here - I've kept the behavior of deleting only a single value, but the comparison with deleting multiple indicies by choroba here is very interesting too! I've included Eily's solution that leaves the array out of its original order too.

use warnings;
use strict;
use Benchmark qw/cmpthese/;

my @numbers = ( 'a'..'t' );
my $index = 3;
my $expect = 'abcefghijklmnopqrst';
use constant TEST => 0;

cmpthese(-2, {
    splice => sub {
        my @output = @numbers;
        splice @output, $index, 1;
        join("", @output) eq $expect or die if TEST;
    },
    grep => sub { # choroba
        my @output = @numbers[ grep $_ != $index, 0 .. $#numbers ];
        join("", @output) eq $expect or die if TEST;
    },
    slice => sub { # hippo
        my @output = @numbers[ 0..$index-1, $index+1..$#numbers ];
        join("", @output) eq $expect or die if TEST;
    },
    hash => sub { # bliako
        my %ha; @ha{0..$#numbers} = @numbers;
        delete $ha{$index};
        my @output = map { $ha{$_} } sort {$a <=> $b} keys %ha;
        join("", @output) eq $expect or die if TEST;
    },
    hash_slice => sub { # swl
        my %ha; @ha{0..$#numbers} = @numbers;
        delete $ha{$index};
        my @output = @ha{ sort {$a <=> $b} keys %ha };
        join("", @output) eq $expect or die if TEST;
    },
    swap => sub { # Eily
        my @output = @numbers;
        $output[$index] = pop @output;
        join("", sort @output) eq $expect or die if TEST;
    },
    pop_sort => sub { # Eily's + sort
        my @output = @numbers;
        $output[$index] = pop @output;
        @output = sort @output;
        join("", @output) eq $expect or die if TEST;
    },
});

__END__

               Rate     hash hash_slice    grep pop_sort   slice    sw
+ap  splice
hash       113253/s       --       -10%    -78%     -82%    -84%    -8
+7%    -87%
hash_slice 126029/s      11%         --    -76%     -80%    -83%    -8
+5%    -86%
grep       518838/s     358%       312%      --     -17%    -28%    -3
+9%    -41%
pop_sort   627138/s     454%       398%     21%       --    -14%    -2
+6%    -28%
slice      725216/s     540%       475%     40%      16%      --    -1
+4%    -17%
swap       846179/s     647%       571%     63%      35%     17%      
+--     -3%
splice     873809/s     672%       593%     68%      39%     20%      
+3%      --

[download]

Replies are listed 'Best First'.
Re^2: Fastest way to "pick without replacement"
by haukex (Archbishop) on Nov 21, 2020 at 12:11 UTC

    I was curious if storing the values in a hash in the first place might be better. Turns out, no, even if the output is a hash as well.

    use warnings;
use strict;
use Benchmark qw/cmpthese/;

my @array = ( 'a'..'t' );
my %hash = map { $_ => $array[$_] } 0..$#array;
my $index = 3;
my $expect = 'abcefghijklmnopqrst';
use constant TEST => 0;

cmpthese(-2, {
    splice => sub {
        my @output = @array;
        splice @output, $index, 1;
        join("", @output) eq $expect or die if TEST;
    },
    hash_slice => sub {
        my %ha; @ha{0..$#array} = @array;
        delete $ha{$index};
        my @output = @ha{ sort {$a <=> $b} keys %ha };
        join("", @output) eq $expect or die if TEST;
    },
    swap => sub {
        my @output = @array;
        $output[$index] = pop @output;
        join("", sort @output) eq $expect or die if TEST;
    },
    prehash_del => sub {
        my %ha = %hash;
        delete $ha{$index};
        my @output = @ha{ sort {$a <=> $b} keys %ha };
        join("", @output) eq $expect or die if TEST;
    },
    prehash_local => sub {
        delete local $hash{$index};
        my @output = @hash{ sort {$a <=> $b} keys %hash };
        join("", @output) eq $expect or die if TEST;
    },
    prehash_grep => sub {
        my @output = @hash{ sort {$a <=> $b}
            grep { $_ != $index } keys %hash };
        join("", @output) eq $expect or die if TEST;
    },
    outhash => sub {
        my %output = %hash;
        delete $output{$index};
        join("", @output{ sort {$a <=> $b} keys %output }) eq $expect
            or die if TEST;
    },
});

__END__

                  Rate hash_slice prehash_del prehash_local prehash_gr
+ep outhash swap splice
hash_slice    127891/s         --        -10%          -40%         -5
+0%    -68% -85%   -85%
prehash_del   142822/s        12%          --          -33%         -4
+5%    -64% -83%   -84%
prehash_local 214633/s        68%         50%            --         -1
+7%    -46% -75%   -75%
prehash_grep  258191/s       102%         81%           20%           
+--    -36% -70%   -70%
outhash       400518/s       213%        180%           87%          5
+5%      -- -53%   -54%
swap          847448/s       563%        493%          295%         22
+8%    112%   --    -2%
splice        868423/s       579%        508%          305%         23
+6%    117%   2%     --

    [download]
[reply]
[d/l]

      Out of interest, I ran the code through Devel::NYTProf, setting the number of iterations to 200,000. The sort functions in the hash-based methods are the main slow-points, with populating the hash coming a close second (i.e. @ha{0..$#array} = @array;).

      haukex has already shown that pre-initialising the hash does not change the order by much.

      Another point is that the hash slice subs don't need to get the results using a slice - they can just get the values directly.

      The code below adds two subs that sort the values call on %ha.

      When run on my system (Strawberry perl 5.28) both variants are about 20%-25% faster than their respective originals. The top few subs are, unsurprisingly, unchanged. I have not done prehash_local but would expect the same relative difference.

      use warnings;
use strict;
use Benchmark qw/cmpthese/;

my @array = ( 'a'..'t' );
my %hash = map { $_ => $array[$_] } 0..$#array;
my $index = 3;
my $expect = 'abcefghijklmnopqrst';
use constant TEST => 0;

cmpthese(-2, {
    splice => sub {
        my @output = @array;
        splice @output, $index, 1;
        join("", @output) eq $expect or die if TEST;
    },
    hash_slice => sub {
        my %ha; @ha{0..$#array} = @array;
        delete $ha{$index};
        my @output = @ha{ sort {$a <=> $b} keys %ha };
        join("", @output) eq $expect or die if TEST;
    },
    h_slice_2 => sub {
        my %ha; @ha{0..$#array} = @array;
        delete $ha{$index};
        my @output = sort values %ha;
        join("", @output) eq $expect or die if TEST;
    },
    swap => sub {
        my @output = @array;
        $output[$index] = pop @output;
        join("", sort @output) eq $expect or die if TEST;
    },
    prehash_del => sub {
        my %ha = %hash;
        delete $ha{$index};
        my @output = @ha{ sort {$a <=> $b} keys %ha };
        join("", @output) eq $expect or die if TEST;
    },
    prehash_del_2 => sub {
        my %ha = %hash;
        delete $ha{$index};
        my @output = sort values %ha;
        join("", @output) eq $expect or die if TEST;
    },
    prehash_local => sub {
        delete local $hash{$index};
        my @output = @hash{ sort {$a <=> $b} keys %hash };
        join("", @output) eq $expect or die if TEST;
    },
    prehash_grep => sub {
        my @output = @hash{ sort {$a <=> $b}
            grep { $_ != $index } keys %hash };
        join("", @output) eq $expect or die if TEST;
    },
    outhash => sub {
        my %output = %hash;
        delete $output{$index};
        join("", @output{ sort {$a <=> $b} keys %output }) eq $expect
            or die if TEST;
    },
});

__END__

                  Rate hash_slice h_slice_2 prehash_del prehash_del_2 
+prehash_local prehash_grep outhash swap splice
hash_slice     50341/s         --      -20%        -21%          -36% 
+         -52%         -59%    -67% -79%   -79%
h_slice_2      62792/s        25%        --         -2%          -20% 
+         -40%         -48%    -58% -74%   -74%
prehash_del    63796/s        27%        2%          --          -19% 
+         -39%         -48%    -58% -74%   -74%
prehash_del_2  78613/s        56%       25%         23%            -- 
+         -25%         -35%    -48% -68%   -68%
prehash_local 104733/s       108%       67%         64%           33% 
+           --         -14%    -31% -57%   -57%
prehash_grep  121518/s       141%       94%         90%           55% 
+          16%           --    -19% -50%   -50%
outhash       150826/s       200%      140%        136%           92% 
+          44%          24%      -- -38%   -38%
swap          243449/s       384%      288%        282%          210% 
+         132%         100%     61%   --    -1%
splice        244776/s       386%      290%        284%          211% 
+         134%         101%     62%   1%     --

      [download]
[reply]
[d/l]
[select]
      My guess is that using a bit-string is the fastest approach.

      Every set bit would represent a used number. °

      Of course this would mean that the overall algorithm needs to be adjusted ...

      Anyway in my experience you are doing micro-optimization here, the exponential growth of the search space makes better bound conditions to cut sub-trees far more important than tuning Perl.

      Cheers Rolf
      (addicted to the Perl Programming Language :)
      Wikisyntax for the Monastery

      °) the strings can't get that big, a result set for 32 input numbers would already be beyond limits.

[reply]
        Anyway in my experience you are doing micro-optimization here

        This was mostly to satisfy my curiosity and perhaps provide an interesting challenge, I'm not really optimizing anything - I always had a gut feeling that splice might be kind of slow (and it probably still is on very large arrays), so it's nice to see that in this test it's actually quite the opposite.

[reply]

In Section Seekers of Perl Wisdom