大きなテキスト ファイルのインデックスを追跡する必要があります。std::map簡単なハックとして、インデックスとそれに付随するデータを保持してきました。ユーザーがテキストの 230,400 文字にいる場合、テキストのメタデータを表示できます。
マップが大きくなったので、(予想どおり) いくつかの速度の問題が発生しています。
たとえば、テキストが最初に変更された場合、マップ内のその位置の後のインデックスを 1 つインクリメントする必要があります (O(N) 操作)。
これを O(log N) の複雑さに変更する良い方法は何ですか? 私は近い AVL Arraysを見てきました。
更新と検索に O(log n) の時間を期待しています。たとえば、ユーザーがテキスト配列の文字 500,000 を使用している場合、その文字のメタ データがあるかどうかをすばやく見つけたいと考えています。
(追加するのを忘れました: ユーザーはいつでもメタデータを追加できます)
簡単。オフセットのバイナリ ツリーを作成します。
任意のオフセットの値は、ノードが右の子である場合はいつでもオフセットを追加して、リーフからルートまでツリーをトラバースすることによって計算されます。
次に、ファイルの早い段階でテキストを追加すると、変更されるオフセットの親であるノードのオフセットを更新するだけで済みます。つまり、最初のオフセットの前にテキストを追加すると、ルート ノードに追加される文字数が追加されます。これで、オフセットの半分が修正されました。次に、左の子にトラバースし、オフセットを再度追加します。現在、オフセットの 3/4 が更新されています。すべてのオフセットが更新されるまで、左の子をトラバースしてオフセットを追加し続けます。
@OP:
8 文字のテキスト バッファと、奇数バイトへの 4 つのオフセットがあるとします。
the tree: 5
/ \
3 2
/ \ / \
1 0 0 0
sum of right
children (indices) 1 3 5 7
ここで、オフセット 4 に 2 バイトを挿入したとします。バッファは次のとおりです。
01234567
今その
0123xx4567
したがって、変更された配列の部分を支配するノードのみを変更します。この場合、ルート ノードだけを変更する必要があります。
the tree: 7
/ \
3 2
/ \ / \
1 0 0 0
sum of right
children (indices) 1 3 7 9
総和の規則は、葉から根へと歩きます。私がその親の右の子である場合、自分の親の値を自分自身に合計します。
現在の場所にインデックスがあるかどうかを確認するには、ルートから始めて、このオフセットが自分の場所よりも小さいかどうかを尋ねます。はいの場合、左にトラバースして何も追加しません。いいえの場合、右にトラバースして値をインデックスに追加します。トラバーサルの最後に値がインデックスと等しい場合、はい、注釈があります。最小インデックスと最大インデックスを使用して同様の探索を行い、範囲内のすべてのインデックスを支配するノードを見つけて、表示しているテキストのすべてのインデックスを見つけることができます。
ああ、これは単なるおもちゃの例です。実際には、定期的にツリーのバランスを取り直す必要があります。そうしないと、ファイルの一部だけに新しいインデックスを追加し続けると、バランスが崩れたツリーが得られ、最悪の場合、パフォーマンスが O( log2 n) ですが、O(n) になります。ツリーのバランスを保つには、「赤/黒ツリー」のようなバランスの取れたバイナリ ツリーを実装する必要があります。これにより、O(log2 n) のパフォーマンスが保証されます。ここで、N はメタデータの数です。
インデックスを保存しないでください! それを行うと同時にパフォーマンスを向上させる方法はありませんO(n)-配列の先頭に文字を追加すると、n - 1インデックスをインクリメントする必要があり、それを回避する方法はありません。
しかし、代わりに部分文字列の長さを保存すると、ツリー構造のレベルごとに 1 つ変更するだけで済み、O(log n). 私の（テストされていない）解決策は、ノードにメタデータが添付されたRopeを使用することです-少しいじる必要があるかもしれませんが、それはしっかりした基盤だと思います。
それが役立つことを願っています!