gallu’s blog

エンジニアでゲーマーで講師で占い師なおいちゃんのブログです。

「配列から一部の要素を削る」のはどっちが早い?

いやまぁ直接的には、うちのフレームワーク(MagicWeapon)で使う系のコードのお話なのですがw
「値が重複しない前提の配列」から、「特定の値を引き算する」方法とその計測です。


とりあえず手っ取り早いところで、PHPにはarray_diffって関数があるのですが( http://php.net/manual/ja/function.array-diff.php )。
微妙に気になるのが「多分、線形検索やってるよなぁ」ってところ。
いやまぁそんなに多大に気にしても仕方がないような気がするのですが。


で、おいちゃんが割と使うのが。「値が重複しない前提」があるのと「順番は無関係」ってのもあるので。
array_flip( http://php.net/manual/ja/function.array-flip.php )で反転してkeyをunsetしてもう一回array_flipすれば、線形検索はいらなくない? って思ったあたり。
反証としては「hash値の計算で時間がかかる」「flipした時の作業用の配列の作成とGCに時間がかかる」あたり。


この辺は検証したほうが早いので、さっそく検証。
まずコード

<?php

ini_set('display_errors', 1);
error_reporting(-1);

$base = 'a';
$awk = array();
for($i = 0; $i < 10000; $i ++) {
  $awk[] = $base ++;
}
//var_dump($awk);

$t = microtime(true);
for($i = 0; $i < 100; $i ++) {
  // array_diff
  $awk2 = array_diff($awk, array('ntp', 'gjh', 'jwp', 'col'));

  // array_flip
/*
  $awk2 = array_flip($awk);
  unset($awk2['ntp']);
  unset($awk2['gjh']);
  unset($awk2['jwp']);
  unset($awk2['col']);
  $awk2 = array_flip($awk2);
*/
}
$t = microtime(true) - $t;
var_dump($t);

上述コードで、コメントアウト適当に操作して「diffとflip」とで検証。


まずPHP5.5系。
diff

float(2.1626000404358)
float(1.5443460941315)
float(1.647617816925)
float(1.7004590034485)
float(1.635516166687)
float(1.6240890026093)
float(1.6233410835266)

flip

float(1.3751840591431)
float(1.4717681407928)
float(1.4122080802917)
float(1.3495209217072)
float(1.403538942337)
float(1.4738049507141)
float(1.4681560993195)


次にPHP7.0系
diff

float(0.088997840881348)
float(0.081218004226685)
float(0.084403038024902)
float(0.085947036743164)
float(0.071822166442871)
float(0.084525108337402)
float(0.087594985961914)

flip

float(0.068278074264526)
float(0.074533939361572)
float(0.08522891998291)
float(0.075110912322998)
float(0.073028087615967)
float(0.078052997589111)
float(0.08232593536377)


…おかしいマシンパワーそんなに変わらないはずなのに、桁が違う(苦笑
さすがPHP7系、配列周りのチューニングが半端ないw


7系、forの回数を1000回にして追試。
diff

float(0.54727816581726)
float(0.64334392547607)
float(0.54209017753601)
float(0.53981614112854)

flip

float(0.80930995941162)
float(0.68021702766418)
float(0.68110299110413)
float(0.81561899185181)


…をや?
履行回数を増やすと、flipの成績が悪化していく。
やぱり「配列領域の確保と解放」に時間がかかってるのかしらん?
いくつか追試をしてみたですが、全体的な傾向として「履行回数が少ないとflip有利」「履行回数が多いとdiff有利」なので、やぱり領域確保&解放にそれなりのコストが費やされてる悪寒。


むつかしいなぁ正直。
こまか〜〜〜く話をすると「そんなに何回もぶん回す処理ではない」ので、それを考えると一応「flip有利」ではあるんだけど。
微々たるもんでもあるので、diffのほうが「見た目シンプルでわかりやすい」気がしないでもない。
ちなみにメモリは、PHP7では「どっちも一緒」、PHP5.5では「flipのほうが少しメモリ使用量が多い」感じでした。
つまり「PHP7前提ならこれもまた差異がない」、と。


悩ましいなぁ…でもまぁ「見た目シンプルでわかりやすい」前提だと、diffのほうがいいのかしらん? 的な気がしないでもない。
当初使用想定だと、要素数なんていっても100未満である可能性が高いので、そうすると線形検索ったって大してCPUコストかからないだろうしねぇ。


という、微妙に煮え切らない結果でしたw