c++ - C++での一意のIDの生成

Question

C ++で2つ（またはそれ以上）の短いintから一意のIDを生成するための最良の方法は何ですか？グラフ内の頂点を一意に識別しようとしています。頂点にはデータとして2〜4個の短い整数が含まれ、理想的にはIDはそれらのハッシュのようなものになります。スピードや使いやすさよりも携帯性と独自性を優先します。

ここにはたくさんの素晴らしい答えがあります。私は今夜、自分の問題に最も適したものを見つけるためにそれらを試してみます。私がしていることについてもう少し。

グラフは、オーディオファイルからのサンプルのコレクションです。グラフをマルコフ連鎖として使用して、古いファイルから新しいオーディオファイルを生成します。各頂点にはいくつかのサンプルが格納され、別のサンプルを指し、サンプルはすべて短いintであるため、データからIDを生成するのは自然なことのように思われました。それらを長く長いものに組み合わせるのは良いことのように聞こえますが、たぶん0 123のような単純なもので十分generateIDです。一意性を保証するために必要なスペースがどれくらいかわからない場合、各頂点に2つの16ビットサンプルが格納されている場合、2 ^ 32の可能な組み合わせが正しいですか？したがって、各頂点に4つのサンプルが格納されている場合、2 ^ 64の可能な組み合わせがありますか？

ライブラリおよびプラットフォーム固有のソリューションは、この質問にはあまり関係ありません。私のプログラムをコンパイルする可能性のある他の人に、追加のライブラリをダウンロードしたり、OSに合わせてコードを変更したりする必要はありません。

score 10 · Accepted Answer

時には、最も単純なものが最も効果的です。

Vertex オブジェクトに id フィールドを追加して、構築順に番号を割り当てることはできますか?

static int sNextId = 0;
int getNextId() { return ++sNextId; }

score 5 · Accepted Answer

簡単な解決策は、下位 16 ビットが最初の頂点座標であり、次の 16 ビットが 2 番目の頂点座標である 64 ビット整数を使用することです。これは、非常にコンパクトではありませんが、すべての頂点で一意になります。

そのため、これを行う中途半端なコードを次に示します。うまくいけば、キャストが正しくなりました。

uint64_t generateId( uint16_t v1, uint16_t v2, uint16_t v3, uint16_t v4)
{ 
   uint64_t id;
   id = v1 | (((uint64_t)v2) << 16) | (((uint64_t)v3) << 32) | (((uint64_t)v4) << 48);
   return id;
}

必要に応じて、ユニオンを使用してこれを行うこともできます (Leon Timmermans の素晴らしいアイデア、コメントを参照)。このように非常にきれいです：

struct vertex
{
    uint16_t v1;
    uint16_t v2;
    uint16_t v3;
    uint16_t v4;
};

union vertexWithId
{
    vertex v;
    uint64_t id;
};

int main()
{
    vertexWithId vWithId;
    // Setup your vertices
    vWithId.v.v1 = 2;
    vWithId.v.v2 = 5;

    // Your id is automatically setup for you!
    std::cout << "Id is " << vWithId.id << std::endl;
    return 0;
}

score 0 · Accepted Answer

IDが一意であることを保証する唯一の方法は、取得したIDよりも多くのIDの組み合わせを作成することです。

たとえば、2つのショート（16ビットを想定）の場合、32ビットのintを使用する必要があります

int ID = ((int)short1 << 16) | short2;

4つのショートパンツの場合、64ビット整数などが必要になります。

基本的に他のすべての衝突（複数のものが同じIDを取得する可能性があります）はほぼ保証されています。

ただし、IDを取得するための別のアプローチ（私はより良いと思います）は、頂点が挿入されたときにIDを配布することです。

unsigned LastId = 0;//global

unsigned GetNewId(){return ++LastId;}

これには、各頂点にさらに多くの/異なるデータを追加できるようにする効果もあります。ただし、リセットせずに2 ^ 32を超える頂点を作成する場合は、これがおそらく最善の方法ではありません。

score 0 · Accepted Answer

long longを使用して、4つの可能性すべてを保存できるようにしてから、それぞれのshortをビットシフトします。

（（long long）shortNumberX）<< 0、4、8、または12

シフトする前にキャストすることを確認してください。そうしないと、データが最後から削除される可能性があります。

編集：追加するのを忘れた、あなたはそれらを一緒にORする必要があります。

score 0 · Accepted Answer

頂点を格納するハッシュテーブルを作成している場合、衝突を回避する方法がいくつか考えられます。

ビットを捨てることなく入力データから ID を直接生成し、考えられるすべての ID を保持するのに十分な大きさのハッシュテーブルを使用します。64 ビット ID では、後者は非常に問題になります。ID の範囲よりも小さいテーブルを使用する必要があるため、衝突に対処する必要があります。32 ビット ID を使用しても、衝突せずにこれを行うには 4GB をはるかに超える RAM が必要です。
頂点を読み込んで、順番に ID を生成します。残念ながら、シーケンシャル ID ジェネレーターはハッシュ関数ではないため、以前に読み取った頂点を検索して確率を更新するのは非常にコストがかかります。マルコフ連鎖を構築するために使用されるデータの量が、マルコフ連鎖が生成するために使用されるデータの量よりも大幅に少ない場合 (または両方とも小さい場合)、これは問題にならない可能性があります。

または、衝突を処理するハッシュテーブルの実装 ( unordered_map / hash_mapなど) を使用して、アプリケーションの残りの部分に集中することもできます。

score 0 · Accepted Answer

質問の「ID」の定義は明確ではありません。高速な頂点検索のキーとして使用する必要がありますか? のコンパレータを定義できますstd::map（例については以下を参照）

同じ座標を持つ (ただし、別のフィールドでは異なる) 2 つの Vertex オブジェクトを区別できるようにする必要がありますか? Vertex オブジェクトの値とは関係のない int のシーケンスなどを生成する「id factory」(singleton パターンを参照) を定義します。- Fire Lancer が提案する方法とほぼ同じです (ただし、スレッドセーフの問題に注意してください!)

私の意見では、同じ座標を持つ 2 つの頂点は同じです。では、なぜ追加の ID が必要なのですか?

この型で「厳密な弱い順序付け」を定義するとすぐに、それをキーとして使用できますstd::map。

struct Vertex {
  typedef short int Value;
  Value v1, v2;

  bool operator<( const Vertex& other ) const {
    return v1 < other.v1 || ( v1 == other.v1 && v2 < other.v2 ) ;
};

Vertex x1 = { 1, 2 };
Vertex x2 = { 1, 3 };
Vertex y1 = { 1, 2 }; // too!

typedef std::set<Vertex> t_vertices;

t_vertices vertices;
vertices.insert( x1 );
vertices.insert( x2 );
vertices.insert( y1 ); // won't do a thing since { 1, 2 } is already in the set.

typedef std::map<Vertex, int> t_vertex_to_counter;
t_vertex_to_counter count;
count[ x1 ]++;
assert( count[x1] == 1 );
assert( count[y1] == 1 );
count[ x2 ]++;
count[ y1 ]++; 
assert( count[x1] == 2 );
assert( count[y1] == 2 );

score 0 · Accepted Answer

移植性を好む場合は、boost::tupleが便利です。

4 つの項目のタプルが必要です。

typedef boost::tuple<uint16,uint16,uint16,uint16> VertexID;

次のように割り当てることができます。

VertexID id = boost::make_tuple(1,2,3,4);

ブーストタプルは既に比較、等値などをサポートしているため、コンテナーやアルゴリズムで簡単に使用できます。

score 0 · Accepted Answer

Windows の場合はCoCreateGUID API を使用できます。Linux の場合は /proc/sys/kernel/random/uuid を使用できます。「libuuid」も確認できます。

score -1 · Accepted Answer

カフオフで、素数を使用すると言いますが、

id = 3 * value1 + 5 * value2 + .... + somePrime * valueN

ID スペースをオーバーフローしないようにしてください (長い?長い長い?)。固定数の値があるので、いくつかのランダムな素数をクラップします。それらを生成する必要はありません。リストには、しばらく使用できる十分なものがあります。

私は証明が少し大ざっぱですが、もっと数学的な人が私をつなぐことができるかもしれません。おそらく、数値の一意の素因数分解と関係があります。

c++ - C++での一意のIDの生成

11 に答える 11

Related

Reference