Generar un IDENTIFICADOR Único en c++

Question

¿Cuál es la mejor manera de generar un IDENTIFICADOR Único de dos (o más) de corto enteros en C++?Estoy tratando de identificar los vértices en una gráfica.Los vértices que contienen de dos a cuatro enteros como de datos, y lo ideal es que el ID sería algún tipo de hash de ellos.Prefieren la portabilidad y la singularidad de la velocidad o facilidad.

Hay un montón de grandes respuestas de aquí, voy a estar tratando de todos ellos esta noche para ver lo que se ajusta a mi problema la mejor.Algunas palabras más sobre lo que estoy haciendo.

La gráfica es una colección de muestras de un archivo de audio.Yo uso el gráfico como una Cadena de Markov para generar un nuevo archivo de audio en el archivo antiguo.Desde cada vértice tiendas un par de muestras y puntos a otro de la muestra, y las muestras son todas corto enteros, parecía natural para generar un IDENTIFICADOR de los datos.La combinación de ellos en un largo, largo suena bien, pero tal vez algo tan simple como un 0 1 2 3 generateID es todo lo que necesito.no estoy seguro de cuánto espacio es necesario para garantizar la unicidad, si cada vértice tiendas 2 samples de 16 bits, hay 2^32 posibles combinaciones correctas?y así, si cada vértice tiendas de 4 muestras, hay 2^64 combinaciones posibles?

De la biblioteca y de la plataforma de soluciones específicas en realidad no es relevante para esta pregunta.No quiero a alguien que pueda compilar mi programa a tener que descargar librerías adicionales o cambiar el código para adaptarlo a su sistema operativo.

Answer 1

Una solución simple es usar un entero de 64 bits donde el menor de 16 bits es el primer vértice de coordenadas, el próximo 16 bits es el segundo, y así sucesivamente.Este será único para todos sus vértices, aunque no muy compacta.

Así que aquí hay algunos a medias código para hacer esto.Esperemos que recibí los moldes a la derecha.

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

Opcionalmente esto se podría hacer con un sindicato (gran idea de Leon Timmermans, véase el comentario).Muy limpio de esta manera:

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 veces las cosas más simples que funciona mejor.

Usted puede simplemente añadir un campo de id del Vértice objeto y asignarle un número en el orden de la construcción?

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

Answer 3

el uso de un largo tiempo, así que usted puede almacenar todos los 4 posibilidades, entonces bitshift cada uno corto:

((mucho, mucho)shortNumberX) << 0, 4, 8, o 12

asegúrese de que usted emitidos antes del cambio, o su datos podría dejar fuera de la final.

Editar:se olvidó de agregar, usted debe O juntos.

Answer 4

Si usted prefiere la portabilidad, entonces boost::tupla es bonito:

Usted quiere una tupla de 4 elementos:

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

Puede asignar como este:

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

El impulso de la tupla ya cuenta con el apoyo para la comparación, la igualdad, etc., por lo que es fácil para el uso en contenedores y algoritmos.

Answer 5

La definición de la "IDENTIFICACIÓN" en la pregunta no es muy clara:qué es necesario para utilizar como clave para el rápido Vértice de búsqueda?Se podría definir un comparador para la std::map (consulte a continuación para ver un ejemplo)

Qué se necesita para ser capaz de diferenciar entre dos Vértices de los objetos con el mismo sistema de coordenadas (pero diferente en otro campo)?Definir el id de fábrica' (cfr.el patrón singleton) que genera por ejemplo,una secuencia de enteros, ajenos a los valores de los Vértices de los objetos.- Mucho en el camino de Fuego Lancer sugiere (pero cuidado con el hilo de las cuestiones de seguridad!)

En mi opinión, los dos vértices con idénticas coordenadas son idénticos.Así que, ¿por qué necesitan un extra de IDENTIFICACIÓN?

Tan pronto como definir un 'estricto débil pedido"en este tipo, se puede utilizar como una clave, por ejemplo, deun 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

Si estás en Windows, puede utilizarCoCreateGUID API, en Linux puedes usar /proc/sys/kernel/random/uuid, usted también puede mirar 'libuuid'.

Answer 7

Si usted está construyendo una tabla hash en el que almacenar los vértices, se me ocurren un par de formas para evitar colisiones:

1. Generar Identificadores directamente a partir de los datos de entrada sin tirar ninguna bits de distancia, y el uso de una tabla de hash que es lo suficientemente grande para contener todos los posibles Identificadores.Con 64 bits Identificadores, el último va a ser muy problemático:usted tendrá que usar una tabla que es más pequeño que su rango de IDs, por lo tanto, usted tendrá que lidiar con las colisiones.Incluso con la de 32 bits Identificadores, necesitaría más de 4GB de RAM para tirar esto sin colisiones.
2. Generar Identificadores secuencialmente a medida que se lee en los vértices.Desafortunadamente, esto hace que sea muy caro para buscar los lea previamente los vértices en orden a la actualización de sus posibilidades, desde un ID secuencial generador no es una función de hash.Si la cantidad de datos que se utilizan para la construcción de la cadena de Markov es significativamente menor que la cantidad de datos que la cadena de Markov se utiliza para generar (o si son pequeños), esto puede no ser un problema.

Como alternativa, puede utilizar una tabla de hash de la aplicación que se encarga de colisiones para usted (tales como unordered_map/hash_map), y concentrarse en el resto de su aplicación.

Answer 8

Bueno, la única manera de garantizar que el ID es único, es hacer que tengan más de identificación de combinaciones de lo que las extracciones de los ids

por ejemplo, para los 2 cortos (suponiendo 16bit), se debe usar un int de 32 bits

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

y para las 4 de pantalones cortos de la que tendría una de 64 bits int, etc...

Con básicamente cualquier cosa de colisiones (varias cosas pueden obtener el mismo id) son prácticamente garantizado.

Sin embargo, un enfoque diferente (que creo que sería mejor)para obtener los identificadores sería de la mano de ellos como vértices se insertan:

unsigned LastId = 0;//global

unsigned GetNewId(){return ++LastId;}

Esto también tiene el efecto de permitir que usted agregue más/datos diferentes para cada vértice.Sin embargo, si usted espera crear más de 2^32 vértices sin reiniciarlo, esto probablemente no es el mejor método.

Answer 9

improvisando yo diría que el uso de los números primos,

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

Asegúrese de que no se desborde su id de espacio (largo?largo tiempo?).Ya que usted tiene un número fijo de valores sólo basura aleatoria de los números primos.No te molestes en generación, hay disponible suficiente en las listas para que te vas por un tiempo.

Estoy un poco incompleto en la prueba, aunque, tal vez alguien más mathmatical puede me enganche.Probablemente tiene algo que ver con la única factorización en primos de un número.