13

バックグラウンド

整数のシーケンスの大規模なコレクション (〜数千) があります。各シーケンスには次のプロパティがあります。

  1. 長さは 12 です。
  2. シーケンス要素の順序は重要ではありません。
  3. 同じ順序で要素が 2 回出現することはありません。
  4. すべての要素が約 300 未満です。

プロパティ 2. と 3. は、シーケンスが実際には setであることを暗示していますが、アクセス速度を最大化するために C 配列として格納されていることに注意してください。

新しいシーケンスがコレクションに既に存在するかどうかを確認するための適切な C++ アルゴリズムを探しています。そうでない場合は、新しいシーケンスがコレクションに追加されます。ハッシュ テーブルを使用することを考えました (ただし、C++11 コンストラクトや Boost などの外部ライブラリは使用できないことに注意してください)。シーケンスをハッシュし、値を a に保存することstd::setもオプションです。衝突が十分にまれである場合、衝突は無視できるからです。他の提案も大歓迎です。

質問

可換ハッシュ関数、つまりシーケンス内の要素の順序に依存しない関数が必要です。最初にシーケンスを正規の形式 (並べ替えなど) に縮小し、次に標準のハッシュ関数を使用することを考えました (以下の参考文献を参照)。並べ替え。私が知る限り、以下で参照されている関数はどれも可換ではありません。理想的には、ハッシュ関数は、要素が繰り返されないという事実も利用する必要があります。スピードは非常に重要です。

助言がありますか？

4

5 に答える 5

6

これが基本的な考え方です。自由に変更してください。

  1. 整数のハッシュは単なるアイデンティティです。

  2. からの式を使用して、boost::hash_combine結合ハッシュを取得します。

  3. 配列をソートして、一意の代表を取得します。

コード：

#include <algorithm>

std::size_t array_hash(int (&array)[12])
{
    int a[12];
    std::copy(array, array + 12, a);
    std::sort(a, a + 12);

    std::size_t result = 0;

    for (int * p = a; p != a + 12; ++p)
    {
        std::size_t const h = *p; // the "identity hash"

        result ^= h + 0x9e3779b9 + (result << 6) + (result >> 2);
    }

    return result;
}

更新：それをスクラッチします。質問を編集して、まったく別のものにしました。

すべての数値が最大 300 の場合、ソートされた配列をそれぞれ 9 ビット、つまり 108 ビットに圧縮できます。「順序付けされていない」プロパティは、約 29 ビットである余分な 12! を節約するだけなので、実際には違いはありません。

128ビットの符号なし整数型を探して、ソートされパックされた整数のセットを直接格納することができます。または、その範囲を 2 つの 64 ビット整数に分割し、上記のようにハッシュを計算できます。

uint64_t hash = lower_part + 0x9e3779b9 + (upper_part << 6) + (upper_part >> 2);

(または0x9E3779B97F4A7C15、64 ビット バージョンのマジック ナンバーとして使用することもできます。)

于 2012-10-11T13:54:44.310 に答える
4

サイズ 300 のビットセットで、12 個の整数のそれぞれに対応するビットを切り替えることができます。次に、boost::hash_combine の式を使用して、10 個の 32 ビット整数を結合し、このビットセットを実装します。

これは交換可能なハッシュ関数を提供し、ソートを使用せず、要素が繰り返されないという事実を利用します。

このアプローチは、任意のビットセット サイズを選択し、12 個の整数のそれぞれに任意の数のビットを設定またはトグルする場合に一般化できます (300 個の値のそれぞれに設定/トグルするビットは、ハッシュ関数または事前に計算されたルックアップ テーブル)。これにより、ブルーム フィルターまたは関連する構造が生成されます。

サイズ 32 ビットまたは 64 ビットのブルーム フィルターを選択できます。この場合、大きなビット ベクトルの断片を 1 つのハッシュ値に結合する必要はありません。サイズ 32 のブルーム フィルターの従来の実装の場合、ハッシュ関数 (またはルックアップ テーブルの各値のゼロ以外のビット) の最適な数は 2 です。

古典的なブルーム フィルターの "or" 操作の代わりに "xor" を選択し、ルックアップ テーブルの各値に半分の非ゼロ ビットを使用すると、Jim Balter が言及した解決策が得られます。

「or」演算の代わりに「+」を選択し、ルックアップ テーブルの各値に約半分の非ゼロ ビットを使用すると、Konrad Rudolph によって提案されたものと同様の解決策が得られます。

于 2012-10-11T14:36:49.687 に答える
4

シーケンスの要素を数値順に並べ替えてから、シーケンスをtriに格納します。トライの各レベルは、そのレベルで要素を検索するデータ構造です...その中に含まれる要素の数に応じて、異なるデータ構造を使用できます...たとえば、リンクされたリスト、二分探索木、またはソートされたベクトル。

トライではなくハッシュ テーブルを使用する場合でも、要素を数値的に並べ替えてから、これらの非可換ハッシュ関数のいずれかを適用できます。シーケンスを比較するには、要素をソートする必要があります。これは、ハッシュ テーブルの衝突が発生するためです。並べ替える必要がない場合は、各要素に一定の係数を掛けて、int のビット全体に塗りつぶすことができます (そのような係数を見つけるための理論はありますが、実験的に見つけることができます)。結果。または、テーブルで ~300 の値を検索し、それらを XOR を介して適切に混合される一意の値にマッピングすることもできます (それぞれの値は、0 ビットと 1 ビットの数が等しくなるように選択されたランダムな値である可能性があります。各 XOR は、ビットのランダムな半分、これが最適です)。

于 2012-10-11T19:03:53.800 に答える
4

sum 関数をハッシュとして使用するだけで、それがどこまで到達するかを確認できます。これは、データの非反復特性や、データがすべて 300 未満であるという事実を利用していません。一方、非常に高速です。

std::size_t hash(int (&arr)[12]) {
    return std::accumulate(arr, arr + 12, 0);
}

関数は順序を認識しない必要があるため、最初に並べ替えを行わずに入力値の限られた範囲を利用するスマートな方法がわかりません。これが絶対に必要な場合は、衝突に関して、ソート ネットワーク(つまり、多数のif…<code>else ステートメント) をハードコーディングして、12 個の値をその場でソートします (ただし、ソート ネットワークがどのように12 個の値は次のように見えるか、実用的である場合でも)。

EDITコメントでの議論の後、衝突を減らすための非常に良い方法があります.合計する前に、配列内のすべての値を整数乗に上げます。これを行う最も簡単な方法は、transform. これはコピーを生成しますが、それでもおそらく非常に高速です。

struct pow2 {
    int operator ()(int n) const { return n * n; }
};

std::size_t hash(int (&arr)[12]) {
    int raised[12];
    std::transform(arr, arr + 12, raised, pow2());
    return std::accumulate(raised, raised + 12, 0);
}
于 2012-10-11T14:02:38.300 に答える
2

Jim Balter の回答は、私が最終的にコード化したものに最も近いものだったので受け入れましたが、すべての回答がその有用性に対して +1 を付けられました。

これが私が最終的に得たアルゴリズムです。私は、300 個の 64 ビット整数を生成する小さな Python スクリプトを作成し、バイナリ表現に正確に 32 個の true ビットと 32 個の false ビットが含まれるようにしました。真のビットの位置はランダムに分布しています。

import itertools
import random
import sys

def random_combination(iterable, r):
    "Random selection from itertools.combinations(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.sample(xrange(n), r))
    return tuple(pool[i] for i in indices)

mask_size = 64
mask_size_over_2 = mask_size/2

nmasks = 300

suffix='UL'

print 'HashType mask[' + str(nmasks) + '] = {'
for i in range(nmasks):
    combo = random_combination(xrange(mask_size),mask_size_over_2)
    mask = 0;
    for j in combo:
        mask |= (1<<j);
    if(i<nmasks-1):
        print '\t' + str(mask) + suffix + ','
    else:
        print '\t' + str(mask) + suffix + ' };'

スクリプトによって生成された C++ 配列は、次のように使用されます。

typedef int_least64_t HashType;

const int maxTableSize = 300;

HashType mask[maxTableSize] = {
  // generated array goes here
};

inline HashType xorrer(HashType const &l, HashType const &r) {
  return l^mask[r];
}

HashType hashConfig(HashType *sequence, int n) {
  return std::accumulate(sequence, sequence+n, (HashType)0, xorrer);
}

このアルゴリズムは、私が試したものの中で断然最速です ( this、thisはキューブ、thisはサイズ 300 のビットセット)。私の「典型的な」整数シーケンスでは、衝突率は 1E-7 よりも小さく、これは私の目的には完全に受け入れられます。

于 2012-10-15T16:49:30.780 に答える