ぐらめぬ・ぜぷつぇんのはてダ(2007 to 2011)

2007年～2011年ごろまで はてなダイアリー に書いてた記事を引っ越してきました。

array_flip()ってこう使うのか・・・！！！

PHP

今、事情によりPukiWikiのソースコードを眺めています。で、lib/link.php の links_add() 関数で、

$rel_auto = array_flip($rel_auto);

という部分がありました。array_flip()というのは
http://jp.php.net/manual/ja/function.array-flip.php
にあるとおり、配列のキーと値を反転させる関数です。

実はこの関数、以前から「何に使うのかなー」と不思議に思っていたのですが、links_add()の中で上に続いて次の行を見て、久しぶりに感動しました。

$all_auto = isset($rel_auto[$_page]);

・・・！！！！！！！そうか・・・そうだったのか・・・！！


PHPで、配列にある値がセットされているのかどうか調べるには、次の二つの方法があります。

// キーに設定されているかどうか
if (isset($foo['key'])) { .. }

// 値に設定されているかどうか
if (in_array($value, $foo)) { .. }

で、PHPの場合・・・というか言語に依らずハッシュをキーとしたmapの場合は大概そうだと思いますが、キーに設定されているかどうかの方が動作が速いです。
ここで、array_flip()の出番なわけですよ！！

$haystack = array($a, $b, $c, ... );
$needle = '...';
// 今までは・・・
// in_array($needle, $haystack)
// array_flip()を使えば・・・
$haystack = array_flip($haystack);
isset($haystack[$needle]); // or array_key_exists()

と出来るではありませんか！！

・・・が。

だめ、全然だめ。array_flipが遅い（そりゃそうだ）。
同じ配列の値を数10回以上検索するのならやる価値はあるだろうが、そのときもneedleを配列にして一度にin_arrayで検索した方が速い。

in_arrayとarray_flip+array_key_existsの比較 - ”improve it!”

・・・え。マジ？ Σ（ﾟдﾟlll）
ちょっと確認してみる。比較対象は三つ。

  • 1つのneedleに対し、in_array()で100回探索。
  • 1つのneedleに対し、array_flip()後、isset()で100回探索
  • 1つのneedleに対し、array_flip()後、array_key_exists()で100回探索

先に結果だけ。

Pen4 2.8GHz HT, WindowsXP SP2, PHP 4.4.7

# 1つのneedleに対し、in_array()で100探索。
> php array_flip_benchmark01.php
0.124406
0.121956
0.135410
0.132754
0.120091
0.136385
0.125521
0.134713
0.125297
0.122074
-----------
Average : 0.1278607

# 1つのneedleに対し、array_flip()後、isset()で探索 ... "hit"がisset()の分。
> php array_flip_benchmark02.php
0.008059,0.000257,0.008316
0.013198,0.000432,0.013630
0.015014,0.000261,0.015275
0.010188,0.000261,0.010449
0.013043,0.001135,0.014178
0.010145,0.000255,0.010400
0.017030,0.000275,0.017305
0.016809,0.000472,0.017281
0.017025,0.000263,0.017288
0.009889,0.000255,0.010144
-----------
Average :
        array_flip() : 0.01304
        hit : 0.0003866
        total : 0.0134266

# 1つのneedleに対し、array_flip()後、array_key_exists()で100回探索 ... "hit"がarray_key_exists()の分。
> php array_flip_benchmark03.php
0.008997,0.000457,0.009454
0.013676,0.000454,0.014130
0.014360,0.000273,0.014633
0.009967,0.000286,0.010253
0.014600,0.000285,0.014885
0.010226,0.000272,0.010498
0.018018,0.000487,0.018505
0.025147,0.000355,0.025502
0.010049,0.000269,0.010318
0.017555,0.000569,0.018124
-----------
Average :
        array_flip() : 0.0142595
        hit : 0.0003707
        total : 0.0146302

・・・in_arrayよりは、array_flip()で反転後にisset()やarray_key_exists()で判定した方が遙かに速い様ではあるのだけれど。
また、needleが配列になった場合は試していなくて、単純にscalar値1つだけで試してます。そこも違うのかな・・・。

とりあえず、以下にソース

--------------------------------------------------------
array_flip_benchmark01.php

<?php
require_once('Benchmark/Timer.php');

$sz = 10000;

$arr1 = array();
for ($i = 0; $i < $sz; $i++) {
    $arr1[] = mt_rand(1, $sz);
}
shuffle($arr1);
shuffle($arr1);

$t1 =& new Benchmark_Timer();
$elapsed = array();
for ($k = 0; $k < 10; $k++) {
    $t1->start();
    for ($i = 0; $i < 100; $i++) {
        $needle = mt_rand(1, $sz);;
        in_array($needle, $arr1);
    }
    $t1->stop();
    $elapsed[] = $t1->timeElapsed('Start', 'Stop');
}

$sum = 0;
foreach ($elapsed as $el) {
    $sum += $el;
    echo $el.PHP_EOL;
}
echo "-----------".PHP_EOL;
echo "Average : ". $sum / 10 . PHP_EOL;

--------------------------------------------------------
array_flip_benchmark02.php

<?php
require_once('Benchmark/Timer.php');

$sz = 10000;

$arr1 = array();
for ($i = 0; $i < $sz; $i++) {
    $arr1[] = mt_rand(1, $sz);
}
shuffle($arr1);
shuffle($arr1);

$t1 =& new Benchmark_Timer();
$elapsed = array();
for ($k = 0; $k < 10; $k++) {
    $t1->start();
    $arr2 = array_flip($arr1);
    $t1->setMarker('m1');
    for ($i = 0; $i < 100; $i++) {
        $needle = mt_rand(1, $sz);
        $d = isset($arr2[$needle]);
    }
    $t1->stop();
    $elapsed[] = array(
        'array_flip' => $t1->timeElapsed('Start', 'm1'),
        'hit' => $t1->timeElapsed('m1', 'Stop'),
        'total' => $t1->timeElapsed('Start', 'Stop'),
        );
}

$sum_af = 0;
$sum_hit = 0;
$sum_total = 0;
foreach ($elapsed as $el) {
    $sum_af += $el['array_flip'];
    $sum_hit += $el['hit'];
    $sum_total += $el['total'];
    echo $el['array_flip'] . ',' . $el['hit'] . ',' . $el['total'] . PHP_EOL;
}
echo "-----------".PHP_EOL;
echo "Average : ".PHP_EOL;
echo "\tarray_flip() : " . $sum_af / 10 . PHP_EOL;
echo "\thit : " . $sum_hit / 10 . PHP_EOL;
echo "\ttotal : " . $sum_total / 10 . PHP_EOL;

--------------------------------------------------------
array_flip_benchmark03.php

<?php
require_once('Benchmark/Timer.php');

$sz = 10000;

$arr1 = array();
for ($i = 0; $i < $sz; $i++) {
    $arr1[] = mt_rand(1, $sz);
}
shuffle($arr1);
shuffle($arr1);

$t1 =& new Benchmark_Timer();
$elapsed = array();
for ($k = 0; $k < 10; $k++) {
    $t1->start();
    $arr2 = array_flip($arr1);
    $t1->setMarker('m1');
    for ($i = 0; $i < 100; $i++) {
        $needle = mt_rand(1, $sz);
        array_key_exists($needle, $arr2);
    }
    $t1->stop();
    $elapsed[] = array(
        'array_flip' => $t1->timeElapsed('Start', 'm1'),
        'hit' => $t1->timeElapsed('m1', 'Stop'),
        'total' => $t1->timeElapsed('Start', 'Stop'),
        );
}

$sum_af = 0;
$sum_hit = 0;
$sum_total = 0;
foreach ($elapsed as $el) {
    $sum_af += $el['array_flip'];
    $sum_hit += $el['hit'];
    $sum_total += $el['total'];
    echo $el['array_flip'] . ',' . $el['hit'] . ',' . $el['total'] . PHP_EOL;
}
echo "-----------".PHP_EOL;
echo "Average : ".PHP_EOL;
echo "\tarray_flip() : " . $sum_af / 10 . PHP_EOL;
echo "\thit : " . $sum_hit / 10 . PHP_EOL;
echo "\ttotal : " . $sum_total / 10 . PHP_EOL;

うーん・・・。まぁ、YakiBikiも内部で結構な数のneedle探しをしている箇所があるので、地道にこの手法で置き換えることで、大分速くなる箇所もあるのかも知れない。