Ermitejo - エスペラント語日本語翻訳

#BLOGO
開発機の故障によるErmitejoの開発停止 >
2009/3/31

Perlでルックアップテーブルを1センテンスで書くには

分類: 開発記 / タグ:

組み込みハッシュを持つPerlは(そして、他のP言語でも)、ルックアップテーブルが非常に役に立ちます。慣用句(idiom)なだけに短く書きたいは思いますが、結局無理して短く書いてもいいことがないという結論に落ち着きました。

ルックアップテーブルの使い道

例えば、或る一方の配列@barに含まれる、他方の配列@fooと同じ要素について何か処理をしたい場合、端的には多重foreachで書けないことはありません。

FOO:
foreach my $item_in_foo (@foo) {
    next FOO
        unless defined $item_in_foo;
    # undefはeq出来ないので。単純に比較するだけならこうする。
    # undefの値を何かに使いたいなら、definedチェックはBARループのif文に入れる

    BAR:
    foreach my $item_in_bar (@bar) {
        next BAR
            unless defined $item_in_bar; # 上の注記に同じ。
        if ($item_in_foo eq $item_in_bar) {
            # ... any process
            last BAR;
        }
    }
}

しかし、普通はそのように冗長なことはせずに、

my %seen;
@seen{@foo} = ();

BAR:
foreach my $item_in_bar (@bar) {
    next BAR
        unless defined $item_in_bar;
    if (exists $seen{$item_in_bar}) {
        # any process ...
    }
}

で済みます。

配列@foo@barのサイズ(長さ)が共にNとすると、二重にforeachするとO = N2オーダーの計算量が必要になります。一方でハッシュの探索は(疑似的に)O = 1オーダーで済みます。

上記の例ならList::CompareSet::Scalarを使って集合演算する手もありますが、@barに相当する物がなくて都度処理する必要がある場合には、まず@barに相当する配列をでっち上げなければなりません。

テーブルをいかに作るべきか

ということでルックアップテーブルはクックブックでも紹介されるほどの常套句なのですが、面倒くさがりの私は、このルックアップテーブルを作成する処理でも手を抜きたいと思っていました。

教科書的な手法

my @foo = qw(a b c);

のように、配列@fooが所与のものであった場合、ルックアップテーブルの作成には

my %seen;
@seen{@foo} = ();

と、2ステートメントが必要です。

勿論、undef @seen{@foo};のように空リストを突っ込まなくても構いません(後で掲げるベンチマークでは、ほぼ互角の効率です)。

ともあれ、何度も使うイディオムなのに、2ステートメントを費やすのが気に食いません。Perlを触って6年経ちますが、未だにこうした初歩的な点を未解決にしたままここまで来てしまいました。

mapを使う手法

例えば1行で書こうと思えば書けますが、

my %seen = map {$_, undef} @foo;

これはmap BLOCK LISTBLOCK部分を別ステップとして勘定に入れた方がフェアなような気がします。それこそステートメントではなく1「行」で書こうとすればmy %seen; undef @bar{@foo};というようにコードフォーマッティング作法上の反則も出来ますが、きりがないのでやめておきます。

なお、my %seen = map ( ($_, undef), @foo);という、map EXPR LIST方式は推奨しないと、D. Conway先生が『Perlベストプラクティス』で言及しています。

変態的な手法

さて、何かスマートな書き方はないものでしょうか。
そこで、二つの互いに関連する配列からハッシュをでっち上げるときの常套句である、List::MoreUtilsmesh(別名zip)も試してみましょう。

二つの互いに関連する……というのは、つまりこういうことです。

use List::MoreUtils qw(mesh);
my @prefectures = qw(北海道 青森県 岩手県 宮城県);
my @cities      = qw(札幌   青森   盛岡   仙台);
my %the_seat_of_the_prefectural_government = mesh @prefectures, @cities;

これをforeachで回すのは、いかにもかったるいですね。

my @prefectures = qw(北海道 青森県 岩手県 宮城県);
my @cities      = qw(札幌   青森   盛岡   仙台);
my %the_seat_of_the_prefectural_government;
foreach my $index (0 .. $#prefectures) {
    $the_seat_of_the_prefectural_government{$prefectures[$index]} = $cities[$index];
}

ということでmeshですが、これはLISTではなくARRAYを食わせる必要があるので、以下のようにします。

# my %seen = mesh @foo, (); # error!
my %seen = mesh @foo, @{[]}

だんだん変態的なコードになってきました。D. Conway先生曰くところの「名誉標準モジュール」といってもいいくらいだとはいえ、やはり組み込み関数やコアモジュールで何とかしたいという思いもあります。

結論:普通が一番

結局、色々考えるよりも、ベンチマークしてみたら一目瞭然でした。オペコードを眺めるまでもないですね。

#! /usr/local/bin/perl

use strict;
use warnings;

use Benchmark qw(timethese cmpthese);
use List::MoreUtils qw(mesh);

my $count = 5_000_000;
my @foo   = qw(a b c);

cmpthese(
    timethese(
        $count,
        {
            'undef'         => sub { my %seen; undef @seen{@foo};     },
            'empty'         => sub { my %seen; @seen{@foo} = ();      },
            # 'filled'      => sub { my %seen; @seen{@foo} = @foo;    },
            'map'           => sub { my %seen = map {$_, undef} @foo; },
            'mesh_undef'    => sub { my %seen = mesh @foo, @{[]};     },
            # 'mesh_filled' => sub { my %seen = mesh @foo, @foo;      },
        }
    )
);
Benchmark: timing 5000000 iterations of empty, map, mesh_undef, undef...
     empty:  6 wallclock secs ( 6.30 usr +  0.00 sys =  6.30 CPU) @ 794028.90/s (n=5000000)
       map: 25 wallclock secs (24.70 usr +  0.00 sys = 24.70 CPU) @ 202396.37/s (n=5000000)
mesh_undef: 30 wallclock secs (30.24 usr +  0.00 sys = 30.24 CPU) @ 165371.26/s (n=5000000)
     undef:  6 wallclock secs ( 6.00 usr +  0.00 sys =  6.00 CPU) @ 833333.33/s (n=5000000)
               Rate mesh_undef        map      empty      undef
mesh_undef 165371/s         --       -18%       -79%       -80%
map        202396/s        22%         --       -75%       -76%
empty      794029/s       380%       292%         --        -5%
undef      833333/s       404%       312%         5%         --

いやはや、無理して1センテンスで書くのはやめようと思います。

List::UtilList::MoreUtilsは、確かに先生の指摘するように「わずかな処理時間を倹約するよりも、コードの明瞭性や生産性をこそ重視すべき」場合には有用です。今回の場合、「都道府県 => 県庁所在地ハッシュ」の作成のために使ったmeshがそれに該当します。しかし、たかがルックアップテーブルごときに持ち出すのはやり過ぎな感じがします。@{[]}という空リストならぬ空配列をでっち上げる処理よりも、空リストをそのまま突っ込む方が、よほど世のため人のためになるというものです。

ただ、Readonlyなハッシュ(リファレンス)については、それが大抵はクラス定数として使われることもあるので、無駄な一次配列を作らないという意味で、無理矢理1センテンスで書くという方法はありなのかも知れません。私はそのような場合にのみ、変態的な文を書いています。

#162 (2009/03/31 23:48:50), Gardejo

コメントはまだありません »

コメントはまだありません。

このコメント欄の RSS フィード トラックバック URL

ご意見・ご感想をお寄せください

開発機の故障によるErmitejoの開発停止 >
< 脇書非表示 > 脇書表示