PHPで疎なIndex配列はなぜか性能が悪い件とその対処法

PHPerの西村です。最近、AHCではC++を使うことも増えましたが、PHPerです。

ところで、みなさん、PHPで疎なIndex配列が遅くて困ったことはないでしょうか？PHPの配列は柔軟で、Indexを0,1,2,3,...と振ることもできますし、0,100,200,などと振ることもできます。間隔をあけて振っても性能は特に変わらさそうに見えるのですが、実はIndexの間隔が極端に空いているとなぜか性能が落ちます。（詳しいかたいれば解説いただけるととても助かります。）このせいでAtCoderのコンテストでTLEに苦しんだこともあります。

コード例1:

<?php
for($step = 1; $step <= 100_000_000_000; $step*=10){
    $map = [];
    $time = microtime(true);
    for($i = 0; $i < 10000; $i++){
        $map[$i*$step] = 1;
    }
    $dt = microtime(true) - $time;
    printf("step=%d time=%.6f\n", $step, $dt);
}

実行結果1:

コード例1を実行すると実行結果1のようになります。間隔が10000ぐらいまでは0.3ms程度で安定しています。1秒当たり3000万回程度実行できています。メモリ確保が必要な処理であることやスクリプト言語であることを考えると悪くない速度です。しかし、それ以上間隔が広がると性能がおち、間隔が10^11の場合は間隔が小さい場合と比べて100倍ぐらいの時間がかかってしまいます。1秒間に30万回です。遅いです。AtCoderだとTLEします。しました。（この測定では簡単のために等間隔でやってますが等間隔でなくても同じようになります。Indexを浮動小数点数にするとやや違った傾向になりますが、抜本的には変わりません。）

解決策

キーを文字列にすると、値が小さい範囲では3倍ほど時間がかかりますが、値が大きくなっても3倍で済みます。整数をそのまま使うと100倍かかっていたので大幅な改善になりました。

コード例2:

<?php
for($step = 1; $step <= 100_000_000_000; $step*=10){
    $map = [];
    $time = microtime(true);
    for($i = 0; $i < 10000; $i++){
        $map["a".($i*$step)] = 1;
    }
    $dt = microtime(true) - $time;
    printf("step=%d time=%.6f\n", $step, $dt);
}

実行例2:

まとめ

PHPで非常に疎なIndex配列を作ると性能がよくない。10人に一人のPHPerが一生に1度ぐらいは出くわすと思うので知っておいて損はないと思います。なんでこういう特性になるのかはPHPの内部実装を詳しく理解しないと分からず、私も理解しておりませんが、この罠でTLEになる場合は先頭に文字を追加して文字列にすることで回避できます。なお、数字として解釈できる文字列をキーに使った場合は数値にキャストされてしまって無駄な努力になる可能性があるのでご注意ください。