1

それぞれブロックを含むN 個のタイムラインがあるという状況があります。ブロックには特定のインデックスを持つトークンが含まれており、最大および最小のトークン インデックスを認識しています。ブロックの最初のインデックスを (タイムライン、ブロック) ペアにマッピングするインデックスもあります。次に例を示します。

Timeline 1: [1 2 5 8 9 11] [14 17 18 21] [22 23 25 26] ...
Timeline 2: [3 4 6 7 10 12] [13 15 16 19 20 24] [27 28 34 45] ...

Index:
  1 -> timeline 1, block 1
  3 -> timeline 2, block 1
  13 -> timeline 2, block 2
  14 -> timeline 1, block 2
  22 -> timeline 1, block 3
  27 -> timeline 2, block 3

ご覧のとおり、トークンの欠落はありません (ギャップはありません)。

これらのデータ構造は、私が最初に持っているものです。特定のトークン インデックスのクエリを最適化するための最良の代替データ構造は何でしょうか? トークン 19 を取得したいとします。ここで行う必要があるのは、インデックス内で二分検索を行って各タイムラインの適切なブロックを見つけ、次に各ブロック内で完全検索を行うことです。トークン 19 を使用すると、二分検索の結果、19 を含むブロック (1, 2) と (2, 2) が得られ、完全な線形検索を実行してトークン 19 を見つけます (ブロック内の二分検索は、トークンがさまざまなサイズであり、まだどのデータ構造にも含まれていません)。

ありがとうございました！

編集:すべてのタイムラインの間隔を含む間隔ツリーを使用することを考えています。問題は、クエリが依然として多くの間隔になることです。さらに、バイナリ検索に比べてあまり最適化されません。

4

3 に答える 3

0

トークン、そのタイムライン、およびブロックへのポインターを保持するオブジェクトへのt個のポインターの配列Aを持つことができます。言語が好きなメカニズムを使用して配列内の参照を保持できる場合..ブロック内でバイナリ検索ができない場合に何ができるかわかりません。

于 2012-05-18T20:35:52.100 に答える
0

たぶん、まばらな空間充填曲線を使用できますか? インデックスがある場合、それは次元を削減する関数です。空間充填曲線も同じですが、インデックスに空間情報を追加します。空間充填曲線または空間インデックスの別のデータ構造は四分木です。したがって、quadtree または kd-tree を使用して検索できます。

于 2012-05-19T03:36:58.837 に答える
0

私の頭に浮かぶ最も簡単な方法 (多くのメモリ容量を必要としない場合) は、blob 値の配列を作成することです。ここで、index はクエリ トークン (例では 19) であり、値は対応する blob 部分です。それ。ギャップがないので、配列は良いはずです。この配列の構築は O(n) で、そこでの検索は O(1) です。ただし、既存の構造もすでに最適化されているため、クエリの量が比較的多い場合にのみ、これはいくつかの利点をもたらします。(実際にはここでテストを行う必要があります。どちらの方法がより高速です。)

配列の構築:

array = []
foreach ( timeline in timelines ){
  foreach ( block in timeline){
    foreach( token in block ){
      array[token.index] = token.value
    }
  }    
}

コストがかかりすぎる場合は、トークンのタイムライン番号のみを保存してみてください。これにより、クエリが発生したときにすべてのタイムラインを検索する必要がなくなります。あなたがしなければならないことは、タイムラインを取得し、ブロックをバイナリ検索し、ブロック内で単純な前方検索を行うことだけです。

于 2012-05-18T21:12:35.940 に答える