array_unique と array_flip x2 の速度比較

2021-05-17
PHP
array_unique
array_flip

表題の通りです。職場にて array_flip を2回やると、 array_unique より早いらしいという言説を見かけたため、腹落ちするまで調べてみました。なにしろ「らしい」という単語に過剰反応してしまうもので…。

マイクロベンチマーク

適当に重複した80万件の配列を作って、比較対象の関数で実行します。

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
32
33
<?php

$dup = [];
for ($i = 0; $i < 80000; $i++) {
if($i < 30000) $dup[] = $i;
$dup[] = $i;
}

// array_flip2回
$start = microtime(true);
array_flip(array_flip($dup));
printf("array_flip x2 => %.13f 秒\n", microtime(true) - $start);

// array_unique
$start = microtime(true);
array_unique($dup, SORT_STRING);
printf("array_unique SORT_STRING => %.13f 秒\n", microtime(true) - $start);

// array_unique
$start = microtime(true);
array_unique($dup, SORT_NUMERIC);
printf("array_unique SORT_NUMERIC => %.13f 秒\n", microtime(true) - $start);

// array_unique
$start = microtime(true);
array_unique($dup, SORT_REGULAR);
printf("array_unique SORT_REGULAR => %.13f 秒\n", microtime(true) - $start);

// array_unique
$start = microtime(true);
array_unique($dup, SORT_LOCALE_STRING);
printf("array_unique SORT_LOCALE_STRING => %.13f 秒\n", microtime(true) - $start);

関数名 オプション 処理時間(秒) 最速を1とした時の速度比
array_flip x2 - 0.0085070133209 1
array_unique SORT_STRING 0.0282361507416 3.32
array_unique SORT_NUMERIC 0.0873460769653 10.28
array_unique SORT_REGULAR 0.0463910102844 5.45
array_unique SORT_LOCALE_STRING 0.5002570152283 58.81

結果の考察

結果だけ見ると、「うぉぉ、 array_flip x2 でいいじゃん!」となりそうですが、世の中はそう美味い話は転がっていません。array_flip を array_unique の代用として使うには、条件があります。

  • 対象が int配列

これが絶対条件です。array_flip すると numeric な文字列は型が吹き飛びます。array_unique は最初に登場した値を残していきますが、array_flip では単純にhashのキーを上書きしていくので後勝ちになります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$ php -a
Interactive shell

php > var_export(array_flip(array_flip([1,2,'2'])));
array (
0 => 1,
2 => 2,
)
php > var_export(array_flip(array_flip([1,'2',2])));
array (
0 => 1,
2 => 2,
)
php > var_export(array_unique([1,2,'2'], SORT_STRING));
array (
0 => 1,
1 => 2,
)
php > var_export(array_unique([1,'2',2], SORT_STRING));
array (
0 => 1,
1 => '2',
)

array_unique のオプションによる違い

SORT_STRING というオプションは、PHP 7.2 から導入されたもので、 Hash をメモに使うことで、O(n)オーダーでの処理を可能にしています。

SORT_REGULAR, SORT_NUMERIC, SORT_LOCALE_STRING の3つについては、アルゴリズムとしては同じで、配列の値をソートして、ソート済みの配列に対して先勝ちでユニークな値を拾っていきます。オプションに違いによって、ソートするときのコンパレーターが変わります。計算量は O(n log n) ですが、コンパレーターの差で処理速度が変わるようです。

FlameGraph

perf-tools を使ってPHPソースレベルの Flamegraph を作る

当ブログで紹介した方法で、各関数に対してFlameGraphを取ってみました。詳細は中身を見てほしいのですが、 array_unique SORT_STRINGarray_flip と同じ計算料にもかかわらず処理速度が遅いのは、__toString の呼び出しにコストがかかるためでした。同様に array_unique SORT_LOCALE_STRING が飛び抜けて処理効率が悪いのも __toString が原因のようです。

FlameGraph は、どれくらいのコストがかかっているのかが一目瞭然で、わかりやすいですね!!

array_flip [array_flip x2](/images/flame/flame_array_flip.svg) array_unique [array_unique SORT_STRING](/images/flame/flame_array_unique_string.svg) array_unique [array_unique SORT_REGULAR](/images/flame/flame_array_unique_regular.svg) array_unique [array_unique SORT_NUMERIC](/images/flame/flame_array_unique_numeric.svg) array_unique [array_unique SORT_LOCALE_STRING](/images/flame/flame_array_unique_locale.svg)