25

この質問に関連して、ユーザーEric Lippertのコメントに基づいています。

Ropeデータ構造が文字列ビルダーよりも効率的であるシナリオはありますか? 一般的なケースでは、ロープのデータ構造がネイティブの文字列または文字列ビルダーの操作よりも速度の点で優れていることはほとんどないという意見もあるため、実際にロープが優れている現実的なシナリオを見てみたいと思います。

4

5 に答える 5

27

SGI C++ 実装のドキュメンテーションには、大きな O の動作と一定の要素について詳細に説明されており、有益です。

彼らのドキュメントでは、非常に長い文字列が含まれることを想定しています。参照用に提示された例では、 10 MB の文字列について説明しています。そのようなことを扱うプログラムはほとんど書かれず、そのような要件を持つ多くのクラスの問題については、可能であれば完全な文字列を利用できるようにするのではなく、ストリームベースになるようにプログラムを作り直すことで、非常に優れた結果が得られます。そのようなロープは、ロープを単なる文字のシーケンスではなくセクション (それ自体がロープ) として適切に処理できる場合、マルチメガバイトの文字シーケンスの非ストリーミング操作用です。

重要な長所:

  • 連結/挿入がほぼ一定時間の操作になる
  • 特定の操作では、以前のロープ セクションを再利用して、メモリ内で共有できるようにする場合があります。
    • .Net 文字列は、Java 文字列とは異なり、部分文字列の文字バッファーを共有しないことに注意してください。これは、メモリ フットプリントに関して長所と短所がある選択です。ロープは、この種の問題を回避する傾向があります。
  • ロープは、必要になるまで部分文字列の遅延読み込みを許可します
    • これを正しく行うのは難しく、過度に熱心なアクセスのために無意味にレンダリングするのは非常に簡単であり、文字のシーケンスとしてではなくロープとして処理するコードを消費する必要があることに注意してください。

重大な短所:

  • ランダム読み取りアクセスは O(log n) になります
  • シーケンシャル リード アクセスの定数係数は 5 ～ 10 の間のようです
  • API を効率的に使用するには、「通常の」文字列 API のバッキング実装としてロープをドロップするだけでなく、API をロープとして扱う必要があります。

これは、いくつかの「明白な」使用法 (SGI によって明示的に言及された最初のもの) につながります。

  • 大きなファイルのバッファを編集して、簡単に元に戻す/やり直すことができます
    • ある時点で、文字列全体のストリーミングを含む変更をディスクに書き込む必要がある場合があることに注意してください。したがって、これは、ほとんどの編集が頻繁な永続化を必要とするのではなく、主にメモリに存在する場合にのみ役立ちます (たとえば、自動保存機能を介して)。
  • 重要な操作が発生するが、実際にはほとんど出力が発生しない DNA セグメントの操作
  • 文字列のローカル サブセクションを変更するマルチスレッド アルゴリズム。理論的には、このようなケースは、サブセクションのローカル コピーを取得してから再結合する必要なく、スレッドとコアを分離するために分割できます。これにより、かなりのメモリが節約されるだけでなく、最後にコストのかかるシリアル結合操作が回避されます。

文字列内のドメイン固有の動作を、Rope 実装への比較的単純な拡張と組み合わせて許可できる場合があります。

  • かなりの数の共通部分文字列を含む読み取り専用文字列は、メモリを大幅に節約するために単純なインターンに適しています。
  • まばらな構造を持つ文字列、またはかなりの局所的繰り返しを含む文字列は、妥当なレベルのランダム アクセスを許可しながら、ランレングス エンコーディングに適しています。
  • 部分文字列の境界自体が情報を格納できる「ノード」ですが、そのような構造は、めったに変更されず、頻繁に読み取られる場合は、基数トライとして実行する方がよい可能性が非常に高くなります。

リストされた例からわかるように、すべてが「ニッチ」カテゴリに分類されます。さらに、代わりにストリーム処理操作としてアルゴリズムを書き直す意思がある/できる場合、いくつかは優れた代替手段を備えている可能性があります。

于 2009-12-14T15:43:51.447 に答える
12

第10 回 ICFP プログラミング コンテスト は、基本的に、効率的な解決のためにロープ データ構造を使用する人々に依存していました。これは、妥当な時間内に VM を実行するための重要なトリックでした。

Rope は、接頭辞がたくさんある場合に優れており (明らかに、"prepending" という単語は IT 関係者によって作成されたものであり、適切な単語ではありません!)、挿入には優れている可能性があります。StringBuilders は連続メモリを使用するため、追加の場合にのみ効率的に機能します。

したがって、StringBuilder は、フラグメントを追加して文字列を作成するのに最適です (ごく一般的な使用例)。開発者はこれを何度も行う必要があるため、StringBuilders は非常に主流のテクノロジです。

ロープは編集バッファに最適です。たとえば、企業レベルの TextArea の背後にあるデータ構造などです。そのため (Ropes の緩和、たとえばバイナリ ツリーではなく行のリンク リスト) は UI コントロールの世界では非常に一般的ですが、それらのコントロールの開発者やユーザーにはあまり公開されていません。

ロープを回収するには、非常に大量のデータとチャーンが必要です。プロセッサはストリーム操作に非常に優れており、RAM がある場合は、プレフィックス用に再割り当てするだけで、通常のユースケースでは問題なく機能します。一番上で言及されたその競争は、私がそれが必要であると見た唯一の時でした.

于 2009-12-10T09:19:49.567 に答える
12

この質問に対する簡単な答えは「はい」です。これについてはほとんど説明する必要はありません。もちろん、Rope データ構造が文字列ビルダーよりも効率的な場合もあります。それらは異なる働きをするため、異なる目的により適しています。

(C# の観点から)

特定の状況では、バイナリ ツリーとしてのロープ データ構造の方が優れています。非常に大きな文字列値 (SQL から 100 MB 以上の xml が送られてくると考えてください) を見ている場合、ロープ データ構造はプロセス全体を大きなオブジェクト ヒープから遠ざけることができます。

5 ～ 1000 文字の文字列を見ている場合、パフォーマンスが十分に向上しない可能性があります。これは、極端な状況にある 5% の人々のために設計されたデータ構造の別のケースです。

于 2009-12-08T03:01:33.757 に答える
1

Javascript VM は、多くの場合、文字列にロープを使用します。

Higgs Javascript VM の開発者である Maxime Chevalier-Boisvert 氏は、次のように述べています。

JavaScript では、文字列の配列を使用し、最終的には Array.prototype.join を使用して、文字列の連結をかなり高速な O(n) にすることができますが、JS プログラマーが文字列を構築する傾向がある「自然な」方法は、+= 演算子を使用して追加することです。それらを段階的に構築します。JS 文字列は不変であるため、これが内部で最適化されていない場合、増分追加は O(n2 ) です。特に文字列の追加を行う SunSpider ベンチマークのために、ロープが JS エンジンに実装された可能性が高いと思います。JS エンジンの実装者はロープを使用して、以前は低速だったものをより高速にすることで、他のエンジンよりも優位に立つことができました。これらのベンチマークがなかったら、文字列の追加のパフォーマンスが悪いというコミュニティからの叫び声は、「Array.prototype.join を使用してください。ダミーです!」という声で応えられた可能性があります。

また。

于 2014-11-15T08:42:55.357 に答える
1

ほとんどの高度なテキスト エディターは、主に大きなテキストでの頻繁な挿入と削除を改善するために、テキスト本体を「一種のロープ」として表します (ただし、実装では、リーフは通常、個々の文字ではなく、テキスト ランです)。

通常、StringBuilder は追加用に最適化されており、過剰な割り当てを行うことなく、再割り当ての総数を最小限に抑えようとします。一般的な保証は (log2 N の割り当て、およびメモリの 2.5 倍未満) です。通常、文字列は一度作成され、変更されることなくしばらく使用される場合があります。

Rope は頻繁な挿入と削除に最適化されており、コピーされるデータの量を最小限に抑えようとします(より多くの割り当てによって)。線形バッファーの実装では、挿入と削除のそれぞれが O(N) になり、通常は 1 文字の挿入を表す必要があります。

于 2009-12-14T17:30:29.553 に答える