質問: お世話になっております。 実質的に置換と同じことで遙かに処理の速い方法はありますでしょうか? 事例 たとえば以下のようにテキストの置換パターンが複数あったとします。 ``` 08A54G→タナ 08A→タ 54G→ナ ``` テキストエディタの置換のマクロでも変換していけますが、数百万字だとけっこう時間がかかります。 かかる時間とは、テキストエディタや連続置換であるかにもよりますが、速くて5分以上です。 しかし、C++などで作ったアプリなら、これと同じ表示を1秒もかからず変換できたりします。 おそらくこの仕組みは置換とは別の方法だと思いますので、その処理方法の名前を知りたいのです。 上記のようなルールのこれらのパターンを一瞬で置き換えて表示する方法はPythonなどのインタプリタでありますでしょうか? よろしくお願いいたします。
回答: 処理方法の名前はボイヤー-ムーア法、Bitapアルゴリズムなど、文字列検索アルゴリズムがあります。 しかし高々数百万字に対して5分以上は時間がかかりすぎです。 パソコンのスペックや置換パターンの数によりますが、一番原始的なブルートフォース検索アルゴリズムを用いても置換処理自体は数秒以内に完了するでしょう。 どちらかというと下記の情報処理技術者向け用語の方がお求めの回答かもしれません。 * アクセス速度 「1文字置換するたびにファイル書き出しとファイル読み込みを行い、それを数百万回繰り返す」処理と 「数百万文字をメモリ上に配置してから置換する」処理では、文字通り桁違いに処理時間が変わります。 参考: 各種メモリ/ストレージのアクセス時間,所要クロックサイクル,転送速度,容量の目安 - まとめ * 描画コスト 他の回答にあるように、もしもテキストエディタで「1文字置換する」→「数百万文字をエディタ上に再描画する」→「1文字置換する」→「数百万文字をエディタ上に再描画する」→...を数百万回繰り返していると非常に処理速度が遅くなります。 5分以上かかる原因もおそらくそれです。 「一瞬で」処理が完了する処理は置換中に描画を行わず、置換後に描画する(あるいは描画自体を行わない)仕組みです。コメントにある`pipe`による高速化はその意味でも有効です。 * マルチスレッド 上記のように置換と再描画を連続して行うと時間がかかりますが、置換処理するプロセスと並行して別のプロセスで再描画を行う処理にすることで速度の改善が見込めます。 他にも数百万文字を例えば1万文字ごとに分割して複数のプロセスで置換してから最後に結合するなど、マルチスレッド処理を適切に用いることで高速化することができます。ただしこちらは1万文字ごとの切れ目を適切に処理するよう注意が必要です。