perlで配列の検索を高速化したい
配列内に要素があるかないか判定したい。 でも頭から検索しにいくから 後にある検索は遅くなってしまう。
use strict; use warnings; use List::Util qw/first/; use Benchmark qw/timethese cmpthese/; my @ids = (0 .. 1000000); timethese(1000,{ first => sub { my $first = first {$_ == 0} @ids; }, mid => sub { my $mid = first {$_ == 500000} @ids; }, last => sub { my $last = first {$_ == 1000000} @ids; } });
Benchmark: timing 1000 iterations of first, last, mid... first: 4 wallclock secs ( 3.27 usr + 0.00 sys = 3.27 CPU) @ 306.28/s (n=1000) last: 65 wallclock secs (62.56 usr + 0.03 sys = 62.59 CPU) @ 15.98/s (n=1000) mid: 34 wallclock secs (32.91 usr + 0.00 sys = 32.91 CPU) @ 30.39/s (n=1000)
そんなときは、ハッシュに詰めればいいとperlprefに書いてあって わかるんですが、配列から値1のハッシュを 作成するのはどうすればいいのだろうか。
@ids = (0 1 2 3); #↓を一発で作成したい。 %ids = ( 0 =>1, 1=>1, 2=>1, 3=>1);
早速、コメント(xtetsujiさん)とツイートをいただきました
@dokechin %ids = map { ($_ => 1) } @list;
— Daisuke Maki (@lestrrat) August 22, 2013
use strict; use warnings; use List::Util qw/first/; use Benchmark qw/timethese cmpthese/; my @ids = (0 .. 1000000); my %idh = map { $_=> 1} @ids; timethese(10,{ first => sub { my $first = first {$_ == 0} @ids; }, mid => sub { my $mid = first {$_ == 500000} @ids; }, last => sub { my $last = first {$_ == 1000000} @ids; }, hash_first => sub { my $first = $idh{0}; }, hash_mid => sub { my $mid = $idh{500000}; }, hash_last => sub { my $last = $idh{1000000}; } });
Benchmark: timing 10 iterations of first, hash_first, hash_last, hash_mid, last, mid... first: 0 wallclock secs ( 0.05 usr + 0.00 sys = 0.05 CPU) @ 212.77/s (n=10) (warning: too few iterations for a reliable count) hash_first: 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU) (warning: too few iterations for a reliable count) hash_last: 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU) (warning: too few iterations for a reliable count) hash_mid: 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU) (warning: too few iterations for a reliable count) last: 4 wallclock secs ( 3.73 usr + 0.00 sys = 3.73 CPU) @ 2.68/s (n=10) mid: 2 wallclock secs ( 1.92 usr + 0.00 sys = 1.92 CPU) @ 5.21/s (n=10)
配列からマップを作ることができるんですねぇ!! ほんと、自分の頭の固さを痛感しました。 なぞが解けてすっきりしました。