Estructura de datos adecuada para una clave bidireccional <-> val tabla de búsqueda

Question

Tengo un conjunto de claves (carácter) < -> hash (entero) asociaciones en R. Me gustaría almacenar estas asociaciones en una única estructura que permite me para hacer referencia a un par clave/hash por clave, y también por hash.

así que algo como

"hello" <-> 1234 

en la variable db.

y acceder a ella con (más o menos, no tiene por qué ser exacta sintaxis de acceso):

db["hello"] -> 1234 
db[1234] -> "hello" 

He intentado utilizar una trama de datos, y el nombramiento de los rownames las llaves. Pero luego no puedo hacer referencia a una fila por un número entero hash. Si uso enteros hash como nombres de filas, entonces no puedo hacer referencia por nombre clave, etc.

Mi solución actual es mantener dos dbs como dos marcos de datos. Uno tiene los hash como rowname, el otro tiene las teclas como rownames. Esto funciona, pero parece un poco incómodo y repetitivo mantener alrededor de dos marcos de datos idénticos (que no sean sus nombres de fila).

Me gustaría que fuera súper rápido en ambas direcciones :). Creo que esto significa O (log (n)) para la dirección del personaje, y O (1) para la dirección del entero, pero yo no soy un experto en la estructura de datos/algoritmo. O (log (n)) en la dirección entera probablemente sea correcto, pero creo que O (n) (necesita recorrer toda la solución db) en cualquier dirección reducirá demasiado las cosas.

El db es también bijective. Es decir, cada tecla asigna exactamente un valor, y cada valor se asigna exactamente a una clave.

EDIT: Gracias por los mensajes hasta el momento:

Ejecución de algunas pruebas, la técnica de coincidencia es definitivamente más lento que un data.table con llave. Como señaló Martin, esto se debe únicamente al tiempo requerido para que el partido cree la tabla con clave. Es decir, ambos coinciden y una tabla de datos con clave realiza una búsqueda binaria para encontrar el valor. Pero independientemente, la coincidencia es demasiado lenta para mis necesidades al devolver un valor único. Así que codificaré una solución y publicación de data.table.

> system.time(match(1,x)) 
    user system elapsed 
    0.742 0.054 0.792 
> system.time(match(1,x)) 
    user system elapsed 
    0.748 0.064 0.806 
> system.time(match(1e7,x)) 
    user system elapsed 
    0.747 0.067 0.808 
> system.time(x.table[1]) 
    user system elapsed 
     0  0  0 
> system.time(x.table[1e7]) 
    user system elapsed 
    0.001 0.001 0.000 
> system.time(x.table[1e7]) 
    user system elapsed 
    0.005 0.000 0.005 
> system.time(x.table[1]) 
    user system elapsed 
    0.001 0.000 0.000 
> system.time(x.table[1]) 
    user system elapsed 
    0.020 0.001 0.038 

Edit2:

Fui con la solución fmatch y un vector llamado. Me gustó la simplicidad del enfoque de coincidencia, pero estoy haciendo búsquedas repetidas en el DB, por lo que el rendimiento de recrear la tabla hash en cada llamada para que coincida fue demasiado grande.

fmatch tiene la misma interfaz que coincide, funciona con el mismo tipo de datos vectoriales, etc. Simplemente almacena/memoriza la tabla hash creada, de modo que las llamadas posteriores en el vector nombrado solo tienen que realizar la búsqueda hash. Todo esto se abstrae de la persona que llama, por lo que fmatch es simplemente un dropin para el partido.

código de contenedor simple para las operaciones de búsqueda bidireccional:

enfoque

getChunkHashes = function(chunks, db) { 
     return(db[fmatch(chunks, names(db))]) 
} 

getChunks = function(chunkHashes, db) { 
     return(names(db[fmatch(chunkHashes, db)])) 
} 

Answer 1

dado:

El db también es biyectiva. Es decir, cada tecla asigna exactamente un valor, y cada valor se asigna exactamente a una clave.

Entonces me gustaría sugerir soluciones de hash (por ejemplo la hash package), el fastmatch package, o data.table::chmatch. Una combinación con clave en data.table es más para ordenado teclas de varias columnas y/o datos agrupados, que no es realmente el problema que tiene.

Answer 2

Una base es el uso de un vector llamado:

db <- c(hello = 1234, hi = 123, hey = 321) 

para ir de clave (s) valor (s), el uso [:

db[c("hello", "hey")] 
# hello hey 
# 1234 321 

para ir de valor (s) a la clave (s) es un poco más complicado:

names(db)[match(c(321, 123), db)] 
# [1] "hey" "hi" 

(Tenga en cuenta que match(x, y) devuelve el índice del partido primera de x en y, por lo que este método sólo funciona bien si su mapa es inyectiva, algo que no dejó claro en su pregunta.)

Si considera que el último uso es un poco "pesado", definitivamente puede escribir su propia función.

Nota: como se señala, este enfoque es potencialmente lento en la dirección del valor de la clave, por lo que puede no ser ideal para el acceso bidireccional repetitivo de un mapa grande. Para su defensa, es fácil de implementar, no requiere ningún paquete que no sea base, y hará un trabajo muy decente para el 99% de las necesidades de las personas. Si nada, puede usarse aquí como un punto de referencia contra alternativas más rápidas.

Answer 3

Más una explicación sobre la preocupación de @claytonstanley por la respuesta de @flodel. match hace un hash de uno de sus argumentos y luego busca el otro. El costo es en la creación del hash en lugar de las operaciones de búsqueda

> n = 1e7; x = seq_len(n) 
> system.time(match(1, x)) 
    user system elapsed 
    1.156 0.064 1.222 
> system.time(match(n, x)) 
    user system elapsed 
    1.152 0.068 1.221 

y se amortiza en el número de look-ups realiza

> y = sample(x) 
> system.time(match(y, x)) 
    user system elapsed 
    2.112 0.052 2.167 

por lo que definitivamente quieren que la búsqueda sea 'vectorizada '.