2008-09-15 22 views
7

¿Cuál es la mejor manera de generar una identificación única a partir de dos (o más) entradas cortas en C++? Intento identificar vértices de forma única en un gráfico. Los vértices contienen de dos a cuatro entradas cortas como datos, e idealmente la ID sería una especie de hash de ellos. Prefiere la portabilidad y la exclusividad sobre la velocidad o la facilidad.Generando una identificación única en C++

Aquí hay muchas respuestas excelentes, esta noche las probaré todas para ver cuál es la mejor para mi problema. Algunas palabras más sobre lo que estoy haciendo.

El gráfico es una colección de muestras de un archivo de audio. Uso el gráfico como una Cadena de Markov para generar un nuevo archivo de audio del archivo anterior. Como cada vértice almacena algunas muestras y puntos a otra muestra, y las muestras son todas cortas, parecía natural generar una ID a partir de los datos. Combinarlos en una larga duración suena bien, pero tal vez algo tan simple como solo es todo lo que necesito. no estoy seguro de cuánto espacio es necesario para garantizar la singularidad; si cada vértice almacena 2 muestras de 16 bits, ¿hay 2^32 combinaciones posibles correctas? y entonces si cada vértice almacena 4 muestras, ¿hay 2^64 combinaciones posibles?

Las soluciones específicas de biblioteca y plataforma no son realmente relevantes para esta pregunta. No quiero que nadie más que pueda compilar mi programa tenga que descargar bibliotecas adicionales o cambiar el código para adaptarse a su sistema operativo.

Respuesta

4

Una solución simple es usar un entero de 64 bits donde los 16 bits inferiores son la primera coordenada del vértice, los siguientes 16 bits es el segundo, y así sucesivamente. Esto será único para todos tus vértices, aunque no muy compacto.

Así que aquí hay un poco de código medio para hacer esto. Espero tener los moldes bien.

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 podría hacerse con una unión (gran idea de Leon Timmermans, ver 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; 
} 
+2

Realmente creo que una unión proporcionaría una manera más limpia de hacer justamente eso, pero eso es una cuestión de gusto. –

+3

fyi, tipo-juego de palabras como este con un sindicato es un comportamiento indefinido. – scpayson

0

Bueno, la única manera de garantizar el ID es único, es hacer que tenga más combinaciones de identificación de cuáles son sus gettings los identificadores de

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

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

y durante 4 cortos que se necesita un int de 64 bits, etc ...

con básicamente las colisiones cualquier otra cosa (varias cosas pueden obtener el mismo id) están prácticamente garantizados.

Sin embargo, un enfoque diferente (que creo que sería mejor) para obtener las identificaciones serían a darlos hacia fuera a medida que se inserta vértices:

unsigned LastId = 0;//global 

unsigned GetNewId(){return ++LastId;} 

Esto también tiene el efecto de que le permite añadir más/diferente datos a cada vértice. Sin embargo, si espera crear más de 2^32 vértices sin restablecerlo, probablemente este no sea el mejor método.

+0

Usar y siempre resultará que los 8 bits más bajos son todos 0. En su lugar, se debe cambiar 16 y orar. – Patrick

0

usar un largo tiempo para que pueda almacenar los 4 posibilidades, entonces BitShift cada corta:

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

asegurarse de que lances antes de cambiar, o sus datos podrían caerse del final.

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

8

A veces las cosas más simples funcionan mejor.

¿Puede simplemente agregar un campo de identificación al objeto Vertex y asignarle un número en orden de construcción?

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

fruto de la casualidad yo diría que el uso de los números primos,

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

Asegúrese de que no desborde su espacio de Identificación (tiempo? Mucho tiempo?). Ya que tienes un número fijo de valores, simplemente machaca algunos primos aleatorios. No se moleste en generarlos, hay suficientes listas disponibles para que pueda continuar por un tiempo.

Aunque soy un poco superficial en cuanto a la prueba, tal vez alguien más matemático pueda conectarme. Probablemente tiene algo que ver con la factorización prima única de un número.

0

Si prefiere la portabilidad, entonces boost::tuple es agradable:

le gustaría que una tupla de 4 artículos:

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

Puede asignar la siguiente manera:

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

El impulso tuple ya tiene soporte para comparación, igualdad, etc., por lo que es fácil de usar en contenedores y algoritmos.

0

La definición de "ID" en la pregunta no es muy clara: ¿necesita usarla como clave para la búsqueda rápida de vértices? Podría definir un comparador para el std::map (vea abajo un ejemplo)

¿Necesita poder diferenciar entre dos objetos Vértice con las mismas coordenadas (pero diferentes en otro campo)? Defina alguna 'fábrica de identificación' (cfr. El patrón singleton) que genera, p. una secuencia de entradas, sin relación con los valores de los objetos Vertex. - Mucho en la forma en que sugiere Fire Lancer (¡pero cuidado con los problemas de seguridad de los hilos!)

En mi opinión, dos vértices con coordenadas idénticas son idénticos. Entonces, ¿por qué necesitarías una identificación adicional?

Tan pronto como defina un 'strict weak ordering' en este tipo, puede usarlo como clave, p. 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); 
0

Si está en Windows, puede utilizar la API CoCreateGUID, en Linux se puede utilizar/proc/sys/kernel/random/UUID, también puede mirar a 'libuuid'.

0

Si usted está construyendo una tabla hash en el que almacenar sus vértices, puedo pensar en un par de maneras de evitar colisiones:

  1. Generar identificadores directamente de los datos de entrada sin lanzar ningún bit de distancia, y use una tabla hash que sea lo suficientemente grande como para contener todas las identificaciones posibles. Con los ID de 64 bits, este último será extremadamente problemático: tendrá que usar una tabla que sea más pequeña que su rango de ID, por lo tanto, deberá lidiar con las colisiones. Incluso con identificaciones de 32 bits, necesitaría más de 4 GB de RAM para llevarlo a cabo sin colisiones.
  2. Genera identificadores secuencialmente mientras lee en los vértices. Desafortunadamente, esto hace que sea muy costoso buscar vértices previamente leídos para actualizar sus probabilidades, ya que un generador de ID secuencial no es una función de hash. Si la cantidad de datos utilizados para construir la cadena de Markov es significativamente menor que la cantidad de datos que la cadena de Markov se utiliza para generar (o si ambos son pequeños), esto puede no ser un problema.

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

Cuestiones relacionadas