ヤドカリラボ

ヤドカリのラボです

正規表現を用いる際のパフォーマンスチェックリスト

Python

Python で正規表現を書いて分析や機械学習のモデル構築、予測に活用する際には、正規表現実行時のパフォーマンスが足かせとなる場合があります。

正規表現の処理に用いられる実行時間がどのくらいになるかはテキストデータの分量や機械学習モデルの精度検証の実行回数に応じて変わってきます。

一つのテキストデータに対する正規表現の実行時間を少なくすることで、タスクによっては全体として大幅な処理時間の短縮が見込まれます。そのことによって精度検証を素早く回したり、テキスト処理実行時の前処理の実行時間を削減する等の効果が得られます。精度検証の間の実行待ち時間やバッチ・キューによる予測時の時間が減り、最終的には精度向上の機会の向上やサービスのユーザ体験の向上に繋がるというわけです。

本記事では Python を用いた場合の正規表現のパフォーマンス改善候補についてリストアップし、具体的な対応方法について見ていきます。

Table of contents

環境情報

本記事でのコードの実行環境は以下の通りです。

  • MBP 2019 (macOS Catalina)
  • Python 3.6.7
  • pandas 1.0.1 (一部 0.25.3 )
  • fb-re2 1.0.6

実行環境の用意は下記の記事を参考にDockerで作成しました。

qiita.com

環境構築にあたって利用したDockerイメージはこちらです。

正規表現をコンパイルする

Python で正規表現を扱う際には定番の re モジュールですが、大きめの正規表現を繰り返し用いることが想定される場合には予め compile メソッドを用いてコンパイル*1しておくと、トータルとしての実行時間を削減できます。

In

import re
import timeit

target_text = 'kou123otsu'
digit_pattern = r'\d+'
count = 100

def direct_use():
    for _ in range(count):
        re.search(digit_pattern, target_text)

def compile_once():
    regex = re.compile(digit_pattern)

    for _ in range(count):
        regex.search(target_text)

def compile_everytime():
    for _ in range(count):
        regex = re.compile(digit_pattern)
        regex.search(target_text)


for func in [direct_use, compile_once, compile_everytime]:
    print(func)
    %timeit func()

Out

> <function direct_use at 0x7ff9904998c8>
> 119 µs ± 1.05 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> <function compile_once at 0x7ff96991c598>
> 47.9 µs ± 470 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> <function compile_everytime at 0x7ff96991c510>
> 111 µs ± 935 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
関数 実行時間 実行時間% (per direct_use)
direct_use 119µs 100%
compile_once 47.9µs 40%
compile_everytime 111µs 93%

尚、トータルとしてとあえて断ったのは、この例での通常の利用ケースを想定した関数 direct_use の中でも二回目の実行以降はコンパイルされた正規表現パターンが実行されているためです。

というのも、re ライブラリ側の実装として、通常のマッチング関数に渡されたパターンはキャッシュが効くようになっています。

docs.python.org

しかし、下記記事によれば、キャッシュが効いていたとしても、キャッシュに対する検索時間がかかるという旨の考察がなされています。

teratail.com

やはり大量に同じパターンを用いる場合はコンパイルした正規表現を渡しておいたほうが実行時間的には無難といえます。

複数マッチや文字クラスでまとめられそうな表現は一つにまとめる

検索対象が複数の文字列に及ぶ場合、正規表現として文字クラス等を用いて一つにまとめたほうが処理が速いです。

In

import re
import timeit

target_text = '契約期間中に解約しようとするときは通知しなければならない'
count = 100

def sub_redundantly():
    target_words = ['契約', '解約']
    for _ in range(count):
        result = target_text
        for word in target_words:
            result = re.sub(word, 'XXX', result)

def sub_all():
    word_pattern = '[契解]約'
    for _ in range(count):
        result = target_text
        result = re.sub(word_pattern, 'XXX', result)
        
for func in [sub_redundantly, sub_all]:
    print(func)
    %timeit func()

Out

> <function sub_redundantly at 0x7f3b61056ea0>
> 256 µs ± 1.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> <function sub_all at 0x7f3b618a4bf8>
> 200 µs ± 2.96 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
関数 実行時間 実行時間% (per sub_redundantly)
sub_redundantly 256µs 100%
sub_all 200µs 78%

for 文の中で複数の似たような単語を同時に変換しているような処理はパフォーマンス改善対象の候補になるでしょう。

キャプチャを伴わないグループ化 (?:) を用いる

正規表現を用いて () 内に囲ったパターンにマッチした一部の文字列を抽出することはキャプチャと言われますが、キャプチャは正規表現内で明示的に避けることができます。キャプチャを避けることで正規表現の実行のパフォーマンスにも若干の違いが出てきます。

In

import re
import timeit

target_text = 'https://subdomain.company.co.jp/{}/index.html'.format('/'.join([chr(i) for i in range(97, 97+26)]))
print(target_text)
subdomain_pattern_1 = r'$https?://([a-z]+)\.[a-z]+(\.co\.jp|\.ac\.jp)/([a-z]+/)*(index|title).html'
subdomain_pattern_2 = r'$https?://([a-z]+)\.[a-z]+(?:\.co\.jp|\.ac\.jp)/(?:[a-z]+/)*/(?:index|title).html'
count = 100

def capture_all():
    regex = re.compile(subdomain_pattern_1)
    for _ in range(count):
        regex.search(target_text)

def capture_only_subdomain():
    regex = re.compile(subdomain_pattern_2)
    for _ in range(count):
        regex.search(target_text)    


for func in [capture_all, capture_only_subdomain]:
    print(func)
    %timeit func()

Out

> https://subdomain.company.co.jp/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y/z/index.html
> <function capture_all at 0x7fb28fe87d08>
> 62.5 µs ± 680 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> <function capture_only_subdomain at 0x7fb28fe87d90>
> 60.6 µs ± 836 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
関数 実行時間 実行時間% (per capture_all)
capture_all 62.5µs 100%
capture_only_subdomain 60.6µs 97%

これはターゲット文字列が極端な例ですが、キャプチャが行われないことで実行時間に若干の違いが出ています。(しかしそこまでの差ではない）

pandas の str アクセサについて

pandas の str アクセサは文字列操作について汎用的な操作を提供しますが、バージョンによっては pd.Series の replace を用いた方が速いです。

In

import pandas as pd
import timeit

target_text = '契約期間中に解約しようとするときは通知しなければならない'
count = 100
df = pd.DataFrame({'text': [target_text] * count}, dtype=str)
word_pattern = '[契解]約'

def replace_by_accessor():
    df["text1"] = df["text"].str.replace(word_pattern, 'XXX', regex=True)

def replace_by_ordinal():
    df["text2"] = df["text"].replace(word_pattern, 'XXX', regex=True)
    
for func in [replace_by_accessor, replace_by_ordinal]:
    print(func)
    %timeit func()

Out

pandas == 0.25.3
> <function replace_by_accessor at 0x7fc054daff28>
> 523 µs ± 11.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> <function replace_by_ordinal at 0x7fc054dafea0>
> 483 µs ± 15.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

pandas == 1.0.1
> <function replace_by_accessor at 0x7f8864198ae8>
> 562 µs ± 40 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> <function replace_by_ordinal at 0x7f8864198a60>
> 584 µs ± 18.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
関数 pandas ver 実行時間 実行時間% (per replace_by_accessor, pandas==0.25.3)
replace_by_accessor 0.25.3 523µs 100%
replace_by_ordinal 0.25.3 483µs 92%
replace_by_accessor 1.0.1 (latest) 562µs 107%
replace_by_ordinal 1.0.1 (latest) 584µs 112%

この記事を書くまでの筆者環境は 0.25.3 であったため、このTipsを載せましたが、1.0.1 では実行時間が逆転して str アクセサのほうが短くなっています。

また、どちらの方法もバージョン更新後の方が実行時間がかかるようになっているため、latest な pandas はパフォーマンスという点については必ずしも改善されているわけでは無いと言えます。

re2

Google が開発した re2 エンジンは C++ で書かれた DFA型(deterministic finite automaton) の高速な正規表現エンジンです。

Python の re パッケージで用いられているものとは正規表現エンジンのタイプが異なり、実行できない文法も存在します。（後方参照や再帰機能）

この記事では re2 エンジンについて特に深追いはしません。以下の記事や書籍には更に詳しい解説がされています。

naoyat.hatenablog.jp

正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)

正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)

実際のソースコードでも実行時間が短縮されているかどうか確認してみます。

In

import re
import re2
import timeit

target_text1 = 'kou123otsu'
digit_pattern = r'\d+'

target_text2 = 'https://subdomain.company.co.jp/{}/index.html'.format('/'.join([chr(i) for i in range(97, 97+26)]))
subdomain_pattern = r'$https?://([a-z]+)\.[a-z]+(?:\.co\.jp|\.ac\.jp)/(?:[a-z]+/)*/(?:index|title).html'

counts = [100, 1000, 10000]


def search_by_re(count, target, pat):
    regex = re.compile(pat)
    for _ in range(count):
        regex.search(target)


def search_by_re2(count, target, pat):
    regex2 = re2.compile(pat)
    for _ in range(count):
        regex2.search(target)


for func in [search_by_re, search_by_re2]:
    print(func)
    
    print('target : ' + target_text1)
    print('pattern : ' + digit_pattern)
    
    for count in counts:        
        %timeit func(count, target_text1, digit_pattern)
        
    print('target : ' + target_text2)
    print('pattern : ' + subdomain_pattern)
    
    for count in counts: 
        %timeit func(count, target_text2, subdomain_pattern)

Out

> <function search_by_re at 0x7f8863ad80d0>
> target : kou123otsu
> pattern : \d+
> 42.6 µs ± 313 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> 424 µs ± 2.86 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> 4.52 ms ± 36.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
> target : https://subdomain.company.co.jp/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y/z/index.html
> pattern : $https?://([a-z]+)\.[a-z]+(?:\.co\.jp|\.ac\.jp)/(?:[a-z]+/)*/(?:index|title).html
> 59.9 µs ± 643 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> 595 µs ± 2.13 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> 6.02 ms ± 65.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
> <function search_by_re2 at 0x7f8863ad8620>
> target : kou123otsu
> pattern : \d+
> 137 µs ± 821 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> 1.21 ms ± 22.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> 11.8 ms ± 87.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
> target : https://subdomain.company.co.jp/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y/z/index.html
> pattern : $https?://([a-z]+)\.[a-z]+(?:\.co\.jp|\.ac\.jp)/(?:[a-z]+/)*/(?:index|title).html
> 89.2 µs ± 1.55 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> 521 µs ± 7.27 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> 4.81 ms ± 67.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
関数 pattern 実行回数 実行時間 実行時間% (per search_by_re)
search_by_re digit 100 42.6µs 100%
search_by_re2 digit 100 137µs 322%
search_by_re digit 1000 424µs 100%
search_by_re2 digit 1000 1.21ms 285%
search_by_re digit 10000 4.52ms 100%
search_by_re2 digit 10000 11.8ms 261%
search_by_re subdomain 100 59.9µs 100%
search_by_re2 subdomain 100 89.2µs 149%
search_by_re subdomain 1000 595µs 100%
search_by_re2 subdomain 1000 521μs 88%
search_by_re subdomain 10000 6.02ms 100%
search_by_re2 subdomain 10000 4.81ms 80%

先程紹介の書籍内にも解説があり、深く原因を追求することは本記事では避けますが、必ずしも re2 のほうが優れているというわけではなく、どういった正規表現を用いるか、実行回数のスケールに応じて結果が異なっています。

例えば、\d+ の正規表現については re を用いた処理のほうがパフォーマンスが高いのに対し、サブドメインを取得する２つめの正規表現については、実行回数のスケールが増えるに従い、re2 を用いた処理のほうが徐々にパフォーマンスが高くなっています。

パフォーマンスの改善によるサービス全体への改善成果と、正規表現のパターンに応じてライブラリの使い分けをするコストを踏まえてこの類の改善はしていきたいところです。

広告

この記事はMNTSQ勤務中に書かれた。

MNTSQは正規表現のパフォーマンス向上に関心のあるエンジニアを募集しています。

www.wantedly.com

参考リンク

*1:この記事ではコンパイルという単語の意味について深追いすることはしません。コンパイルの内部の仕組みは正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)に詳しいです。