Generierung einer Eindeutigen ID in c++

Eine einfache Lösung ist die Verwendung eines 64-bit-Ganzzahl, wo die unteren 16 bits der ersten vertex-Koordinate, die nächsten 16 bits ist die zweite, und so weiter. Diese werden einmalig für alle Ihre Scheitelpunkte, wenn auch nicht sehr kompakt.

So, hier ist etwas halbherzig-code, dies zu tun. Ich hoffe, ich habe die Modelle rechts.

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;
}

Optional umgesetzt werden könnte dies mit einer union (tolle Idee von Leon Timmermans, siehe Kommentar). Sehr sauber so:

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;
}

verwenden Sie eine lange, lange, so dass Sie können speichern Sie alle 4 Möglichkeiten, dann bitshift jeder kurz:

((long long)shortNumberX) << 0, 4, 8, oder 12

achten Sie darauf werfen bevor Sie sich, oder Ihre Daten könnten in die drop-off am Ende.

Edit: vergaß hinzuzufügen, sollten Sie ODER Sie zusammen.

Die definition von "ID" in der Frage ist nicht wirklich klar: Sie brauchen, um verwenden Sie es als Schlüssel für den schnellen Vertex-lookup? Definieren Sie einen Komparator für die std::map (siehe unten für ein Beispiel)

Müssen Sie in der Lage sein, zu unterscheiden zwischen zwei Vertex-Objekte mit den gleichen Koordinaten (unterscheiden sich aber in einem anderen Bereich)? Definieren Sie hier einige id 'Fabrik' (cfr. das singleton-pattern) erzeugt z.B. eine Sequenz von Ganzzahlen, die sich nicht auf die Werte der Vertex-Objekte. - Viel in der Art Feuer Lancer schlägt (aber Vorsicht, der thread-Sicherheitsprobleme!)

Meiner Meinung nach, zwei Knoten mit identischen Koordinaten identisch sind. Also, warum würde Sie noch brauchen, eine extra ID?

Sobald Sie definieren einen 'strenge schwache bestellen' auf diese Art, Sie können verwenden Sie es als Schlüssel, z.B. eine 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 );

Wenn Sie eine hash-Tabelle zum speichern der vertices, an die ich denken kann ein paar Möglichkeiten, um Kollisionen zu vermeiden:

1. Generieren IDs direkt aus der input-Daten, ohne dass alle bits Weg, und verwenden Sie eine hash-Tabelle, die groß genug ist, um alle möglichen IDs. Mit 64-bit-IDs, die letzteren werden als äußerst problematisch: Sie haben eine Tabelle verwenden, die kleiner ist als Ihre Palette von IDs, deshalb werden Sie haben, um mit Kollisionen. Auch mit 32-bit-IDs, müssen Sie auch über 4GB RAM zu ziehen diese aus, ohne Kollisionen.
2. Generieren-IDs sequenziell Lesen Sie in den Eckpunkten. Leider, das macht es sehr teuer, um die Suche für vorher Lesen, Eckpunkte, um zu aktualisieren Sie Ihre Wahrscheinlichkeiten, da ein sequenzielle ID-generator ist keine hash-Funktion. Wenn die Menge der Daten verwendet, die zur Konstruktion der Markov-Kette ist deutlich kleiner als die Menge der Daten, dass die Markov-Kette generiert wird (oder wenn Sie sind beide klein), kann dies nicht ein Problem sein.

Alternativ könnten Sie verwenden eine hash-Tabelle Implementierung, die Griffe Kollisionen für Sie (wie unordered_map/hash_map), und konzentrieren sich auf den rest der Anwendung.

aus dem Stegreif würde ich sagen, verwendet Primzahlen,

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

Stellen Sie sicher, dass Sie nicht überlaufen Ihre id-Raum (lange? lange, lange?). Da hast du eine Feste Anzahl von Werten nur Mist einige zufällige Primzahlen. Kümmern Sie sich nicht erzeugen, gibt es genug verfügbar in den Listen, um Sie gehen für eine Weile.

Bin ich ein wenig skizzenhaft auf den Beweis, obwohl, vielleicht hat jemand mehr mathematischen kann mir Haken. Hat wahrscheinlich etwas zu tun mit der einmaligen Primzahl-ZERLEGUNG von einer Zahl.