かんちゃんの備忘録

プログラミングや言語処理、ゲームなど知的好奇心のための備忘録(個人の感想)です。

正規表現マッチングの処理時間にも気をつける

本記事は Sansan Advent Calendar 2022 - Adventar の初日の記事です。

正規表現は文字列マッチングにおいて、とても便利な機能です。 基本的に各プログラミング言語でライブラリとして実装されており、利用可能です。

そんな正規表現ですが、例えば貪欲な探索を長い文字列を対象に使うと、もちろん結構遅くなります。

どれくらい処理時間が遅くなるかを調べる簡素なツールを作り、確認してみました。

ツールを作る

ある任意の文字列(string)を含むランダムな任意の長さの文字列(random string)から、正規表現regex)に一致する表現を取り出す、ということをN回行うツールを作りました。

github.com

使い方は以下です。

$ regbench "\d+番" "背番号は10番" --search-target-length=50 --number_of_trials=10
Trying 10/10
{"times": 10, "total_elapsed_sec": 7.191700000001161e-05, "average_search_sec": 7.191700000001161e-06, "method": "search", "pattern": "\\d+番", "string": {"head_of_last_trial_string": "vAboTdcPQs", "length": 50}, "matched": {"head_of_matched": "10番"}}

引数に、正規表現、任意の文字列、その他オプションの順で渡します。

上記の場合だと、「背番号は10番」という文字列をどこかに含んだ50文字の文字列が生成されます。これを対象に正規表現「\d+番」に一致するものがないかを調べます。これを10回繰り返します。 結果、正規表現と一致するものを探す処理に約7.19e-5秒かかっていることがわかります。

マッチ時間の一例

生成する文字列長は50,000文字、試行回数は10回、re.search でマッチする要素を取得します。

以下に、正規表現や検索対象に含める文字列を変更した際の結果を示します。

正規表現 検索対象に確実に含める文字列 平均処理時間
test test 2.5970899999998993e-05
test hoge 4.0716699999999996e-05
.test test 0.0001207250000000007
.test hoge 0.0003335540999999994
.* test test 4.220839999999892e-05
.* test hoge 1.4453570459000002
.* test$ test 1.4394586875
.* test$ hoge 1.4445743792

正規表現パターンが単純な文字列や任意の一文字の場合は平均処理時間はかなり短いです。

一方で、任意の一文字以上繰り返しを含めると、結果が異なります。検索対象が確実に含まれる場合と含まれない場合で、処理時間が大きくことなります。 re.search ですので、マッチした時点で終了です。 .*test の場合、検索対象に正規表現が含まれない場合は探索時間が延びています。 これは、探索回数が多い正規表現だったためです。

一回のマッチングに1秒かかることには衝撃を受けました。

正規表現のバックトラック

正規表現で分岐が発生する場合、マッチに失敗した場合は分岐前の状態に戻り、別の分岐にマッチするかを試します。 ここでの分岐前の状態に戻る動作がバックトラックと呼ばれています。 バックトラックにより探索のステップ数が爆発的に増えていくことが、処理時間が長くなる原因です。

以下のサイトを使うと、正規表現のステップ数が確認できます。

regex101.com

これを悪用した正規表現マッチングでの過負荷によるサーバー停止を狙ったReDosというのがあるようです。

gihyo.jp

とはいえ、実装中に気づくのは難しいので確認する

防ぐために簡単に思いつくのは、理論的に理解して実装しないこと、マッチ時と非マッチ時のステップ数を確認すること、実際のデータで検証してみることかと思います。

regex101や自作ツールにより、正規表現の罠にはまらないように気をつけたいと思います。

スマブラSPのオンラインの入力遅延と付き合う

本記事は、スマブラ Advent Calendar 201920日目の記事です。

スマブラ発売から1年が経ちましたが、全く飽きる気配がなくこの面白いゲームにどれだけ時間を使ってしまうのか、と恐怖を覚えているほどです。

オンライン*1ばかりやっていたのですが、最近は宅オフやオフ会に少しずつ参加するようになり、オフラインとオンラインの両方でプレイするようになりました。

オンラインで遠方の友人と対戦に励むことができるのは、非常に素晴らしいことです。 しかしながらスマブラのオンラインの遅延で一般的に言われている6F(0.1秒)の差は、私にとっては頭を混乱させる要因の一つです。 今回は、具体的にオンラインにどう付き合うのがいいのかを自分が混乱しないためにできる限り考察します*2

2020/05/05追記:オンラインの遅延フレームの正確な測定については、スマブラSPECIAL検証Wikiをご覧ください。検証によると5F遅延のようです。

※オンラインでの遅延フレーム数6Fには検証ソースがないこと、入力可視化による簡易調査は誤差が考えられるため、表現を訂正しました。申し訳ありません。

※ PKファイヤーの話を修正しました。

*1:5体なんとかVIP程度のレベルです。

*2:遅延があるからオンラインを敬遠するというのではなく、オンラインでいかに楽しむかをよく考えるという話です。

続きを読む

朝起きるためにやることやらないこと

夜型人間 Advent Calendar 2019 10日目の記事です。

全員が正確な時計を持ち、カレンダーで予定を分単位で記録でき、いつでも連絡を取ることのできる世の中では、8時集合と言えばそれは08:00(JST/UTC+0900)集合なのです。

ニワトリが泣き出したらだとか、日が昇ったらといったアバウトな時間管理ではありません。

つまり、定められた時刻に移動し出社を勤しむには、朝のある時刻までに起きる必要があります。

今回の記事では、朝起きるために意識してやるやらないとしていることをまとめました*1

*1:実験をしたり論文を読んだりとしっかり根拠づけしたわけではなく、自分がいいと思い込んでやっていることです。

続きを読む

1年ぶりのXonsh

本記事は Xonsh Advent Calendar 2018の16日目の記事です。

昨年の Advent Calendar 以降使っていなかった Xonsh について約1年ぶりに触ります。

ほんと少しでも書いてくれるだけでハッピー。

ということで、よりハッピーになっていただきたいのでほんの少し書きました。

Pythonのモジュールが提供する機能をパイプラインに組み込めれば便利そうだったので、コマンドを作ってみました。

導入

インストール

$ pip install xonsh

起動

$ xonsh

コマンドを作る

~/.xonshrc に関数とそのエイリアスを定義することで、 xonsh が認識します。

def _hoge():
    print("fuga")


aliases["hoge"] = _hoge

aliases が対話型シェル環境からコマンドとして利用できるコマンド群のエイリアスとなります。

関数の引数には、 argsstdin といったコマンドに対する引数や標準入出力などを定義できるようです。

こんなコマンドだと便利?

中央値や最頻値をさくっと出せると便利かもしれないと思い、コマンドを定義してみました。

# ~/.xonshrc
import statistics


def _mean(args, stdin=None, stdout=None):
    print(
        statistics.mean((float(line.strip()) for line in stdin)),
        file=stdout
    )

def _mode(args, stdin=None, stdout=None):
    print(
        statistics.mode((line.strip() for line in stdin)),
        file=stdout
    )


aliases["mean"] = _mean
aliases["mode"] = _mode

上記の関数を試してみます。

$ source ~/.xonshrc
$ seq 10 | sort -r | mean
5.5
$ echo "1\n2\n3\n2" | sort -r | mode
2
$ echo "ほげ\nふが\nほげ" | sort -r | mode
ほげ

複数列に拡張していくのは、引数の管理が大変そうです。 エラー処理も割と大変そうなので、デコレータ作るとボイラープレート減らせるのかな?と思いました。

シンプルに cut コマンドと組み合わせることで、わざわざファイルを確認するためにコードを書かなくても済みそうです。

MeCabの使い方の備忘録

Sansan Advent Calendar 2018 の1日目の記事です。

いつもお世話になっているMeCabについての備忘録です。

インストール、辞書、辞書整備、Pythonやシェルでの取り扱いまで、使い方をまとめます。 マニュアル読めば分かるよ!というかたは公式マニュアルが充実しているのでそちらを読むのがいいかと思います。

続きを読む

固定回線(IPoE方式のv6アルファ)を引いた

上京してから1年半ほどWiMAXを利用していたのですが、いろいろと限界を感じたため固定回線を引きました。

高速と言われているIPoE方式にしたのでそのまとめです。

結論としては、快適な回線を得ることができました。

  • 固定回線を引くことにしたきっかけ
  • OCN 光 v6アルファ パッケージにした
  • 開通まで1週間半
  • WiMAXとv6アルファの速度比較
  • 開通して困ったことと対策
  • まとめ

固定回線を引くことにしたきっかけ

箇条書きで挙げてみます。

  • Google DriveDropboxなどストレージへのアップロードが非常に遅い
  • 帯域が細いのか複数台での利用が厳しい(PS4で何かしら更新しているときは別の機器からは利用がほぼできない)
  • 速度やPINGが安定せずゲームが厳しい(スプラトゥーン2にハマったので安定した回線がほしかった)
  • 3日で10GB制限&シークタイム削減のために動画は480pで閲覧していた
続きを読む

サポーターズ勉強会でPythonでのスクレイピングについて登壇しました

10月10日に「Pythonで始めるスクレイピング」というタイトルでサポーターズColabで登壇しました。

発表内容の概要と振り返りを書こうと思います。

発表内容

初心者を対象に、Python言語によるWebクローリングとスクレイピングについて説明とハンズオンを行いました。

前半はスライドを用いた説明です。

導入は、そもそものクローリングとスクレイピングの概念について混同しがちな部分であるため、図を用いて整理しています。 実際にPythonライブラリを用いてページのフェッチとスクレイピングを行う方法として、requestsモジュールやBeautifulsoupなどメジャーなライブラリを紹介しました。

中盤は、Scrapyの概要やヘッドレスブラウザでの描画について述べました。 また、実際にクロールする際のマナーについてもアクセス数や頻度に注意することや、連絡先を明記することなど気をつけることがたくさんあります。

後半はGoogle Colabratoryを使ったハンズオンです。

前半のスライドの内容を実際に動作させることができます。

振り返り

良かった点は、「こんな方にオススメ」という人にしっかり伝わる資料ができたことだと思います。 スクレイピングを始めたいけど一歩目が難しい人の後押しにしっかりなったかと思います。

いまいちだった点は、時間配分です。 後半のハンズオンが非常に駆け足になってしまいました。 スマホで時間を確認すればよかったのですが、PCはスライドショーモードにはなっておらず時計が見えませんでした。 また、会場の時計も見つけることができず時間配分が感覚になってしまいました。 よほど練習した資料であれば何となくでも時間はわかるものですが、今回はそこまで詰め切れていませんでした。

ただ、コメントをかなり丁寧に書いたつもりですので、持ち帰ってじっくり見ていただけるかと思います。

ご参加いただいたみなさまありがとうございました

スクレイピングを始めてみたい人や、機械学習の学習データとしてあれこれしたい人にとってぴったりの勉強会だったかと思います。

会場の準備や勉強会登壇の機会を与えてくださいましたサポーターズCoLabさんには感謝しております。

最後に、ご参加いただいたみなさまありがとうございました。