最適化された文字列挿入アルゴリズム

Question

巨大なコード（平均長900000文字）に特定の一致文字列の前後に文字列を挿入する小さな部分があります。

例：

Loremのイプサムは、単に印刷と植字 業界のダミーテキストです。 Lorem Ipsumは、未知のプリンタがタイプのガレーを取り、 がタイプの標本を作るためにそれをスクランブルした1500s以来、これまでに業界標準のダミーテキスト であった。

Loremのイプサムは<span class="class1 class2">printing</span>と植字業界の単にダミーテキストです。で置き換え

Lorem Ipsumは<span class="class1 class2 class3">been</span>業界の標準的なダミーテキスト<span class="class1">ever since the 1500s</span>を持っています。これは、未知のプリンタがタイプのガレーを取り、それをスクランブルしてタイプの標本を作るときです。

---

これまでのところ良いです。検索と置換ができるだけですが、内容は幾分意味があるので、その場合はprintingが置き換えられましたが、テキストの他の場所にはない可能性があります。 私たちが行ったことは、テキストを置き換えたいところのインデックスだったので、すべての置換の開始位置と終了位置を取得します。

現在のコード：900000文字長い文字列を解析

new_val = huge_string_goes_here 
entities.each { |entity| 
    add_before = "<span class=\"#{entity.getStuff}\">" 
    add_after = '</span>' 

    new_val.insert(entity.getStart+increment, add_before) 
    increment = increment+add_before.length 
    new_val.insert(entity.getEnd+increment, add_after) 
    increment = increment+add_after.length 
} 

は約15〜20秒を取っています。

私たちがどのように最適化できるかについてご意見はありますか？操作のこの種のは、はるかに高速ネイティブに解釈したコードと比べなければなりません -

は

Answer 1

はあなたのための一致指数を見つけることができたC extension module for Rubyを書いて考えてみていただきありがとうございます。インデックスを取得したら、前/後のテキストを挿入するためにRubyを使用することができます。パフォーマンスがさらに向上する必要がある場合は、Cですべてを実行することを検討してください。

任意の最適化と同様に、 「最適化」が最適化されていないコードを実際に改善することを確認することです。いくつかのサンプルケースのベンチマークを書いて、純粋なRubyコードの所要時間を記録し、ネイティブエクステンションを使用して同じベンチマークを実行し、パフォーマンスが実際に優れているかどうかを確認します。

Answer 2

私はこの種のタスクにfomaを使用したいと思いますが、セマンティクスをどれだけうまく統合できるかはわかりません。それは命令的思考とは異なりますが、その考え方を知っていれば、かなり簡単です。 Fomaはオープンソースの実装でxfstなので、そのリソースを使うことができます。

Answer 3

これを行うために低レベルの言語に行きたくない場合は、ソース文字列を一度スキャンして書き出すように思考を変更すると便利ですこれは、〜900000-N文字すべてを挿入ポイントNの後ろに移動する必要がなくなるためです。

これらの操作を非常に高速にするために特別な表現があります（ropesなど）が、このような場合は必要ありません。

編集：無視されている、および/またはそれらが現代を説明していない巨大な定数要因のために、良いbig-Osを持つ多くの古いデータ構造（およびそれに関してもあまりにも重要）アーキテクチャ（例えば、キャッシュ、vsの検索）。ロープは実際には速くなるためにはポインタ集中型であるように思えますが、一般的なバッファ編集の場合はgap bufferのようなものを使用すればさらにうまくいくでしょう。