2023.04.24
STAFF BLOG
スタッフブログ
TECHNICAL
テクログ
この記事は何ですか？
str_replaceとstrtrの実行速度が大幅に異なることがあり、どのような実装をしていて計算量がどの程度なのかが気になりました。しかし、わざわざPHPのソースコードを読みに行くほどでもなかったので、自分の中で考えられる「遅い関数」と「速い関数」の実行速度を計測し、str_replaceとstrtrの計算量オーダーの見積もりだけしようという試みです。
str_replaceとstrtrについて
それぞれ下記のPHPマニュアルが詳しいです。
- str_replace：https://www.php.net/manual/ja/function.str-replace.php
- strtr：https://www.php.net/manual/ja/function.strtr.php
ざっくり、どちらも「部分文字列の置換を行う関数」になっています。
違いとしては、str_replaceの方が機能が豊富です。
- 第4引数「count」に変数を指定することで、置換回数を取得できる。
- 第1引数「search」、第2引数「replace」、第3引数「subject」には文字列だけでなく、文字列の配列を渡すことができる。
計測を行うケース
先ほどの「 str_replaceとstrtrの実行速度が大幅に異なることがあり」というのは、例えば以下のような場合です。
- search：aaa…ab（「a」が10^4個続き、最後に「b」がつくような長さ10^4+1の文字列）
- replace：空文字
- subject：aaa…aa（「a」が10^5個続くような文字列）
ナイーブな方法として以下の2重ループが思いつきますが、その実行速度が遅くなるようなケースです。
n = subjectの長さ
m = searchの長さ
for iが0からn-mまで
for jが0からm-1まで
if subjectのiからi+m-1までの部分文字列がsearchと一致するなら
searchと一致するsubjectの部分文字列をreplaceに置換恐らく、str_replaceはこのような実装になっているのではないかと推測しました。そのため、今回こちらのケースのみ計測していこうと思います。
計測を行う関数
以下4つの関数の速度を計測します。
- str_replace
- strtr
- 自作する遅い関数
- 自作する速い関数
遅い関数
先ほどの2重ループを回すような処理を持つ関数として作成します。計算量は、subjectの長さをN、searchの長さをMとするとO(NM)です。
速い関数
以下のような処理を持つ関数として作成します。
- dp[i+1]:=subjectのi文字目がsearchの先頭何文字目と一致しているか。
- subject[i]==search[dp[i]]なら、dp[i+1]=dp[i]+1で更新。
- subject[i]!=search[dp[i]]なら、subject[i]==search[0]のときdp[i+1]=1、それ以外はdp[i+1]=0で更新。
計算量はsubjectの長さをNとするとO(N)です。
計測
計測には以下のコードを使用しました。
<?php
$n = 100000; // 10^5
$count = 3; // 計測回数
$search = str_repeat('a', $n / 10) . 'b'; // aaa...ab
$replace = '';
$subject = str_repeat('a', $n); // aaa...a
// str_replaceの計測
$count = 5;
$time_start = microtime(true);
for ($i = 0; $i < $count; ++$i) {
str_replace($search, $replace, $subject);
}
$time = microtime(true) - $time_start;
printf("[str_replace]\n Average: %.12f\n", $time / $count);
// strtrの計測
$count = 5;
$time_start = microtime(true);
for ($i = 0; $i < $count; ++$i) {
strtr($search, $replace, $subject);
}
$time = microtime(true) - $time_start;
printf("[strtr]\n Average: %.12f\n", $time / $count);
// 遅い関数
function slow_replace(string $search, string $replace, string $subject): string
{
$n = strlen($subject);
$m = strlen($search);
for ($i = 0; $i < $n - $m + 1; ++$i) {
$is_substring = true;
for ($j = 0; $j < $m; ++$j) {
if ($subject[$i + $j] !== $search[$j]) {
$is_substring = false;
}
}
if ($is_substring) {
$subject = substr($subject, 0, $i) . $replace . substr($subject, $i + $m);
$n = strlen($subject);
--$i;
}
}
return $subject;
}
// 速い関数
function fast_replace(string $search, string $replace, string $subject): string
{
$n = strlen($subject);
$m = strlen($search);
$dp = [0];
for ($i = 0; $i < $n; ++$i) {
if ($subject[$i] === $search[$dp[$i]]) {
$dp[$i + 1] = $dp[$i] + 1;
if ($dp[$i + 1] === $m) {
$subject = substr($subject, 0, $i - $m + 1) . $replace . substr($subject, $i + 1);
$n = strlen($subject);
$i -= $m;
}
} else if ($subject[$i] === $search[0]) {
$dp[$i + 1] = 1;
} else {
$dp[$i + 1] = 0;
}
}
return $subject;
}
// slow_replaceの計測
$time_start = microtime(true);
for ($i = 0; $i < $count; ++$i) {
slow_replace($search, $replace, $subject);
}
$time = microtime(true) - $time_start;
printf("[slow_replace]\n Average: %.12f\n", $time / $count);
// fast_replaceの計測
$time_start = microtime(true);
for ($i = 0; $i < $count; ++$i) {
fast_replace($search, $replace, $subject);
}
$time = microtime(true) - $time_start;
printf("[fast_replace]\n Average: %.12f\n", $time / $count);結果
| 関数 | 実行速度(second) |
| str_replace | 0.168267393112 |
| strtr | 0.000000762939 |
| slow_replace | 16.234501171112 |
| fast_replace | 0.011269569397 |
計測回数が3回というあまりの少なさのため、きちんとした値が気になる方はソースコードの値をいろいろいじったりして確認してみてください……。
考察
PHPの標準関数は内部で最適化されているはず（要出典）なのでそれを加味すると、str_replaceとstrtrのオーダーはslow_replace、fast_replaceと大体同じだと思われます。（strtrが速すぎです……。）
str_replaceについては、N=10^5、M=10^4のときでも高速に動作していたので、定数倍を切り詰めるような場面でもなければわざわざstrtrを使用しなくても大丈夫なのかなという感じです。個人的には「strtr」だと何の関数かパッと見でわかりづらいので、可読性の観点からstr_replaceを使用したい気持ちになります。ただ、競プロなど実行速度が求められる場面では、定数倍で実行時間制限を超えてしまう危険を少しでも減らすためstrtrを使用するのがよいかもしれません。
あと、今回は実際に置換が行われないケースのみ試しましたが、実際に置換が行われると「遅い関数」と「速い関数」がさらに遅くなってしまうと思います。置換をしたときにそれ以降の文字列の添え字が変わってしまうのが原因になると思うので、置換によって削除される文字列と、挿入される文字列の位置を記録しておいて、最後に置換処理を行うのがよさそうです。（今回はそれが関係ないパターンのみを試したので、実装量を減らして時短しています……。）
まとめ
- str_replaceとstrtrのオーダーはそれぞれO(NM)とO(N)よりそこそこ速いくらい。（ただし、Nはsubjectの長さで、Mはsearchの長さ）
- str_replaceはN=10^5、M=10^4くらいなら高速に動作するので基本的にはstr_replaceで大丈夫そう。
- 競プロなど実行速度が求められる場面では、strtrを使用した方がよいかもしれません。
補足
Q. なぜN=10^5、M=10^5で、どちらも10^5にしないのですか？
A. subjectの部分文字列のうち長さMのものはN-M+1個しかないので、N≒Mだとオーダーが変わってしまうからです。
