PHPのarray系組込関数の一部を高速化する

とあるシステムをPHPで作っていた時のお話。


それなりに大きな配列を操作したり、小さい配列をループ内で操作したとき、
応答速度が少し遅い･･･なんて場面にぶつかってしまいました。
Xhprof なんかを使ってプロファイリングしてみると、
array_diff、array_unique、array_intersect あたりがボトルネックになっていることが分かりました。
少し調べてみると、こういった関数の高速版を公開している人がいましたので、メモがてら紹介します。
※使用は自己責任で。

array_diff

array_diff は、配列の差分を返します。(PHP: array_diff - Manual)
これの高速版がstackoverflowにありました。

以下はコードの抜粋。
O(n)になってますね。特にデメリットも思い浮かばず。

<?php
  function my_array_diff( $a, $b ) {
    $map = $out = array();
    foreach( $a as $val ) $map[$val] = 1;
    foreach( $b as $val ) if ( isset( $map[$val] ) ) $map[$val] = 0;
    foreach( $map as $val => $ok ) if( $ok ) $out[] = $val;
    return $out;
  }
?>
array_unique

array_unique は、配列の重複要素を除いて返します。(PHP: array_unique - Manual)
これの高速版がpuremango.co.ukにありました。

以下はコードの抜粋。
実装の発想が面白い。array_flip(PHP: array_flip - Manual)をうまく使っています。
array_flipでキーと値を逆転。そしてまたarray_flipすることで、重複するキーが上書きで消えます。
最初に array_reverse しているのは、array_unique の挙動に近づけるためかな。

<?php
  function fast_unique($input) {
    // Code documented at: http://www.puremango.co.uk/?p=1039
    return array_flip(array_flip(array_reverse($input,true)));
  }
?>
array_intersect

array_intersect は、配列の論理積みたいなもの(と勝手に思ってます)。(PHP: array_intersect - Manual)
これの高速版が、sitepoint.com にありました。

以下はコードの抜粋。
組込 array_intersect の限定的なもののようで、値が数値ではなく文字列とかだと
遅いようです。DBからIDのみ抽出し、論理積をとりたい時などには大活躍ですね。

<?php
  function my_array_intersect( $s1, $s2 ) {
    $i = 0;
    $j = 0;
    $N = count( $s1 );
    $M = count( $s2 );
    $intersection = array();
     
    while ( $i < $N && $j < $M ) {
      if ( $s1[$i] < $s2[$j] ) $i++;
      else if ( $s1[$i] > $s2[$j] ) $j++;
      else {
        $intersection[] = $s1[$i];
        $i++;
        $j++;
      }
    }
    return $intersection;
  }
?>