5163


Perlで下記のような構造を持つ配列があります。

[code]

    @array = ({
                id => '1',
               key => 'a'
              },
              {
                id => '2',
               key => 'b'
              },
              {
                id => '4',
               key => 'c',
            })
    
[/code]

ここで、`@array`に`id=4`が存在するかどうかを調べる際、例えば

[code]

    foreach my $x (@array){
      if($x->{id} == 4) ...
    }
    
[/code]

等として調べることが可能ですが、これでは処理回数が線形的に増え、効率的とは言えません。  
何かピンポイントで`id=4`を調べる良い方法は無いでしょうか。  
教えてください。よろしくお願いします。


CC BY-SA 3.0
2015-01-23T14:16:36.673
5160
2015-01-24T03:54:47.713
2015-01-24T03:54:47.713
49
7739
question
アルゴリズム perl
配列内のリストを効率よく走査するには


grepを使いましょう。可読性が高く、高速で直感的です。

[code]

    my @ar = grep { $_->{id} eq '4' } @{$array};
    
[/code]

リストコンテキストで使用すれば望みのデータだけを取り出す事ができます。

以下はベンチマークの結果です:

[code]

    use strict;
    use warnings;
    use Benchmark qw(cmpthese);
    
    my $array = [
        +{ id => '1', key => 'a' },
        +{ id => '2', key => 'b' },
        +{ id => '4', key => 'c' },
    ];
    
    cmpthese(1_000_000, +{
        foreach => sub {
            my @ar;
            foreach my $x (@{$array}) {
                if ($x->{id} eq '4') {
                    push @ar, $x;
                }
            };
        },
        grep => sub {
            my @ar = grep { $_->{id} eq '4' } @{$array};
        },
    });
    
    __END__
                 Rate foreach    grep
    foreach  869565/s      --    -38%
    grep    1408451/s     62%      --
    
[/code]


CC BY-SA 3.0
2015-01-23T14:37:29.477
5162
2015-01-23T15:09:25.010
2015-01-23T15:09:25.010
62
62
5160
answer


id から対応する配列の要素に対して効率的にアクセスしたいという質問だと思います。この場合、次のようなアプローチが考えられます。

  1. 事前に `id` をキー、インデックスを値とするハッシュを作成しておき、それを利用する。(検索コストは _O(1)_ 、メモリを食う)
  2. `@array` の中身を `id` の順に並べ替えておき、二分検索を行う (検索コストは _O(log_2 n)_ 、ソートが必要)

1のアプローチだと、次のようなコードになります。`%map` の値を無名配列へのリファレンスにすれば、複数の要素がある場合にも対応出来ます。

[code]

    use Data::Dumper;
    ...
    %map = map { ($array[$_]{id} => $_) } (0..$#array);
    $id = 4;
    print Dumper($array[$map{$id}])
    
[/code]

そもそものデータを見直して、`id` をキーとするハッシュとするのも良いかもしれません。


CC BY-SA 3.0
2015-01-23T14:50:00.730
5163
2015-01-23T14:50:00.730
76
5160
answer