4

だから、ここに私の小さな問題があります。

それぞれ L <= c 0 ... c n < H の項目を含むバケット a 0 ... a nのリストがあるとします。LとHのリミットを決めることができます。あまり役に立たないとは思いますが、動的に更新することもできます。

バケットの順序は重要です。私は行ってそれらを交換することはできません。

ここで、次のようにこれらのバケットにインデックスを付けたいと思います。

  • アイテムの総数を知っている
  • i番目の要素を検索できます
  • 任意のバケットからアイテムを追加/削除し、インデックスを効率的に更新できます

簡単そうですよね？これらの基準を見て、私はすぐにフェンウィック ツリーについて考えました。それが彼らが本当に意図していることです。

ただし、ユースケースについて考えると、他のいくつかのユースケースが忍び寄ります。

  • バケツの数が L を下回った場合、バケツは消える必要があります (まだ項目について心配する必要はありません)。
  • バケット数が H に達すると、新しいバケットがいっぱいになるため、新しいバケットを作成する必要があります

フェンウィック ツリーを効率的に編集する方法がわかりません。ツリー全体を再構築せずにノードを削除/追加します...

もちろん、L = 0 に設定して、削除が不要になるようにすることもできますが、アイテムの追加は実際には避けられません。

だからここに質問があります：

このインデックスのより良い構造または Fenwick Tree を更新する方法を知っていますか?

主な関心事は効率です。私はそれを実装する予定があるため、キャッシュ/メモリの考慮事項は心配する価値があります。

背景:

私は、B ツリーやランク付けされたスキップ リストに多少似た構造を考え出そうとしていますが、ローカライズされたインデックスを使用しています。これら 2 つの構造の問題は、インデックスがデータに沿って保持されることです。これは、キャッシュの観点から非効率的です (つまり、メモリから複数のページをフェッチする必要があります)。データベースの実装では、インデックスを実際のデータから分離したままにしておくと、キャッシュが使いやすくなり、効率が向上することが示唆されています。

4

2 に答える 2

3

私はあなたの問題を次のように理解しました：

各バケットには内部順序があり、バケット自体にも順序があるため、すべての要素には何らかの順序があり、その順序で i 番目の要素が必要です。

それを解決するには：

できることは、リーフ ノード (x1、x2、...、xn) がバケット サイズである「累積値」ツリーを維持することです。ノードの値は、直接の子の値の合計です。na を 2 の累乗に保つと単純になり (最後にサイズ 0 のバケットをいつでも埋め込むことができます)、ツリーは完全なツリーになります。

各バケットに対応して、対応するリーフ ノードへのポインタを保持します。

たとえば、バケット サイズが 2、1、4、8 であるとします。

ツリーは次のようになります

     15
    /  \
   3    12
  / \  / \
 2  1  4  8

合計数が必要な場合は、ルート ノードの値を読み取ります。

一部の xk を変更したい (つまり、対応するバケット サイズを変更したい) 場合は、親ポインターをたどってツリーをたどり、値を更新することができます。

たとえば、2 番目のバケットに 4 つのアイテムを追加すると、次のようになります (* でマークされたノードは変更されたノードです)。

     19*
    /   \
   7*    12
  / \   / \
 2  5*  4  8

i 番目の要素を見つけたい場合は、上記のツリーをたどって効率的に二分探索を行います。すでに左の子と右の子の数があります。i > 現在のノードの左の子ノードの値の場合、左の子ノードの値を減算し、右のツリーで再帰します。i <= 左の子ノードの値の場合、左に移動して再度再帰します。

上記のツリーで 9 番目の要素を見つけたいとします。

ルートの左の子は 7 < 9 なので、9 から 7 を引いて (2 を取得)、右に進みます。

2 < 4 (12 の左の子) なので、左に移動します。

3 番目のバケットに対応するリーフ ノードにいます。次に、そのバケットの 2 番目の要素を選択する必要があります。

新しいバケットを追加する必要がある場合は、新しいルートを追加してツリーのサイズを 2 倍にし (必要な場合)、既存のツリーを左側の子にし、追加したものを除いてすべてゼロのバケットを持つ新しいツリーを追加します (新しいツリーの一番左の葉になります)。これは、ツリーに新しい値を追加するための O(1) 時間で償却されます。注意点として、バケットは最後にのみ追加でき、途中には追加できません。

合計カウントの取得は O(1) です。単一のバケットの更新/アイテムのルックアップは O(logn) です。

新しいバケットを追加すると、O(1) が償却されます。

スペース使用量は O(n) です。

バイナリ ツリーの代わりに、おそらく B ツリーでも同じことができます。

于 2010-06-25T17:46:02.480 に答える
0

@Moron私はまだ答えを望んでいますが、提案に従って、これまでに思いついたことがあります。

どうやら私の小さなフェンウィック ツリーのアイデアは、簡単には適応できないようです。フェンウィック ツリーの最後に新しいバケットを追加するのは簡単ですが、途中ではできないので、それは一種の失われた原因です。

バイナリ インデックス ツリー (皮肉なことに、フェンウィックが彼の構造を説明するために使用したまさにその名前) とランク付けされたスキップ リストの 2 つのデータ構造が残っています。

通常、これはインデックスからデータを分離しませんが、次の方法でこの動作を取得できます。

  1. 間接的な使用: ノー​​ドが保持する要素は、バケット自体ではなく、バケットへのポインタです。
  2. プール割り当てを使用して、インデックス要素が互いに独立して割り当てられている場合でも、キャッシュを支援するメモリ内で近くにあるようにします。

バイナリ ツリーは自己組織化されているため、バイナリ ツリーよりもスキップ リストを好む傾向があります。

これらの構造により、 の i 番目の要素に到達できるようになりますがO(log N)、漸近的なパフォーマンスを高速化できるかどうかはわかりません。

もう 1 つの興味深い実装の詳細は、この要素へのポインターを持っているが、他の要素が挿入/削除された可能性があることです。要素のランクを今どうやって知ることができますか?

バケットがそれを所有するノードを指している場合は可能です。ただし、これは、ノードが移動してはならないか、移動したときにバケットのポインターを更新する必要があることを意味します。

于 2010-06-27T13:04:54.687 に答える