Generazione di un ID univoco in C++

Question

Qual è il modo migliore per generare un ID univoco da due (o più) brevi int in C++?Sto cercando di identificare in modo univoco i vertici in un grafico.I vertici contengono da due a quattro int brevi come dati e idealmente l'ID dovrebbe essere una sorta di hash di essi.Preferisci la portabilità e l'unicità alla velocità o alla facilità.

Ci sono molte ottime risposte qui, le proverò tutte stasera per vedere cosa si adatta meglio al mio problema.Ancora qualche parola su quello che sto facendo.

Il grafico è una raccolta di campioni da un file audio.Utilizzo il grafico come catena di Markov per generare un nuovo file audio dal vecchio file.Poiché ogni vertice memorizza alcuni campioni e punta a un altro campione e i campioni sono tutti brevi, è sembrato naturale generare un ID dai dati.Combinarli in un lungo lungo suona bene, ma forse qualcosa di semplice come semplicemente 0 1 2 3 generateID è tutto ciò che mi serve.non sei sicuro di quanto spazio sia necessario per garantire l'unicità, se ogni vertice memorizza 2 campioni a 16 bit, ci sono 2 ^ 32 possibili combinazioni corrette?e quindi se ogni vertice memorizza 4 campioni, ci sono 2^64 combinazioni possibili?

Soluzioni specifiche per libreria e piattaforma non realmente rilevanti per questa domanda.Non voglio che nessun altro che potrebbe compilare il mio programma debba scaricare librerie aggiuntive o modificare il codice per adattarlo al proprio sistema operativo.

Answer 1

Una soluzione semplice consiste nell'utilizzare un numero intero a 64 bit in cui i 16 bit inferiori rappresentano la prima coordinata del vertice, i successivi 16 bit sono la seconda e così via.Questo sarà unico per tutti i tuoi vertici, anche se non molto compatto.

Quindi ecco un codice insensato per farlo.Spero di aver azzeccato i calchi.

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

Facoltativamente questo potrebbe essere fatto con un sindacato (ottima idea di Leon Timmermans, vedi commento).Molto pulito in questo modo:

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

Answer 2

A volte le cose più semplici funzionano meglio.

Puoi semplicemente aggiungere un campo ID all'oggetto Vertex e assegnargli un numero in ordine di costruzione?

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

Answer 3

usa un long long in modo da poter memorizzare tutte e 4 le possibilità, quindi bitshift ciascuna short:

((lungo lungo)cortoNumeroX) << 0, 4, 8 o 12

assicurati di trasmettere prima dello spostamento, altrimenti i tuoi dati potrebbero cadere alla fine.

Modificare:ho dimenticato di aggiungere, dovresti OR insieme.

Answer 4

Se preferisci la portabilità, allora potenziamento::tupla è bella:

Vorresti una tupla di 4 elementi:

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

Puoi assegnare in questo modo:

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

La tupla boost ha già il supporto per il confronto, l'uguaglianza, ecc., quindi è facile da usare in contenitori e algoritmi.

Answer 5

La definizione di "ID" nella domanda non è molto chiara:è necessario utilizzarlo come chiave per la ricerca rapida di Vertex?Potresti definire un comparatore per il std::map (vedi sotto per un esempio)

Hai bisogno di essere in grado di distinguere tra due oggetti Vertex con le stesse coordinate (ma diverse in un altro campo)?Definire una sorta di 'fabbrica degli id' (cfr.il pattern singleton) che genera ad es.una sequenza di int, non correlata ai valori degli oggetti Vertex.- Più o meno come suggerisce Fire Lancer (ma attenzione ai problemi di sicurezza dei thread!)

Secondo me due vertici con coordinate identiche sono identici.Allora perché avresti bisogno di un documento d'identità extra?

Non appena definisci un 'ordinamento debole e rigoroso' su questo tipo, puoi usarlo come chiave ad es.UN 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 );

Answer 6

Se utilizzi Windows, potresti utilizzareCoCreateGUID API, su Linux puoi usare /proc/sys/kernel/random/uuid, puoi anche guardare 'libuuid'.

Answer 7

Se stai costruendo una tabella hash in cui memorizzare i tuoi vertici, posso pensare a un paio di modi per evitare collisioni:

1. Genera ID direttamente dai dati di input senza buttare via alcun bit e utilizza una tabella hash sufficientemente grande da contenere tutti gli ID possibili.Con gli ID a 64 bit, quest'ultimo sarà estremamente problematico:dovrai utilizzare una tabella più piccola del tuo range di ID, quindi dovrai fare i conti con le collisioni.Anche con ID a 32 bit, avresti bisogno di ben più di 4 GB di RAM per farcela senza collisioni.
2. Genera gli ID in sequenza mentre leggi i vertici.Sfortunatamente, questo rende molto costoso cercare i vertici letti in precedenza per aggiornare le loro probabilità, poiché un generatore di ID sequenziale non è una funzione hash.Se la quantità di dati utilizzati per costruire la catena di Markov è significativamente inferiore alla quantità di dati che la catena di Markov viene utilizzata per generare (o se sono entrambi piccoli), questo potrebbe non costituire un problema.

In alternativa, puoi utilizzare un'implementazione della tabella hash che gestisce le collisioni per te (come mappa_non ordinata/hash_map) e concentrati sul resto della domanda.

Answer 8

Bene, l'unico modo per garantire che l'ID sia univoco è creare più combinazioni di ID rispetto a quelle da cui ottieni gli ID

ad esempio per 2 cortometraggi (assumendo 16 bit), dovresti usare un int a 32 bit

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

e per 4 cortometraggi avresti bisogno di un int a 64 bit, ecc...

Praticamente con qualsiasi altra cosa le collisioni (più cose possono avere lo stesso ID) sono praticamente garantite.

Tuttavia un approccio diverso (che penso sarebbe migliore) per ottenere gli ID sarebbe distribuirli man mano che vengono inseriti i vertici:

unsigned LastId = 0;//global

unsigned GetNewId(){return ++LastId;}

Ciò ha anche l'effetto di consentire di aggiungere più/diversi dati a ciascun vertice.Tuttavia, se prevedi di creare più di 2^32 vertici senza reimpostarli, probabilmente questo non è il metodo migliore.

Answer 9

a braccio direi di usare numeri primi,

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

Assicurati di non traboccare il tuo spazio ID (lungo?lungo lungo?).Dato che hai un numero fisso di valori, basta fare schifo ad alcuni numeri primi casuali.Non preoccuparti di generarli, ce ne sono abbastanza disponibili negli elenchi per farti andare avanti per un po'.

Però sono un po' lacunoso con la dimostrazione, forse qualcuno più esperto di matematica può darmi una mano.Probabilmente ha qualcosa a che fare con la scomposizione in fattori primi univoci di un numero.