高速にリストからハッシュにする

Perl

いまいちピンとくる言い方が分からないけれど，つまりはこういうこと．

[
    {
        id => 1,
        value => 'foo',
    },
    {
        id => 2,
        value => 'bar',
    },
]

このようなデータ構造があったときに，以下のようにidをkeyとしてハッシュにしたい．

{
    1 => {
       id => 1,
       value => 'foo',
    },
    2 => {
       id => 2,
       value => 'bar',
    }
}

割とよくあることなので，普段はmapを使ってこのように書いている．

my $x = +{map { ($_->{id} => $_) } @users};

これは，List::Utilのreduceを使っても同じように書ける．引数の先頭がハッシュリファレンスになっていて，それを引き回すことで実現している．

use List::Util qw/reduce/;
my $x = reduce { $a->{$b->{id}} = $b; $a } ({}, @users);

実は，reduceで書いたコードはmapよりも40%程度ではあるが若干早く動作する．一見mapのほうがシンプルで値を返しているだけなので早く動作するように見えるがそうではない．

気になったのでList::Utilのコードを見てみたところ，lightweight callbackを使って実装されていた．

https://metacpan.org/source/PEVANS/Scalar-List-Utils-1.46/ListUtil.xs#L370-430

lightweight callbackについてはperldoc perlcallに少しだけではあるがドキュメントが存在する．ループ中に同じ関数を何度も呼び出すようなケースに使う．

reduceで書いたコードが早いのはlightweight callbackのおかげらしい．ということで，List::Utilのコードを参考に，lightweight callbackを使って高速にリストからハッシュにする処理を書いてみた．

github.com

名前が思い付かなかったのでそのままto_hashに……

  • List::Utilのコードはコアモジュールだからかポータブルな実装．ifdefたくさん．
  • $_はGvSV(PL_defgv)
  • 返り値は関数呼び出し後に*PL_stack_spを参照
  • Perlのハッシュは，キーにundefを指定することができない(空文字列になる)

ベンチマークは以下の通り．

use strict;
use warnings;
use Benchmark qw/:all/;
use List::ToHash;
use List::Util;

my @ARRAY;
for my $i (1..100) {
    push @ARRAY, {
        id    => $i,
        value => '.' x 100,
    };
}

cmpthese(timethese(0, {
    map => sub {
        my $x = +{map { ($_->{id} => $_) } @ARRAY};
    },
    reduce => sub {
        my $x = List::Util::reduce { $a->{$b->{id}} = $b; $a } ({}, @ARRAY);
    },
    for => sub {
        my $x = {};
        $x->{$_->{id}} = $_ for @ARRAY;
        $x;
    },
    to_hash => sub {
        my $x = List::ToHash::to_hash { $_->{id} } @ARRAY;
    },
}));

Benchmark: running for, map, reduce, to_hash for at least 3 CPU seconds...
       for:  3 wallclock secs ( 3.18 usr +  0.01 sys =  3.19 CPU) @ 19303.13/s (n=61577)
       map:  3 wallclock secs ( 3.13 usr +  0.02 sys =  3.15 CPU) @ 13437.46/s (n=42328)
    reduce:  3 wallclock secs ( 3.20 usr +  0.02 sys =  3.22 CPU) @ 18504.66/s (n=59585)
   to_hash:  4 wallclock secs ( 3.12 usr +  0.01 sys =  3.13 CPU) @ 26635.78/s (n=83370)
           Rate     map  reduce     for to_hash
map     13437/s      --    -27%    -30%    -50%
reduce  18505/s     38%      --     -4%    -31%
for     19303/s     44%      4%      --    -28%
to_hash 26636/s     98%     44%     38%      --

結果としては，mapよりも2倍早く処理することができた．ただこの程度であれば微々たる差のように見える．結局はmap使っておけば良さそう．