ニュース

2024年3月7日

PythonおよびJavaでコンパイル済み正規表現を使用するメリット：比較検証して分かったこと

「Python」や「Java」でプログラミングを行う場合、コンパイル済み正規表現を使うとテキスト操作ルーティンの速度が大幅に向上する。

LINE

Hatena

　先日、URL文字列から指定したパラメーターを削除する「最善」の方法についての議論に参加した。

　この議論は、文字列プリミティブを使ってパラメーターを分割してから再度結合する方法から始まった。この手法は分かりやすく読みやすい。1行か2行の正規表現を使っても同じ結果を得ることができる。だが、正規表現（regex）は非常に時間がかかるといわれている。一般的には時間がかかることは間違いない。

　とはいえ、正規表現と文字列プリミティブではかかる時間がどの程度違うのか、事前コンパイル済みの正規表現を使うとパフォーマンスは向上するのかという点では疑問が残る。

文字列操作によってパラメーターを削除する

　パラメーターを削除する最も簡単で恐らく最も分かりやすいのは、分割プリミティブを使って文字列を分割し、指定されたパラメーターを削除してから再結合する方法だ。

　この方法は筆者にとっては大変な作業のように感じられ、ほとんどの言語で文字列が変更不可になっていることを考えると、メモリを大量に使用する可能性が高い。

　「Java」では、この操作を次の4行のコードで実現できる。

String[] parts = input.split("&");
List<String> partsList = new ArrayList<>(Arrays.asList(parts));
partsList.removeIf(part -> part.contains("option"));
outputsSplit = String.join("&",partsList);

　「Python」では、次のようにコードが短く、簡潔になる。

parts = input.split("&")
parts = [part for part in parts if "option" not in part]
output = '&'.join(parts) 
Both do the same thing: manipulate and rejoin a split list.

正規表現を使ってパラメーターを削除する

　JavaやPythonでパラメーターを削除するもう1つの選択肢は、正規表現を使って入力文字列の対応部分を削除する方法だ。この方法は分かりやすさという点ではかなり劣る。だが、使用するコード行は少なくなる。コード行数の少なさという点では正規表現が適している。

　Javaでは次の1行のコードしか必要にならない。

output = input.replaceFirst("option=one$","").replaceFirst("option=one&","");

　Pythonでは次の2行のコードになる。

output = re.sub(r"option=one$", "", input)
output = re.sub(r"option=one&", "", output)

　Python方式では、文字列プリミティブを使うよりもコード行数が少なくなる。これは正規表現に適したユースケースだが、正規表現は時間がかかることでも知られている。

　時間がかかることが事前に分かっていれば、対処できる別の方法がある。

コンパイル済みの正規表現を使ってパラメーターを削除する

　削除するパラメーターに相当する正規表現が変わらないのであれば、代わりにコンパイル済み正規表現を使用できる。

　標準の正規表現は、文字列の中から何かを探すレシピのようなものだと考えられる。コンピュータはこのレシピを利用するたびに毎回読み取って解析しなければならない。正規表現を使う場合、この読み取りと解析の処理に最もパフォーマンスが消費される。

　コンパイル済みの正規表現ならこの読み取りと解析の処理が一度しか行われないため、標準の正規表現よりもはるかに高速になる。だが、照合するパターンが変わるとコンパイル済み正規表現は使えなくなる。

　デメリットはコード行数が増えることだ。正規表現を使うと文字列プリミティブを使うよりも行数が少なくなるという最初の動機が失われる。

　Javaでコンパイル済み正規表現を使うと次のように6行になる。

private static final Pattern PATTERN_END = Pattern.compile("&option=one$");
private static final Pattern PATTERN_START_MIDDLE = Pattern.compile("option=one&");
Matcher matcherEnd = PATTERN_END.matcher(input);
String intermediateResult = matcherEnd.replaceFirst("");
Matcher matcherStartMiddle = PATTERN_START_MIDDLE.matcher(intermediateResult);
output = matcherStartMiddle.replaceFirst("");

　Pythonでは、次の4行になる。

PATTERN_END = re.compile(r"&option=one$")
PATTERN_START_MIDDLE = re.compile(r"option=one&")
intermediate_result = PATTERN_END.sub('', input)
output = PATTERN_START_MIDDLE.sub('', intermediate_result)

　ここで実際に問題になるのは、コード行数が増えてもパフォーマンス上のメリットがあるかどうかだ。

　本稿で取り上げた方法を検証するため、10万行の入力を生成し、その中に削除対象のパラメーターをランダムに配置した。次に、関数を使ってコードを実行し、完了までの時間を計測した。

Javaでコンパイル済み正規表現を使った結果

　Javaでは、驚いたことに、標準の正規表現を使う場合と文字列プリミティブを使用する場合の差はほとんどなかった。10万行を処理するのに、文字列プリミティブでは188ミリ秒、標準の正規表現では224ミリ秒を要した。

　一方、コンパイル済みの正規表現を使った場合、10万行を処理するのに要した時間はわずか52ミリ秒で、文字列プリミティブを使う場合の3分の1以下だった。

Pythonでコンパイル済み正規表現を使った結果

　Pythonで、ランダムに生成した10万行の入力行に前述の同じ方法を使うと、Javaとは幾つか違いが見られた。1つ目は、コードの実行が全体的に約5倍遅かったことだ。これは想定内の結果で、インタープリタ言語とコンパイル言語の違いを表している。

　2つ目は、文字列プリミティブの使用と正規表現の使用に大きな差が出たことだ。10万行を処理するのに、文字列プリミティブでは477ミリ秒だったのに対し、標準の正規表現では904ミリ秒とほぼ2倍の時間がかかった。

　一方でPythonでは、コンパイル済み正規表現が比較的優れたパフォーマンスを発揮した。10万行を処理するのに要した時間は165ミリ秒で、これはPythonで文字列プリミティブを使用する場合と比べて約2倍の速度向上になる。

結論

　これら全ての結果から分かることは、標準の正規表現を使うとシンプルな文字列プリミティブを使う場合と比べて大幅に遅くなることだ。ただし、その差は、使用するコーディング言語に左右される。

　パフォーマンスの高い文字列置換コードを作成するのであれば、コンパイル済みの正規表現を使うのが最適だ。