高速な連結操作と編集操作を備えた文字列の表現が必要です。「Ropes: an Alternative to Strings」という論文を読みましたが、1995 年以降、この分野で大きな改善はありましたか?
編集: 以前に検討した可能性の 1 つは、文字列を葉として持つ2 ～ 3 本の指の木を使用することですが、詳細な分析は行っていません。これにより、ロープの逆とは対照的に、償却された一定時間の両端の追加/削除と対数 (小さい文字列のチャンクの数) の連結が得られます。
1152 次
1 に答える
1
これは古い質問です。誰かこれを読んでくれないだろうか。しかし、それでも興味をそそられます。あなたのコメントでは、あなたが探していると言っています：
より高速な漸近線、または定数係数、またはメモリ使用量の削減
ええと、ロープには O(1) の挿入と O(n) の反復があります。それ以上のことはできません。部分文字列とインデックス作成は、明らかにコストが高くなります。ただし、大規模なドキュメントのほとんどのユース ケースでは、編集やランダム アクセスは必要ありません。最後にのみ連結する場合、文字列の 1D ベクトル/リストによって挿入時定数が改善される可能性があります。文字列の連結が非常に遅いため、JavaScript でこれを使用していました。
メモリ表現は、文字列を使用するよりも効率が悪いと言われています。私はそれを疑います: ガベージ コレクションを備えた言語で作業している場合、ロープを使用すると、複数の場所で同じ文字列フラグメント インスタンスを使用できます。HTML ドキュメントを表すロープには、多くDIVの 、 、SPANおよびLINK要素があります。これは、これらのタグがコンパイル時定数であり、それらをロープに直接追加すると仮定すると、自動的に発生することさえあります。このような短いフレーズであっても、ロープ ドキュメントのサイズは大幅に縮小され、元の文字列と同程度になります。弦が長いほど、正味のゲインが得られます。
また、ツリー要素を読み取り専用にすると、サブロープ (ロープとして表現されるより長いフレーズ) を作成できます。サブロープは、複数回発生するか、ロープ ベースの文字列で共有されます。この共有の欠点は、そのようなシャード ロープ セクションを変更できないことです。それらを編集したり、ツリーのバランスを取るには、オブジェクト グラフをコピーする必要があります。ただし、ほとんど連結して反復する場合は問題ありません。Web サーバーでは、そのサーバーが提供するすべての HTML ドキュメントで共有される CSS スタイルシート宣言を表すサブロープを保持できます。
于 2011-02-03T20:00:44.570 に答える