Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re^3: Fastest way to "pick without replacement"

by swl (Priest)
on Nov 23, 2020 at 01:27 UTC ( #11124041=note: print w/replies, xml ) Need Help??


in reply to Re^2: Fastest way to "pick without replacement"
in thread Fastest way to "pick without replacement"

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% --

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://11124041]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (5)
As of 2021-04-15 01:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?