1

整数を指定すると、小さなセットから一致するものを見つける必要があります。ほとんどの場合、整数はセットに含まれません。ほとんどの検索アルゴリズムでは、これが最悪のケースです (最も時間がかかります)。しかし、このアプリケーションの場合、検索時間は、検索が失敗する速さに左右されます。したがって、最良のケースが「見つからない」アルゴリズムが必要です。

そのようなものは存在しますか？

整数はランダムではなく、配列インデックスです。たとえば、0..10k (15 ビット) です。セットには 0..7 の整数が含まれますが、これは単純な線形検索には十分な数です。しかし、それはほとんどすべてのケースで最悪のケースです。

私が考えることができる唯一のものはブルームフィルターでしょう. F(int) = Set Bit (i AND 1Fh) を定義します (つまり、1 ビットが設定された 32 ビット整数)。各セットで、F(各要素) (n 要素に対して最大 n ビットが設定された 32 ビット整数) の OR 演算された値を一緒に格納します。検索は IF (F(i) AND F(set))>0 となり、線形検索を実行します。

したがって、少なくとも 1 つのセット要素がテスト整数 i と同じ下位 5 ビットを持たない限り、検索は実行されません。2 番目のテストは、次に低い 5 ビットに基づいて追加できます。

より良いアイデアはありますか？

4

1 に答える 1

0

私が想像できる最速のアルゴリズムは、すぐに成功または失敗しますが、ブール値の巨大な配列0..MaxIntであり、Array[SetMember]のTrueを除いてすべてFalseです。検索は単純な配列ルックアップになります。

Found = Array[Test]

しかし、メモリフットプリントはばかげています。一般的な最適化はハッシュ配列です。

テストとして、セットメンバーのビットを使用してパーフェクトハッシュを実装しました。関数PHash（int）は、整数0..15を返します。これは、一致するものが存在する場合に一致する配列インデックスです。検索は次のとおりです。

IF Array[PHash(Test)] = Test 
  THEN Found at Index PHash(Test) 
  ELSE Not Found

プロファイリングがこれが線形探索よりも遅いことを示していることはおそらく誰も驚かないでしょう。（はぁ）

もちろん、単一のハッシュで15ビット整数を個別の4ビット整数に減らすことはできません。私は多くの異なるハッシュ関数を使用しています。セットを生成するために、どの関数がそのセットに対して個別の4ビットハッシュを生成するかを見つけ、そのセットをハッシュ関数ポインターと16要素の配列として格納します。各配列要素はXまたは1つのセットメンバーのいずれかであり、Xはセット範囲内にありません。（パーフェクトハッシュが見つからないと、例外がスローされますが、これはまだ発生していません。）プログラムの開始時に一度実行されるため、プロファイリングではこのオーバーヘッドは重要ではありません。

セット内のテスト整数を見つけるには、Set.HashFunction（Test）を呼び出し、テストをそのSet.Array要素と比較します。その最終的な比較は、線形探索の各ステップと同じです。より速くするには、ハッシュ関数は線形探索の残りの比較よりも速くなければなりません。したがって、これはより高速なアルゴリズムである可能性がありますが、十分に大きいセットサイズの場合のみです。

私はそのセットサイズを見つけるために実験していません。とにかく、それは各ハッシュ関数の速度に依存します。

于 2012-11-23T01:21:19.813 に答える