Perl: the Markov chain saw PerlMonks

### Re: better array to hash conversion

by ruzam (Curate)
 on Dec 11, 2012 at 14:06 UTC ( #1008307=note: print w/replies, xml ) Need Help??

in reply to better array to hash conversion

A little bench-marking can be helpful. For the case of converting an array to a hash where the array values become keys and the array index become values.

I've bench-marked the OP code as well as the variations presented in response, in addition I added my own solution to the problem (variation3). The clear winner is variation1.

```my %hash; @hash{ @array } = 0 .. \$#array;
```#!/usr/bin/env perl
use strict;
use warnings;

use Benchmark qw(:all);

my @array=qw(a b c d e f g h);

sub original {
my %hash;
for (my \$idx=0; \$idx<@array; \$idx++) { \$hash{\$array[\$idx]} = \$idx;}
}

sub variation1 {
my %hash;
@hash{ @array } = 0 .. \$#array;
}

sub variation2 {
my %hash = map { \$array[\$_] => \$_ } 0..\$#array;
}

sub variation3 {
my \$idx = 0;
my %hash = map { \$_ => \$idx++ } @array;
}

cmpthese(-10, {
'original' => sub{
original()
},
'variation1' => sub{
variation1()
},
'variation2' => sub{
variation2()
},
'variation3' => sub{
variation3()
},
});
results:
```               Rate variation2 variation3   original variation1
variation2 142570/s         --       -15%       -35%       -49%
variation3 168018/s        18%         --       -24%       -40%
original   220185/s        54%        31%         --       -21%
variation1 279147/s        96%        66%        27%         --

Replies are listed 'Best First'.
Re^2: better array to hash conversion
by BrowserUk (Pope) on Dec 11, 2012 at 14:41 UTC

As the array size grows, it doesn't take long for the OPs original to out pace variation1. It only requires a 200,000 or so for that to happen, and the benefits mount geometrically as the array size grows:

```#!/usr/bin/env perl
use strict;
use warnings;
use Benchmark qw(:all);

our @array = 'aaaa' .. 'lzzz';
print "\$#array\n";

sub original {
my %hash;
for (my \$idx=0; \$idx<@array; \$idx++) { \$hash{\$array[\$idx]} = \$idx;}
}

sub variation1 {
my %hash;
@hash{ @array } = 0 .. \$#array;
}

sub variation2 {
my %hash = map { \$array[\$_] => \$_ } 0..\$#array;
}

sub variation3 {
my \$idx = 0;
my %hash = map { \$_ => \$idx++ } @array;
}

sub variation4 {
my \$idx = 0;
my %hash; \$hash{ \$_ } = \$idx++ for @array;
}

cmpthese -5, {
'original'   => \&original,
'variation1' => \&variation1,
'variation2' => \&variation2,
'variation3' => \&variation3,
'variation4' => \&variation4,
};

__END__
C:\test>junk91
210911
Rate variation2 variation3 variation1   original variatio
+n4
variation2 2.08/s         --        -2%       -36%       -38%       -4
+2%
variation3 2.12/s         2%         --       -35%       -37%       -4
+1%
variation1 3.26/s        57%        54%         --        -3%        -
+9%
original   3.37/s        62%        59%         3%         --        -
+6%
variation4 3.57/s        72%        68%         9%         6%
+--

(I've added another variation that works better for large arrays.)

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

This is very interesting. Do you know why - and like to explain it?

Thanks and best regards, Karl

«The Crux of the Biscuit is the Apostrophe»

Because all of the map-based methods construct, copy and later discard, multiple, intermediary lists on their way to constructing the hash.

And the costs of doing large numbers of small memory allocations and deallocations add up; especially if they memory manager has to go to the OS a couple of times to expand the process memory pool.

Using for avoids constructing many of the intermediary lists.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re^2: better array to hash conversion
by GrandFather (Sage) on Dec 11, 2012 at 20:10 UTC

This is premature optimisation gone mad! For most purposes for speed to be a factor in this decision the array would need to contain of the order of 1 million entries.

Sure, benchmarks are fun to write (although often hard to make meaningful), but the overwhelming criteria in this sort of coding decision is clarity and maintainability of the code. By that metric on both counts 'original' is way down the list. I'd go for variation 1 or a for modifier version of 'original', either of which is clear, succinct and not particularly prone to coding errors.

True laziness is hard work
This is premature optimisation gone mad! For most purposes for speed to be a factor in this decision the array would need to contain of the order of 1 million entries.

Actually, significant differences start at around 200,000; and as someone who regularly does similar processing with 10s and even 100s of millions, knowing what works quickest whilst avoiding unnecessary memory growth is important.

And unless you have some psychic insight to the OPs application, you have nothing on which to base your conclusions, so it is they that are "premature".

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re^2: better array to hash conversion
by perltux (Monk) on Dec 11, 2012 at 14:27 UTC
Many thanks for that. I find it very interesting that the 'for' loop is actually the second fastest solution, faster than the solutions using 'map'.

A for solution is generally faster than a map, and it has been discussed in map versus for amongst other places. Sometimes however it is more expressive to use "map".

A Monk aims to give answers to those who have none, and to learn from those who know more.
Re^2: better array to hash conversion
by Anonymous Monk on Dec 11, 2012 at 19:09 UTC

presize/preallocate buckets , change the number of elements, change the perl version, and the winner changes :)

funny bench :)

```#!/usr/bin/perl --
use strict; use warnings;
use Benchmark qw/ cmpthese /;

#~ my \$cmptime = -abs(shift);
#~ my \$cmptime = -3;
my \$cmptime = -10;
printf "%10s cmptime %s\n", \$], \$cmptime;
my @array;
for my \$power ( 8, 16,18 ) {
#~ for my \$power ( 8, 16, 20, 24 ){
@array = 1 .. ( 2**\$power );
print "2 ** \$power == @{[int @array ]}\n";
cmpthese(
\$cmptime, {
map { ; \$_ => __PACKAGE__->can( \$_ ) }
qw/ ffor fforc
ifor imap mmap
sffor sfforc sifor simap
slic smap simap2
/
}
);
}
exit;

sub mmap {
my %hash = map { ; \$array[\$_] => \$_ } 0 .. \$#array;
();
}

sub imap {
my \$ix = 0;
my %hash = map { ; \$_ => \$ix++ } @array;
();
}
sub slic { my %hash; @hash{@array} = 0 .. \$#array; (); }

sub ffor {
my %hash;
for my \$ix ( 0 .. \$#array ) { \$hash{ \$array[\$ix] } = \$ix; }
();
}

sub fforc {
my %hash;
for( my \$ix = 0 ; \$ix < @array ; \$ix++ ) { \$hash{ \$array[\$ix] } =
+\$ix; }
();
}

sub ifor {
my %hash;
my \$ix = 0;
\$hash{\$_} = \$ix++ for @array;
();
}

## preSize
sub sffor {
my %hash;
keys( %hash ) = int @array;
for my \$ix ( 0 .. \$#array ) { \$hash{ \$array[\$ix] } = \$ix; }
();
}

sub sfforc {
my %hash;
keys( %hash ) = int @array;
for( my \$ix = 0 ; \$ix < @array ; \$ix++ ) { \$hash{ \$array[\$ix] } =
+\$ix; }
();
}

sub sifor {
my %hash;
my \$ix = 0;
keys( %hash ) = int @array;
\$hash{\$_} = \$ix++ for @array;
();
}

sub smap {
my %hash;
keys( %hash ) = int @array;
@hash{@array} = 0 .. \$#array;
();
}

sub simap {
my \$i = 0;
my %hash;
keys( %hash ) = int @array;
%hash = map { \$_ => \$i++ } @array;
();
}

sub simap2 {
my \$i = 0;
my %hash;
keys( %hash ) = int @array;
%hash = map(( \$_ => \$i++ ), @array);
();
}

__END__

funny results :)

Create A New User
Node Status?
node history
Node Type: note [id://1008307]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (5)
As of 2018-04-21 17:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (81 votes). Check out past polls.

Notices?