問題タブ [ropes]

ウィキペディアから：

主な欠点は、全体的なスペース使用量が多く、インデックス作成が遅いことです。どちらも、ツリー構造が大きくなり、深くなるにつれて、より深刻になります。ただし、インデックス作成の実際のアプリケーションの多くは、文字列の反復のみを含みます。これは、リーフノードがキャッシュ効果の恩恵を受けるのに十分な大きさである限り高速のままです。

ロープとストリングの間にある種の妥協点を実装しています。基本的にはロープだけですが、連結された文字列が短い場合に連結オブジェクトを文字列に平坦化する点が異なります。これにはいくつかの理由があります。

1. 連結された文字列が短い場合、連結オブジェクトの利点は最小限に抑えられます（2つの文字列を通常の形式で連結するのにそれほど時間はかかりません）。
2. これを行うと、木の大きさ/深さが減少します（ロープの欠点が減少します）。
3. これを行うと、リーフノードのサイズが大きくなります（キャッシュをより有効に活用するため）。

ただし、長さが長くなるとロープのメリットも少なくなるので、妥協点を見つけたいと思います。「スイートスポット」は、論理的には「リーフノードがキャッシュ効果の恩恵を受けるのに十分な大きさ」の周りにあるように見えます。問題は、それがどれくらい大きいかわからないということです。

編集：私がこれを書いている間、理想的なサイズはキャッシュページのサイズであることに気づきました。それは、ロープが文字列でとにかく発生する場合にのみキャッシュミスを引き起こすためです。だから私の2番目の質問は、この推論は正しいですか？また、キャッシュページのサイズを検出するクロスプラットフォームの方法はありますか？

私の目標言語はC++です。

Ruby 正規表現が文字列以外のものと照合する場合、to_strそのオブジェクトに対してメソッドが呼び出され、照合する実際の文字列が取得されます。この動作は避けたいです。文字列ではないオブジェクトに対して正規表現を一致させたいのですが、論理的にはランダムにアクセス可能なバイトのシーケンスと考えることができ、それらへのすべてのアクセスはbyte_at()メソッドを介して仲介されます (精神的には Java のCharSequence.char_at()メソッドに似ています)。

たとえば、任意の正規表現の任意のファイルでバイト オフセットを見つけたいとします。式は複数行になる可能性があるため、一度に 1 行ずつ読み取って各行で一致を探すことはできません。ファイルが非常に大きい場合、すべてをメモリに収めることができないため、1 つの大きな文字列として読み取ることはできません。ただし、ファイルの n 番目のバイトを取得するメソッドを定義するのは簡単です (速度のために必要に応じてバッファリングとキャッシュを使用します)。

最終的には、 Ruby Quiz #137のように、完全な機能を備えたロープクラスを作成し、文字列に変換することによるパフォーマンスの低下なしに正規表現を使用できるようにしたいと考えています。

Ruby の正規表現の実装の内部に深く入り込みたくないので、洞察をいただければ幸いです。

C# でRopeデータ構造の公開実装はありますか?

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

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

別の STL コンテナーにロープを使用するのはどのような状況でしょうか?

高速な連結操作と編集操作を備えた文字列の表現が必要です。「Ropes: an Alternative to Strings」という論文を読みましたが、1995 年以降、この分野で大きな改善はありましたか?

編集: 以前に検討した可能性の 1 つは、文字列を葉として持つ2 ～ 3 本の指の木を使用することですが、詳細な分析は行っていません。これにより、ロープの逆とは対照的に、償却された一定時間の両端の追加/削除と対数 (小さい文字列のチャンクの数) の連結が得られます。

私はロープについてのこの論文「ロープ：ひもに代わるもの」を読んでいました

【同紙より図】

そして、それが今日のブラウザーがテキストボックスを実装するために使用するデータ構造であるかどうか疑問に思っていました。これにはロープやその他のデータ構造を使用しますか?

ロープはテキストボックス以外の場所で使用されていますか?

私の質問の前のタイトルは、どういうわけか、文字列の「記憶」がどのように発生するかを知りたいという意味でもありました-入力すると、提案が表示されます。今変更しました。

私が知りたいのは、入力時に文字列を格納するために使用されるデータ構造です。char 配列のような単純なものですか、それともロープのような複雑なものですか?

私はさまざまな論文を調べましたが、収集した情報は次のとおりです。

• SGI 実装とC コードは、長いロープの O(1) 時間の連結も、短いロ​​ープの ~log N 深度も保証しません。
• 異なる情報源は互いに矛盾しています。ウィキペディアは O(1) 連結を主張しています。このページでは、連結は 1 つのオペランドが小さい場合のみ O(1) であり、それ以外の場合は O(log N) であると述べています。

では、連結の時間計算量はどのくらいですか? ツリーのバランスを維持しながら、この連結の複雑さを確保するために正確にリバランスが実行されるのはいつですか? この複雑さについて話すとき、いくつかの特定の使用パターンが想定されていますか?

おはようございます、

私は言語パーサーを作成しており、現在次のことを行うロールバック キャッシュに使用する最適な構造を探しています。

• ストリームから新しい文字を要求すると、ロールバックが要求された場合に備えて、文字がキャッシュに追加されます。
• ロールバックが要求されたら、キャッシュ内の特定のポイントに戻り、別の文字が要求されたときに代わりにそこから取得できるようにします。
• トークンが見つかったら、ロールバック キャッシュ内の現在の位置までのすべてを削除します。

要するに、どのデータ構造が最適であると思われるかを知りたいです。

• 優先度 1: 文字の追加 (codePoints は歓迎される追加)
• 優先度 2: データ構造で部分文字列 (StringBuilder.delete(...) など) を実行する (または完全にクリアする)
• 優先度 3: キャッシュの文字列を作成できること (例: StringBuilder.toString())

私はすぐにあなたから話を聞くことを望む！

/usr/include/c++/4.5.1/ext/ropemy (and )にロープの実装があるようですropeimpl.h。SGI STL と比較したところ、コードはほとんど同じコードベースのようです。

その状態や、機能しているかどうかはわかりません。また、これが非常に古い古いコードなのか、進行中のコードなのかはわかりません

いずれにせよ、それを使用する方法に関する参照は見つかりませんでした（機能する場合）。私が行方不明になっていることを知っていますか？私が使用できる使用例はありますか？

編集ここで cvsの履歴を見ると、最後のアクティビティが 4 か月前であることがわかります。これはあまりアクティブではないように見えますが、放棄されたようにも見えません。