¿Puedo usar una lista como hash en R? Si es así, ¿por qué es tan lento?

Antes de usar R, utilicé bastante Perl. En Perl, a menudo usaba hashes, y las búsquedas de hashes generalmente se consideran rápidas en Perl.

Por ejemplo, el siguiente código poblará un hash con hasta 10000 pares clave / valor, donde las claves son letras aleatorias y los valores son enteros aleatorios. Luego, hace 10000 búsquedas aleatorias en ese hash.

#!/usr/bin/perl -w use strict; my @letters = ('a'..'z'); print @letters . "\n"; my %testHash; for(my $i = 0; $i < 10000; $i++) { my $r1 = int(rand(26)); my $r2 = int(rand(26)); my $r3 = int(rand(26)); my $key = $letters[$r1] . $letters[$r2] . $letters[$r3]; my $value = int(rand(1000)); $testHash{$key} = $value; } my @keyArray = keys(%testHash); my $keyLen = scalar @keyArray; for(my $j = 0; $j < 10000; $j++) { my $key = $keyArray[int(rand($keyLen))]; my $lookupValue = $testHash{$key}; print "key " . $key . " Lookup $lookupValue \n"; } 

Ahora que cada vez más, me gustaría tener una estructura de datos tipo hash en R. El siguiente es el código R equivalente:

 testHash <- list() for(i in 1:10000) { key.tmp = paste(letters[floor(26*runif(3))], sep="") key <- capture.output(cat(key.tmp, sep="")) value <- floor(1000*runif(1)) testHash[[key]] <- value } keyArray <- attributes(testHash)$names keyLen = length(keyArray); for(j in 1:10000) { key <- keyArray[floor(keyLen*runif(1))] lookupValue = testHash[[key]] print(paste("key", key, "Lookup", lookupValue)) } 

El código parece estar haciendo cosas equivalentes. Sin embargo, el Perl es mucho más rápido:

 >time ./perlHashTest.pl real 0m4.346s user **0m0.110s** sys 0m0.100s 

Comparando a R:

 time R CMD BATCH RHashTest.R real 0m8.210s user **0m7.630s** sys 0m0.200s 

¿Qué explica la discrepancia? ¿Las búsquedas en listas R simplemente no son buenas?

¿Aumentar a 100.000 la longitud de la lista y 100.000 búsquedas solo exagera la discrepancia? ¿Hay una mejor alternativa para la estructura de datos hash en R que la lista nativa ()?

La razón subyacente es que las listas R con elementos nombrados no son hash. Las búsquedas hash son O (1), porque durante la inserción la clave se convierte a un entero utilizando una función hash, y luego el valor se pone en el espacio hash(key) % num_spots de una matriz num_spots long (esto es una gran simplificación y evita la complejidad de lidiar con colisiones). Las búsquedas de la clave solo requieren la clave para hallar la posición del valor (que es O (1), frente a una búsqueda de matriz O (n)). Las listas R usan búsquedas de nombres que son O (n).

Como dice Dirk, usa el paquete hash. Una gran limitación con esto es que utiliza entornos (que son hash) y reemplaza [ métodos para imitar tablas hash. Pero un entorno no puede contener otro entorno, por lo que no puede tener hashes nesteds con la función hash.

Hace un tiempo trabajé en la implementación de una estructura de datos de tabla hash pura en C / R que podría anidarse, pero continuó en mi proyecto mientras trabajaba en otras cosas. Aunque sería bueno tenerlo 🙂

Podrías probar los entornos y / o el paquete hash de Christopher Brown (que usa entornos bajo el capó).

Su código es muy similar a R y es una de las razones por las que es tan lento. No he optimizado el código a continuación para una velocidad máxima, solo R’ness.

 n <- 10000 keys <- matrix( sample(letters, 3*n, replace = TRUE), nrow = 3 ) keys <- apply(keys, 2, paste0, collapse = '') value <- floor(1000*runif(n)) testHash <- as.list(value) names(testHash) <- keys keys <- sample(names(testHash), n, replace = TRUE) lookupValue = testHash[keys] print(data.frame('key', keys, 'lookup', unlist(lookupValue))) 

En mi máquina que se ejecuta casi instantáneamente excluyendo la impresión. Tu código corrió aproximadamente a la misma velocidad que informaste. ¿Está haciendo lo que quieres? Puede establecer n a 10 y solo mirar la salida y testHash y ver si eso es todo.

NOTA sobre la syntax: La apply anterior es simplemente un bucle y los que son lentos en R. El punto de los que aplican comandos de familia es la expresividad. Muchos de los comandos que siguen podrían haberse puesto dentro de un bucle con apply y si era un bucle for sería la tentación. En R saque todo lo posible de su circuito. El uso de aplicar los comandos de familia lo hace más natural porque el comando está diseñado para representar la aplicación de una función a una lista de algún tipo en lugar de un ciclo genérico (sí, sé que apply podría usarse en más de un comando).

Soy un poco loco, pero soy empirista, así que compartiré algunas cosas que he observado y dejaré que aquellos con una mayor comprensión teórica de R arrojen luz sobre los porqués.

  • R parece mucho más lento usando transmisiones estándar que Perl. Dado que stdin y stout son mucho más utilizados en Perl, supongo que tiene optimizaciones sobre cómo se hacen estas cosas. Entonces, en RI encuentro MUCHO más rápido leer / escribir texto usando las funciones integradas (por ejemplo, write.table ).

  • Como han dicho otros, las operaciones vectoriales en R son más rápidas que los bucles … y la velocidad wrt, la mayoría de los apply () la syntax familiar es simplemente una envoltura bonita en un bucle.

  • Los elementos indexados funcionan más rápido que los no indexados. (Obvio, lo sé). El paquete data.table admite la indexación de objetos de tipo de dataframe.

  • Nunca he usado entornos hash como @ Allen ilustrado (y nunca he inhalado hash … por lo que usted sabe)

  • Parte de la syntax que usaste funciona, pero podría ser más estricta. No creo que nada de esto realmente importe por la velocidad, pero el código es un poco más legible. No escribo un código muy ajustado, pero floor(1000*runif(1)) algunas cosas como cambiar el floor(1000*runif(1)) a la sample(1:1000, n, replace=T) . No quiero ser pedante, simplemente lo escribí de la manera en que lo haría desde cero.

Entonces, con eso en mente, decidí probar el enfoque hash que usaba @allen (porque es nuevo para mí) en comparación con el “hash de los pobres” que he creado usando una tabla de datos indexados como una tabla de búsqueda. No estoy 100% seguro de que lo que @allen y yo estamos haciendo es exactamente lo que hiciste en Perl porque mi Perl está bastante oxidado. Pero creo que los dos métodos a continuación hacen lo mismo. Los dos probamos el segundo conjunto de claves de las teclas en el ‘hash’ ya que esto evita errores de hash. Querrás probar cómo estos ejemplos manejan hash engaños ya que no he pensado tanto.

 require(data.table) dtTest <- function(n) { makeDraw <- function(x) paste(sample(letters, 3, replace=T), collapse="") key <- sapply(1:n, makeDraw) value <- sample(1:1000, n, replace=T) myDataTable <- data.table(key, value, key='key') newKeys <- sample(as.character(myDataTable$key), n, replace = TRUE) lookupValues <- myDataTable[newKeys] strings <- paste("key", lookupValues$key, "Lookup", lookupValues$value ) write.table(strings, file="tmpout", quote=F, row.names=F, col.names=F ) } 

#

 hashTest <- function(n) { testHash <- new.env(hash = TRUE, size = n) for(i in 1:n) { key <- paste(sample(letters, 3, replace = TRUE), collapse = "") assign(key, floor(1000*runif(1)), envir = testHash) } keyArray <- ls(envir = testHash) keyLen <- length(keyArray) keys <- sample(ls(envir = testHash), n, replace = TRUE) vals <- mget(keys, envir = testHash) strings <- paste("key", keys, "Lookup", vals ) write.table(strings, file="tmpout", quote=F, row.names=F, col.names=F ) } 

si ejecuto cada método con 100.000 sorteos, obtengo algo como esto:

 > system.time( dtTest(1e5)) user system elapsed 2.750 0.030 2.881 > system.time(hashTest(1e5)) user system elapsed 3.670 0.030 3.861 

Tenga en cuenta que esto es aún considerablemente más lento que el código Perl que, en mi PC, parece ejecutar 100K muestras en menos de un segundo.

Espero que el ejemplo anterior ayude. Y si tiene alguna pregunta sobre por why tal @allen, @vince y @dirk podrán responder;)

Después de tipear lo anterior, me di cuenta de que no había probado lo que hizo @ john. Entonces, qué diablos, hagamos todos 3. Cambié el código de @john para usar write.table () y aquí está su código:

 johnsCode <- function(n){ keys = sapply(character(n), function(x) paste(letters[ceiling(26*runif(3))], collapse='')) value <- floor(1000*runif(n)) testHash <- as.list(value) names(testHash) <- keys keys <- names(testHash)[ceiling(n*runif(n))] lookupValue = testHash[keys] strings <- paste("key", keys, "Lookup", lookupValue ) write.table(strings, file="tmpout", quote=F, row.names=F, col.names=F ) } 

y el tiempo de ejecución:

 > system.time(johnsCode(1e5)) user system elapsed 2.440 0.040 2.544 

Y ahí lo tienes. @john escribe el código R apretado / rápido!

Pero un entorno no puede contener otro entorno (citado de la respuesta de Vince).

Tal vez fue así hace algún tiempo (no sé), pero esta información parece no ser más precisa:

 > d <- new.env() > d$x <- new.env() > d$x$y = 20 > d$x$y [1] 20 

Entonces los entornos hacen un mapa / dict bastante capaz ahora. Tal vez se perderá el operador ‘[‘, use el paquete hash en ese caso.

Esta nota tomada de la documentación del paquete hash también puede ser de su interés:

R se está moviendo lentamente hacia una implementación nativa de hashes usando entornos, (ver Extracto. El acceso a entornos usando $ y [[ha estado disponible desde hace algún tiempo y recientemente los objetos pueden heredar de entornos, etc. Pero muchas características que hacen hashes / diccionarios Todavía faltan grandes, como la operación de corte, [.

En primer lugar, como Vince y Dirk dijeron, no estás usando hash en tu código de ejemplo. Una traducción literal del ejemplo Perl sería

 #!/usr/bin/Rscript testHash <- new.env(hash = TRUE, size = 10000L) for(i in 1:10000) { key <- paste(sample(letters, 3, replace = TRUE), collapse = "") assign(key, floor(1000*runif(1)), envir = testHash) } keyArray <- ls(envir = testHash) keyLen <- length(keyArray) for(j in 1:10000) { key <- keyArray[sample(keyLen, 1)] lookupValue <- get(key, envir = testHash) cat(paste("key", key, "Lookup", lookupValue, "\n")) } 

que funciona bastante rápido en mi máquina, la hora principal es la configuración. (Pruébalo y publica los tiempos).

Pero el problema real, como dijo John, es que hay que pensar vectores en R (como map in perl) y su solución es probablemente la mejor. Si desea usar hash, considere

 keys <- sample(ls(envir = testHash), 10000, replace = TRUE) vals <- mget(keys, envir = testHash) 

después de la misma configuración que la anterior, que es casi instantánea en mi máquina. Para imprimirlos todos intenten

 cat(paste(keys, vals), sep="\n") 

Espero que esto ayude un poco.

Alano