問題タブ [ropes]

私は、完全に抽象化されたオブジェクトのために C++ で Rope データ構造を実装することに取り組んでいます。私が抱えている問題は、重要な「分割」操作の実装を理解できないことです。ウィキペディアのページは役に立ちますが、あいまいで非常に理論的であり、テキストに添付されている画像はアルゴリズムの理解に役立ちません。良い実装、またはサンプル コードを提供する論文はありますか? 元の論文を読んでみましたが、どちらも役に立ちません。

ropesJavaには何がありますか?

Java の代わりに Java でそれらを初期化するにはどうすればよいですStringsか?

なぜこの概念が導入されたのですか？

ロープのデータ構造を作ろうとしています。二分木、つまり再帰的なデータ構造の一種です。

ロープの目的は、分割と連結を高速にすることです。これは、ロープ全体をコピーすることを避けることを意味します。
したがって、たとえば、ユーザーはrope1 + rope2対数時間で結果を言い、期待できる必要があります。

ただし、これには問題
があります。ロープが変更されると、その親も間接的に変更されます。
私の目標はropeの簡単な代替品を作ることなのでstring、これは受け入れられません。

これに対する私の解決策は次のとおりです。 に何らかの変更がある場合は常に、古いノードを変更せずに、わずかな変更を加えて新しいropeノードを作成します。

理論的には、これはかなりうまくいくと思います。

ただし、実際には、文字列の変更ごとに (ほとんど?)ヒープ割り当てが必要です。
1 文字の変更でも新しいヒープ オブジェクトが作成され、それ自体が遅いだけでなく、メモリの局所性が大幅に低下し、パフォーマンスに非常に悪影響を及ぼします。

この問題を解決するにはどうすればよいですか？

ロープのデータ構造について読んでいました。C++ と Qt を使用してテキスト エディターを構築することに興味があります。私の質問は次のとおりです。C++ などのプログラミング言語の組み込みの文字列操作関数は、ロープ データ構造を使用しますか? それとも、連結や削除などの文字列操作をより効率的に実行できるように、ロープを実装するための独自のコードを作成する必要がありますか?

ウィキペディアのエントリは言う：

各ノードには、文字列の長さに左側のサブツリーのすべての重みの合計を加えたものに等しい「重み」があります。したがって、2つの子を持つノードは、文字列全体を2つの部分に分割します。左側のサブツリーには、文字列の最初の部分が格納されます。右側のサブツリーには2番目の部分が格納され、その重みは2つの部分の合計です。

私は少し混乱しています。最初に、ノードの重みは文字列の長さに左側のサブツリーのすべての重みの合計を加えたものであると言います。次に、ノードに2つの子（したがって、左と右のサブツリー）がある場合、重みは、左のサブツリーだけでなく、両方の部分の合計であると表示されます。ダイアグラムを見るのは理にかなっていますが（22のすぐ下の9は9であり、7の正しい子/サブツリーは重みに寄与しないため、大きくはありません）、言い回しは私にはわかりませんか、それとも私は何かを誤解していますか？

いくつかの Python コードを書いているときに、任意の位置への挿入、アクセス、および削除を高速に実行できる、文字列のようなデータ構造が必要であることに気付きました。最初に頭に浮かんだデータ構造はロープでした。Python には既にどこかに実装されているロープ データ構造がありますか? 標準ライブラリと PyPI を調べましたが、見たことがありません。( Rope という名前の Python 用のリファクタリング ライブラリと、ワイヤ ロープを販売する Python Rope という会社があることは役に立ちません。)

たとえば、任意Stringの に対して

c: Charの後に、位置 2 に文字を挿入するb方法

アップデート

ランダムな位置で複数の効率的な挿入と削除を行うには、どの Scala コレクションを考慮する必要がありますか? String( aがそのコレクションに変換される可能性があると仮定します。)

ばかげた初心者の質問をしている場合は、お詫び申し上げます。私は C++ が初めてで (C と目的の C に精通している)、標準テンプレート ライブラリのロープを使用したいと考えていました。これは、Xcode が使用するライブラリに含まれていますか? #include <vector>マップについても同じことを試しましたが、成功しましたext/hash_map。しかし、ロープは利用できないようです。ソースをダウンロードしてプロジェクトに含めるだけでよいですか?

2 週間前に、挿入、削除、キーの検索、および 3 つの要素の範囲の合計の取得などの基本的な機能を可能にするスプレイ ツリーの実装を完了しました。この実装は、この質問の参照として、または好奇心から見つけることができます。

追加のタスクとして (オプションで期限が過ぎています。私はこれを成績のためではなく、「Google で検索」するのが容易ではない有用なデータ構造であると信じているため、これを解決しています)、Rope データ構造を実装するように依頼されました。文字列を操作して、文字列が "warlock" で指定されたキーが 0 2 2 の場合、文字列は "lowarck" になります (0 2 は部分文字列 "war" であり、"lock" は "war" を削除した後に残ったものであり、挿入します2 文字目以降は "lo"+"war"+"ck" になります)。これは 1 つのクエリにすぎませんが、30 万文字の長さの文字列に対して最大 10 万のクエリになる可能性があるため、単純なソリューションは機能しません。

私の最初の疑問は、ツリーの初期化についてです(要点を読んだ人のために、ほとんどの人にとって理解しやすいように、頂点の代わりにノードを使用します)。

これは Node クラスと NodePair クラスです。

その後、次の方法でツリーを作成します。

これにより、文字列の最初の文字 (node.key として) の node.size が 1 で、一番左の子になる非常に不均衡なツリーが作成されます。文字列の最後の文字は、size=sb.length() のルートです。

これが正しく初期化されているかどうかは完全にはわかりません。キーとサイズを指定して inorder traversal print を実行したところ、文字列全体がサイズ順で取得されました。これは私が期待していたものです。

その後、Update メソッドを次のように変更しました。

これに：（CLRSの章14.1に基づく）

次に、オリジナルの find メソッド:

これに：（CLRS Chapter 14.1のOrder Statistics-SELECTに基づく）

ただし、ご覧のとおり、このメソッドがノードを返すのに対し、元の検索は NodePair を返すため、この時点で既に問題があります。インストラクターによるNodePairの説明は次のとおりです。

結果と新しいルートのペアを返します。見つかった場合、結果は指定されたキーを持つノードへのポインターです。それ以外の場合、結果は最小の大きなキー (順序の次の値) を持つノードへのポインターです。キーがツリー内のすべてのキーよりも大きい場合、結果は null になります。

Find メソッドを使用して分割するノードを探すため、これは分割メソッドを複雑にします。これに加えて、私はこの find メソッドで NullPointerException を取得しており、他の学生から、他のエラーを回避するには非再帰バージョンを使用する必要があることを理解しているため、基本的には OS-Select の非再帰バージョンを実装する必要があります。以前の find メソッドとして NodePair を使用するか、分割メソッドを次のように変更します。

ご覧のとおり、find メソッドは NodePair の findAndRoot に割り当てられています。OS-Select の非再帰への変換に加えて、私の主な問題は、以前の find メソッドと split メソッドで NodePair が使用される方法を理解することだと思います。

最後に、これはツリーとキーを受け取り、それらを操作するメソッドの実装です。

私のコードからわかるように、私はプログラミングを学び始めて 5 か月しか経っていない初心者であり、Java を選択したので、収集した情報から、このタイプのデータ構造はより中級であることがわかります。エキスパートレベル（以前の splay treeを実装できたことにすでに驚いています。ですから、回答で私の初心者レベルを考慮してください。

PD: これは非再帰的な OS-Select の疑似コード バージョンですが、まだ NullPointerException があります。