データ取得時のループとバイナリ検索のパフォーマンス

Question

私はnレコード数（キー、値）を持っているとします。

今度は値を取得するためにx個のキーを探したいと思います。

xが小さいと、バイナリ検索がすべてのレコードをループして正しいキーを探すよりも効率的です。 BinarySearchはJava 8の配列の一部です。検索を実行する前に配列が既にソートされていると仮定すると、

だから私の時間計算量はO（XログN）である+ O（X）
は説明：

• Oは（Nをログ）バイナリサーチ
の複雑さであります
• O（X）は、価値を得ることの複雑さです。
• O（XログN）私はXが大きすぎる（近いNの値）になった場合、

のためにしかし、いくつかのポイントを見てみたいレコードの数に会費、それはと思われますちょうど私の記録のすべてを1つのループを実行し、その後、私は値を出すために必要なすべてのキーと比較すると、より効率的である...この解決のために

for(Record record : records){ 

    //Since the columns that I look for start with a specific prefix.   
    //This one is one of the factor that makes me confused 
    //when checking the performance. 

    if(record.key.startWith(key-family){ 

     switch(record.key){ 
      case key 0: 
      getvalue 
      break; 

      ....... 

      case key x: 
      getvalue 
      break; 
     } 
    } 
} 

、私の複雑さはO（N）+ですO（NX）
は説明：

• Oは（N）はforループ
• O（NXの複雑さ）switch文の複雑さとなっ値OUT（最悪の場合）までですループが行われます。

レコードのキーの出現が一様ではないとすれば、一部のレコードコレクションでは、キーファミリから始まるキーの数が大幅に異なり、他のレコードコレクションと比較されます。

私の質問は以下のとおりです。

1. どのように我々はXが大きすぎると、バイナリ検索ソリューションとなって非効率性をするときに定義する必要がありますか？

2. 私はあなたから学ぶことができるものはありますか？ :)

ありがとうございます。

Answer 1

XがNに近い場合、Xキーのバイナリ検索はO（N log N）になります。

Xキーのスイッチステートメントを使用した線形検索は、Nと思われます。 スイッチが純粋なジャンプテーブルとして実装されている場合。 Javaでは、tableswitch and tablelookupというインテリジェントな組み合わせが使用されています。値の配列で即時ジャンプテーブルと（低速の）ルックアップが使用されます。たぶんスイッチにO（log X）もかかるので、合計でN（log N）にする必要があります。

N値をインデックスとして使用することで、巨大なスイッチを自分で実行できます。 数字がN（または4N）の範囲にあれば実現可能です。それは配列があまりにも疎ではないでしょう。

次に、BitSetを作成することができます。しかし実生活はめったに良いものではありません。

「レコード」という言葉を見ても、私はそれをデータベースに任せています。

しかし、素敵なソリューションを使用すると、Xキーを並べ替える場合は、私番目のキーのためのバイナリ検索は、（i-1）の発見/挿入postionで開始することができます

あり^thキー。したがって、それはO（N log N）ではなくより少ない。

ix = Arrays.binarySearch(array, ix, array.length, key); 
if (ix < 0) { // Not found, insert position is -x-1 or ~x 
    ix = ~ix; // Make it the insert position (x ^= -1; would do too) 
} 

非対称性があるように：これまで減少範囲でバイナリ検索が、私は、対称再帰バイナリバイナリ・サーチを行いました。パフォーマンスのためではなく、アルゴリズムのために。

/** 
* @param array sorted 
* @param keys sorted 
* @return found keys 
*/ 
static Set<Integer> search(int[] array, int[] keys) { 
    Set<Integer> foundKeys = new HashSet<>(); 
    find(foundKeys, array, 0, array.length, keys, 0, keys.length); 
    return foundKeys 
} 

private static find(Set<Integer> foundKeys, 
     int[] array, int a0, int an, 
     int[] keys, int k0, int kn) { 
    if (k0 < kn) { 
     int k = (k0 + kn)/2; 
     int key = keys[k]; 
     int a = Arrays.binarySearch(array, a0, an, key); 
     if (a >= 0) { 
      foundKeys.add(key); 
     } else { 
      a = ~a; 
     } 
     find(foundKeys, array, a0, a, keys, k0, k); 
     find(foundKeys, array, a, an, keys, k + 1, kn); 
     // The overlap at a/repetition of a is due to: 
     // - not found 
     // - found but keys theoretically might contain doubles 
    } 
} 

（O（XログX）の費用がかかりますが、キーのソートが、コンパイラは同じでした。）

Answer 2

1. バイナリ検索では入力をソートする必要がありますが、これは効率的な方法ではありません。入力がソートされていないと仮定します。

2. ループはすべてのレコードを通過する必要があります。

3. キーのハッシュは、比較操作とフェッチ操作のパフォーマンスを向上させるためのものです。

IMHO、オプション3は、我々は、空間、時間の複雑さと関係するトレードオフの面で比較するとはるかに優れています。 Javaでは、ほとんどの場合、HashMapを使用することができます（大きなデータのような問題に対処していないと仮定して）。