1

キーを取得し、何らかの方法で値を返す C++ メモリ ディクショナリ コンテナーが必要です。つまり、キーが「キー リスト」に存在しない場合、最も類似したキーが検索され、値が与えられます。

助言がありますか？

編集：

コメントありがとうございます。

詳細: 簡単にするために、数値キーから始めましょう。キーがキーから 200 以内の距離にある場合は、取得します。

4

3 に答える 3

2

locality-sensitive hashingと呼ばれるものを使用する必要があり、その上に少しのコードを記述する必要があります (ほんの少しだけ、約束します。もう 1 語)。

まず、他のハッシュ テーブルを使用する必要がありますstd::map。これは、ツリーまたは他の順序付けられたデータ構造である必要があります。std::unordered_map

あなたのキーは、同様の入力をハッシュして出力を閉じる動作を持つ、局所性に敏感なハッシュになります。したがって、AAA のハッシュと AAB のハッシュは、AAA と CCC のハッシュよりも近くなります。値は、あなたが望むものになります。

「最も近い一致」を取得するには、std::map::lower_bound(またはstd::map::upper_bound) を使用して、マップから特定の入力に最も近い値を取得するだけです。

したがって、コードは次のようになります

std::map<unsigned int, some_struct> mymap;
for(;;;)
{
   mymap[locale_sensitive_hash(some_struct(some random value))] = some_struct(some random value)
}

//Now find the object we have that is nearest to some_struct(AAA)
unsigned int this_hash = locale_sensitive_hash(some_struct(AAA));
some_struct nearest_object = mymap.lower_bound(this_hash);

やった、やった。

いくつかのメモ:

これは非数値キーを想定しています。数値はすでにそれ自体の「ロケール依存ハッシュ」です。つまり、H(n)がの場合n、 との差は入力との差H(n)にH(n')正比例します。その場合、必要なのは だけであり、追加のハッシュ手順は必要ありません。nn'lower_bound

このメソッドを非常に簡単に拡張して、オブジェクト間の最大距離を指定するなどのことを行うことができます。これは、使用しているロケールに依存するハッシュと、指定された 2 つの入力に対する 2 つのハッシュ間の距離をどのように表すかによって異なりますが、通常は(with being ) を返す前にH(n)と を比較するだけです。H(n')nearest_structnearest_structn'

于 2012-06-01T16:23:09.000 に答える
1

1 つの方法は、マルチマップを使用することです...

T& get(int key)
{
    // use a multimap as storage
    static multimap<int, T> m;

    multimap<int, T>::iterator best;

    // search for key within 200
    for (auto it = m.lower_bound(key-200); it != m.upper_bound(key+200); ++it)
        if (best)
            // if multiple matches use the closest one to the key
            best = (abs(it->first-key) < abs(best->first-key) ? it : best);
        else
            best = it;

    // if none found, insert new entry
    if (!best)
         best = m.insert(key, T());

    return best->second;
}

少し高速ですが、より厄介な別の方法は、unordered_map と 2 レベルのキーを使用することです...

T& get(int key)
{
    struct KeyValue
    {
        int key;
        T value;
    };

    static unordered_map<int, vector<KeyValue>> m;

    vector<KeyValue>::iterator best;

    int b = key/200;
    int a = b - 1;
    int c = b + 1;

    // function to search bucket for a key...
    auto ms = [&](int bucket)
    {
        for (auto it = m[bucket].begin(); it != m[bucket].end(); ++it)
            if (abs(it->key - key) <= 200)
            {
                if (best)
                    best = (abs(it->key - key) < abs(best->key - key));
                else
                    best = it;
            }
    };

    ms(a);
    ms(b);
    ms(c);

    if (!best)
        best = m[key/200].push_back({key, T()});

    return best->value;
}
于 2012-06-01T16:31:34.227 に答える
0

これを解決する 1 つの方法は、おそらく、構成によって拡張される独自のコンテナー クラスを作成することstd::mapです。

a をメンバーとして保持し、std::map必要な関数と typedef をすべて転送します。

少なくとも次の関数を使用して、「試行錯誤」ロジックを実装してください。

  • count
  • find
  • operator[]
  • at
于 2012-06-01T13:49:34.117 に答える