1

これは実際の問題ではなく、単なる理論構築です。

のような要素で構成される大きな配列があり[1,140,245,123443]、選択性の低いすべての整数または浮動小数点数があり、一意の値の数は配列のサイズの 10 分の 1 です。この場合、B*tree インデックス作成は適切ではありません。

ビットマップインデックスも実装してみましたが、Ruby では二項演算はあまり速くありません。

固定サイズのベクトルの 2 次元配列を検索するための適切なアルゴリズムはありますか?

そして、主な問題は、変換関数が単調でなければならない場合、値のベクトルをどのように変換するかです。そのため、次のような範囲クエリを適用できます。

(v[0]<10, v[2]>100, v[3]=32, 0.67*10^-8<v[4]<1.2154241410*10^-6)

私が持っている唯一のアイデアは、ベクトルの各コンポーネントに対して個別のソートされたインデックスを作成することです...バイナリ検索とマージ...しかし、最悪のシナリオではO（N * N）操作が必要になるため、これは悪い考えです。 ..

4

2 に答える 2

2

各「列」が既知の範囲に漠然と均等に分散していると仮定すると、各列の一連のバケットと、バケットを満たす行のリストを追跡できます。各列のバケットの数は同じでも異なっていてもかまいませんが、完全に任意です。バケットが多いほど高速ですが、メモリが少し多くなります。

my table:
range:    {1to10} {1to4m}    {-2mto2m}
row1:     {7      3427438335 420645075}
row2:     {5      3862506151 -1555396554}
row3:     {1      2793453667 -1743457796}

buckets for column 1:
bucket{1-3} : row3
bucket{4-6} : row2
bucket{7-10} : row1

buckets for column 2:
bucket{1-2m} : 
bucket{2m-4m} : row1, row2, row4

buckets for column 3:
bucket{-2m--1m} : row2, row3
bucket{-1m-0} : 
bucket{0-1m} : 
bucket{1m-2m} : row1

次に、一連の基準が与えられた場合、その基準に一致するバケット{v[0]<=5, v[2]>3*10^10}を引き出します。

 column 1:
v[0]<=5 matches buckets {1-3} and {4-6}, which is rows 2 and 3.
 column 2:
v[2]>3*10^10} matches buckets {2m-4m} and {4-6}, which is rows 1, 2 and 3.
 column 3:
"" matches all , which is rows 1, 2 and 3.

これで、探している行が3つの基準すべてを満たしていることがわかったので、すべての基準に一致したバケット内のすべての行（この場合は行2と3）を一覧表示します。この時点で、バケットの粒度によっては、大量のデータであっても残りの行数は少なくなります。この時点で残っている各行をチェックして、それらが一致するかどうかを確認するだけです。このサンプルでは、​​行2が一致しているのに、行3は一致していないことがわかります。

このアルゴリズムは技術的にはO（n）ですが、実際には、小さなバケットが多数ある場合、このアルゴリズムは非常に高速になる可能性があります。

于 2012-05-24T00:25:50.020 に答える
0

インデックスを使用する:)

基本的な考え方は、2次元配列を（元の位置を維持したまま）1次元のソートされた配列に変換し、後でバイナリ検索を適用することです。

この方法は、任意のn次元配列で機能し、可変長の次元配列と見なすことができるデータベースで広く使用されています。

于 2012-05-23T23:16:47.400 に答える