ぼやきごと/2009-03-04/連想配列（ハッシュテーブル）による条件分岐数の削減 のバックアップ(No.5)

[前へ] [次へ] [目次]

連想配列（ハッシュテーブル）による条件分岐数の削減 †

C++などのコンパイラ言語では、一般にif文でもswitch文でも書ける処理はswitch文で書く方が高速になります。

すべて開くすべて閉じる
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14

-
!
 
 
 
 
-
!
-
|
|
|
|
!

// 定数との等価比較しか無いならば、ifでこう書くよりも…
if      (n == 1) { execFirst(); }
else if (n == 2) { execSecond(); }
else if (n == 3) { execThird(); }
else             { execOthers(); }
 
// switchでこう書く方が高速になる
switch (n)
{
    case 1:  execFirst();  break;
    case 2:  execSecond(); break;
    case 3:  execThird();  break;
    default: execOthers(); break;
}

…とはいってもそこまで気にするほどの差は無く、それよりもソースコード見やすさの方がよっぽど重要ですが。

それに対してPHP等のインタプリタ言語では、大抵の実装において、if文とswitch文に速度の差はほぼありません。
if文でもswitch文でも結局は上から順に読み取って等価チェックするしかないためです。

PHPマニュアルのswitchの項には次のように書いてありますが、これは比較元の話です。
if文でも予め比較元の計算結果を別の変数に入れておけば同じことです。

switch文では、条件は1度だけ評価され、 その結果が各case文と比較されます。 elseif文では、条件は、再度評価されます。 使用する条件が単純な比較処理よりも複雑な処理を行ったり、 重い繰り返し処理を行う場合、switchの方が より処理が速い可能性があります。

条件分岐において、コンパイラ言語でもインタプリタ言語でも有用な高速化の方法としては次のようなものが考えられます。

  1. ヒットする可能性の高い条件ほど上に持ってくる。
  2. そもそもの条件分岐数を極力減らす。

PHPで二番目を実現する方法の一つに、連想配列を使う方法があります*1。
例えば次のようなswitch文を考えてみましょう。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20

<?php
// ユニットIDの配列を用いてユニット名を出力する。
function printUnitNames($unitIds)
{
    foreach ($unitIds as $id)
    {
        switch ($id)
        {
            case 'ramza'   : print('ラムザ');       break;
            case 'delita'  : print('ディリータ');   break;
            case 'algas'   : print('アルガス');     break;
            // 〜中略(大量のcase句)〜
            case 'agrius'  : print('アグリアス');   break;
            case 'mustadio': print('ムスタディオ'); break;
            default        : print('？？？？');     break;
        }
        print("\n");
    }
}
?>

もし $unitIds の要素数が多かった場合、ループ回数が増え、それだけswitch文による分岐処理の回数が増えます。
また、case句が何十個もあったりすると、 $id の値によっては比較回数がかなり多くなり、それだけ時間が掛かります。
この関数が何度も呼び出されるのであればなおさらです。

ここで連想配列を使うと、上述のコードは次のように置き換えることができます。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31

<?php
// ユニット名の連想配列をグローバルに定義
$unitNames = array(
    'ramza'    => 'ラムザ',
    'delita'   => 'ディリータ',
    'algas'    => 'アルガス',
    // 〜中略〜
    'agrius'   => 'アグリアス',
    'mustadio' => 'ムスタディオ',
    );
 
// ユニットIDの配列を用いてユニット名を出力する。
function printUnitNames($unitIds)
{
    global $unitNames;
 
    foreach ($unitIds as $id)
    {
        if (isset($unitNames[$id]))
        {
            // IDが存在するならばその値を出力
            print($unitNames[$id]);
        }
        else
        {
            print('？？？？');
        }
        print("\n");
    }
}
?>

一応issetで存在チェックをしていますが、IDが有効な値であるという保証があるならばif文すら不要になります。
実際に渡されるIDのばらけ具合にもよりますが、大抵の場合においてはこちらの方がかなり高速になります。
特に後ろのIDが多い場合の速度はswitch文の比ではなく、分岐数やループ回数によっては秒単位の差が出ます。

ループ内や何度も呼び出されるような処理では結構重要なテクニックではないかと思います。

Category: [プログラミング][PHP] - 2009-03-04 08:01:33
  • 昔と違って最近では見た目も重視するようにはなってますね。ただ使い分けの細かい部分で単純な物に限りますが0か1のスイッチを作ったらswitchではなくif (!empty ($i))を状態によっては使います。 -- 作者Ｍ 2009-03-06 (金) 04:11:38
  • 0か1…って要するに真偽値（true or false）の話ですよね？ 真偽判定にswitchはさすがに（たとえコンパイラ言語でも）ありえないでしょう。速度云々以前に読みにくいことこの上ないｗ -- ルーチェ 2009-03-06 (金) 21:07:57
[前へ] [次へ] [目次]

*1 C++でもstd::map<>を使えば同等のことができます。