1

長さ 30 の整数ベクトルを 100 万個返す関数があり、それぞれ小さいエントリ (-100 から 100 の間など) があるとします。さらに、出力には約 30000 の一意のベクトルしかなく、残りは重複していると仮定します。一意の出力ベクトルのリストを取得するための適切なデータ構造とアルゴリズムは何ですか? 好ましくは、3% の一意のベクトルの割合がほぼ一定である場合、ソリューションは適切にスケーリングする必要があります。

この質問は主にデータ構造に関するものですが、STL を使用して C++ でこれを実装する予定なので、実装に関するヒントも歓迎します。

  • 単純なアルゴリズムは、既知のベクトルのリストを格納することです (潜在的に辞書順にソートされます)。新しいベクターが到着すると、ループを使用してリストに既に存在するかどうかを確認できます (またはソートされたリストを検索します)。
  • ハッシュ: ベクトルが C 配列に格納されていると仮定しましょう。整数ベクトルに適したハッシュ関数は何ですか? 私が見る欠点は、すべてのベクトルのすべてのコンポーネントが少なくとも一度は触れられることです。これはもう多すぎるようです。
  • どのツリー データ構造でもよいでしょうか。たとえば、表示されているすべてのベクトルの最初のコンポーネントの値をルートとして格納し、次に 2 番目のコンポーネントの値を子として格納できます...

私はコンピューター サイエンスのバックグラウンドを持っていません。また、このような問題に一般的にアプローチする方法を学べる文献へのポインタも非常に役立ちます。

4

5 に答える 5

3

あなたが提案しているものは、ルックアサイド テーブルと呼ばれることもあります。さまざまな検索目的で使用されるセカンダリ テーブル。あなたの場合、このテーブルを整理するさまざまな方法が考えられます。最も明白なのは、それを整理せず、線形検索を使用して、次の要素が既に知られているかどうかを確認することです。テーブルには約 30000 の要素が含まれることになるため、これはおそらく良い考えではありません。標準ライブラリ (少なくとも C++11) から、2 つの可能性があります:std::setと std::unordered_set. 何らかの形式のバランスのとれたツリーを使用するため、検索ごとstd::setに最大で lg  nの比較を行います (30000 要素に対して約 15)。std::unordered_setはハッシュ テーブルであり、適切なハッシュ関数を使用すると、一定数の比較が必要になります。平均で 2 未満に抑えることができます (ただし、負荷係数が低くなるほど、メモリが増える可能性があります)。 、衝突の可能性が低くなります)。あなたが言及したように、あなたはそうしますハッシュ関数を計算する余分なコストがかかります。ご指摘のとおり、これにはベクトル内の各要素にアクセスする必要があります。二分木では、各比較で必要なのは、順序を決定するのに十分な要素を比較することだけです。多くの場合、それは 1 つまたは 2 つだけです。(しかし、多くの重複があると言う場合... 30 エントリすべてにアクセスするまで、重複を検出することはできません。いずれかが異なる可能性があるためです。) どのソリューションが実際により高速になるかを知る唯一の方法は、測定することです。両方、典型的なデータを使用。あなたが説明したようなデータセット（多くの重複）の場合、ハッシュテーブルが勝つと思いますが、確実ではありません。

最後に、ある種の非バイナリ ツリーを使用できます。値を特定の範囲 (例: -100..100) に本当に制限できる場合は、通常のベクトルまたは配列をサブノードへのポインターと共に使用し、必要に応じて転置された要素値で直接インデックスを付けることができます。次に、null ポインターが見つかるか、最後に到達するまで、ツリーをたどります。ツリーの最大の深さは 30 で、実際にはすべての要素が 30 の深さになりますが、通常、そこまで深くなる前に要素が一意であることがわかります。あなたの場合、多くの重複があると、これは実際には前の2つの提案よりも大幅に遅くなると思います（ただし、測定する必要があります）。（そして、私は既存の実装を認識していないため、あなたの側ではもっと多くの作業が必要になります。）

ハッシュに関しては、ほぼすべての形式の線形合同ハッシュで十分です。たとえば、FNV です。このようなハッシュのドキュメントのほとんどは文字列 (の配列 char) に関するものですが、整数型と同様に機能する傾向があります。私は一般的に次のようなものを使用しました：

template <typename ForwardIterator>
size_t
hash( ForwardIterator begin, ForwardIterator end )
{
    size_t results = 2166136261U 
    for ( ForwardIterator current = begin; current != end; ++ current ) {
        results = 127 * results + static_cast<size_t>( *current );
    }
    return results;
}

127乗数として を選択したのは、古いシステムの速度に大きく依存しています。(これがまだ正しいかどうかはわかりません。しかし、乗算は多くのマシンで依然として比較的遅い操作であり、コンパイラはそれがより高速である場合に127 * x似たようなものに変換しx << 7 - xます。) 上記のアルゴリズムを使用した分布は、 FNV、少なくとも私がテストしたデータセットでは.

于 2013-03-31T11:03:23.107 に答える
1

最初のベクトルの値の CRC 表現を計算します。これで、30 個の値を表す 1 つの数字ができました。その数は、残りのベクトルに関して一意である可能性がありますが、保証されていません。

CRC 値をキーとして取得し、実際のベクトルへのポインターをマルチマップ {CRC, VectorPointer} に挿入します。

次に、残りのベクトルごとに CRC を計算し、マルチマップで調べます。

見つからない場合は、{CRC, VectorPointer} を挿入します。見つかった場合は、一致を反復し、データ要素を比較して同一かどうかを判断します。ある場合は、新しいベクターを破棄します。そうでない場合は、{CRC, VectorPointer} を挿入します。

30,000 個のベクターすべてが処理されるまで、すすいで繰り返します。

マルチマップで反復可能な独自のセットがあります。

于 2013-03-31T11:37:16.763 に答える
1

長さ K の N 個のベクトルがあり、M 個しか一意に存在しないとします。

  • ハッシュ + ハッシュマップ

O(K) 時間ですべてのベクトルのハッシュを計算し、ハッシュマップにそのようなベクトルが既にあるかどうかを確認し、O(1) 時間で新しいベクトルを挿入することができます。ハッシュ関数の場合、ハッシュを64ビット型で保存し、オーバーフローを無視するだけで、モジュラスなしで単純に多項式ハッシュを使用できます。実装は非常に簡単で、O(M*K) メモリを必要とする O(N*K) 時間で動作します。最初に要素をソートする必要がある場合、時間は O(N*K*log(K)) になります

  • 基数ツリー

各ベクトルの各要素を調べる必要があるため、ここでは基数ツリーを使用しないでください。これは、ツリーにそのようなベクトルがない場合は、その要素をすべて挿入する必要があり、そのようなベクトルがある場合は、ツリーの葉に降りて確認する必要があるためです。あなたは実際にそのようなベクトルを以前に挿入しました。したがって、漸近線は同じままですが、ツリーを自分で実装する必要があり、あまり良い考えではありません:)

少なくともベクトルのすべての要素を読み取る必要があることを示すのは簡単なようです。これは、常に 2 つの可能性があるためです。以前に現在のベクトルを見つけて、それを特定するためにそのすべての要素を最後まで読み取る必要があるか、または現在のベクトルを以前に見つけておらず、そのすべての要素を読み取る必要があります。それらを並べ替えて保存します。ただし、ベクトルが既にソートされている場合は、要素を最初の不一致まで読み取る必要があります。しかし、最初の 30000 個のベクトルが一意であると想像してみましょう。使用するアルゴリズムやデータ構造に関係なく、他のすべてのベクトルを最後まで読み取って、それらが一意ではないことを判断する必要があります。そして最後に、ほぼすべてのベクトルを最後まで読み取る必要があることがわかりました:)

値が実際に範囲 (-100, 100) 内にあり、ベクトルに 30 個の値しかない8*30 = 240場合、データのビットしかないため、そのようなベクトルは 4 つの 64 ビット整数で保存できることがわかります。しかし、それは遊ぶための別のアイデアにすぎず、それを使用する実装がハッシュ + ハッシュマップよりも高速に機能するとは思いません。

于 2013-03-31T11:39:43.710 に答える
1

基数マップが理想的ですが、std ライブラリには実装がないため、実装する必要があります。

于 2013-03-31T10:00:27.337 に答える
0

ハッシュ: ... 私が見る欠点は、すべてのベクトルのすべてのコンポーネントが少なくとも 1 回は触れられることです。これはもう多すぎるようです。

最悪の場合、2 つのベクトルを一度も見ずに比較するにはどうすればよいでしょうか? いいえ、実際には、1,1,1 と 2,2,2 がある場合、比較/照合はすぐに終了します。しかし、1,2,3 と 1,2,3 があるとしたら?

とにかく、ここにあなたの問題を解決できる1つの方法があります。実装は間違いなく改善できます。

#include <iostream>
#include <map>
#include <vector>
#include <list>
#include <cstdint>
#include <cstdlib>
#include <ctime>

using namespace std;

const int TotalVectorCount = 1000000;
const int UniqueVectorCount = 30000;
const int VectorLength = 30;

typedef vector<int> Vector;

typedef unsigned long long uint64;

void GenerateRandomVector(Vector& v)
{
  v.reserve(VectorLength);
  // generate 30 values from -100 to +100
  for (int i = 0; i < VectorLength; i++)
    v.push_back(rand() % 201 - 100);
}

bool IdenticalVectors(const Vector& v1, const Vector& v2)
{
  for (int i = 0; i < VectorLength; i++)
    if (v1[i] != v2[i])
      return false;

  return true;
}

// this lets us do "cout << Vector"
ostream& operator<<(ostream& os, const Vector& v)
{
  for (int i = 0; i < VectorLength; i++)
    os << v[i] << ' ';

  return os;
}

uint64 HashVector(const Vector& v)
{
  // this is probably a bad hash function,
  // but it seems to work nonetheless
  uint64 h = 0x7FFFFFFFFFFFFFE7;
  for (int i = 0; i < VectorLength; i++)
    h = h * 0xFFFFFFFFFFFFFFC5 + v[i];
  return h & 0xFFFFFFFFFFFFFFFF;
}

Vector UniqueTestVectors[UniqueVectorCount];

void GenerateUniqueTestVectors()
{
  map<uint64,char> m;
  for (int i = 0; i < UniqueVectorCount; i++)
  {
    for (;;)
    {
      GenerateRandomVector(UniqueTestVectors[i]);
      uint64 h = HashVector(UniqueTestVectors[i]);

      map<uint64,char>::iterator it = m.find(h);

      if (it == m.end())
      {
        m[h] = 0;
        break;
      }
    }
  }
}

bool GetNextVector(Vector& v)
{
  static int count = 0;
  v = UniqueTestVectors[count % UniqueVectorCount];
  return ++count <= TotalVectorCount;
}

int main()
{
  srand(time(0));

  cout << "Generating " << UniqueVectorCount << " unique random vectors..."
       << endl;
  GenerateUniqueTestVectors();

#if 0
  for (int i = 0; i < UniqueVectorCount; i++)
    cout << UniqueTestVectors[i] << endl;
#endif

  cout << "Generating " << TotalVectorCount << " random vectors with only "
       << UniqueVectorCount << " unique..." << endl;

  map<uint64,list<Vector>> TheBigHashTable;

  int uniqCnt = 0;
  int totCnt = 0;

  Vector v;
  while (GetNextVector(v))
  {
    totCnt++;

    uint64 h = HashVector(v);

    map<uint64,list<Vector>>::iterator it = TheBigHashTable.find(h);

    if (it == TheBigHashTable.end())
    {
      // seeing vector with this hash (h) for the first time,
      // insert it into the hash table
      list<Vector> l;
      l.push_back(v);

      TheBigHashTable[h] = l;
      uniqCnt++;
    }
    else
    {
      // we've seen vectors with this hash (h) before,
      // let's see if we've already hashed this vector
      list<Vector>::iterator it;
      bool exists = false;

      for (it = TheBigHashTable[h].begin();
           it != TheBigHashTable[h].end();
           it++)
      {
        if (IdenticalVectors(*it, v))
        {
          // we've hashed this vector before
          exists = true;
          break;
        }
      }

      if (!exists)
      {
        // we haven't hashed this vector before,
        // let's do it now
        TheBigHashTable[h].push_back(v);
        uniqCnt++;
      }
    }
  }

#if 0
  cout << "Unique vectors found:" << endl;
  map<uint64,list<Vector>>::iterator it;
  for (it = TheBigHashTable.begin();
       it != TheBigHashTable.end();
       it++)
  {
    list<Vector>::iterator it2;
    for (it2 = it->second.begin();
         it2 != it->second.end();
         it2++)
      cout << *it2 << endl;
  }
#endif

  cout << "Hashed " << uniqCnt << " unique vectors out of " << totCnt << " total" << endl;

  return 0;
}

12848 kB の RAM を使用して 1.12 秒で出力 ( ideone ):

Generating 30000 unique random vectors...
Generating 1000000 random vectors with only 30000 unique...
Hashed 30000 unique vectors out of 1000000 total

これで、一意のベクトルが少なくなり、短くなったため、コンソールに出力できます。

3040 kB の RAM を使用して 0.14 秒で出力 ( ideone ):

Generating 10 unique random vectors...
-45 75 1 -71 -83 97 10 -18 89 -10 
-11 60 18 -54 -90 77 19 -90 -7 -31 
-15 -65 -47 88 25 -56 4 39 -20 39 
-64 -14 -37 -13 15 -70 -66 -75 12 73 
-35 -99 32 83 98 -8 59 16 2 -98 
86 37 -63 -62 24 62 -68 78 -50 -38 
17 -64 48 80 -26 -87 61 8 -62 -28 
-70 -47 -27 62 86 -29 -97 44 37 -45 
-4 -28 92 -17 -40 -35 -56 -58 -57 -55 
5 10 -19 -48 -61 5 -35 100 -88 -47 
Generating 1000000 random vectors with only 10 unique...
Unique vectors found:
86 37 -63 -62 24 62 -68 78 -50 -38 
17 -64 48 80 -26 -87 61 8 -62 -28 
5 10 -19 -48 -61 5 -35 100 -88 -47 
-4 -28 92 -17 -40 -35 -56 -58 -57 -55 
-11 60 18 -54 -90 77 19 -90 -7 -31 
-15 -65 -47 88 25 -56 4 39 -20 39 
-35 -99 32 83 98 -8 59 16 2 -98 
-45 75 1 -71 -83 97 10 -18 89 -10 
-64 -14 -37 -13 15 -70 -66 -75 12 73 
-70 -47 -27 62 86 -29 -97 44 37 -45 
Hashed 10 unique vectors out of 1000000 total
于 2013-03-31T12:53:02.790 に答える