R Language
Hashmaps

Entornos como mapas hash

Nota: en los pasajes subsiguientes, los términos hash map y hash table se usan indistintamente y se refieren al mismo concepto , es decir, una estructura de datos que proporciona una búsqueda de claves eficiente mediante el uso de una función hash interna.

Introducción

Aunque R no proporciona una estructura de tabla hash nativa, se puede lograr una funcionalidad similar aprovechando el hecho de que el objeto de environment devuelto por new.env (de forma predeterminada) proporciona búsquedas de clave hash. Las siguientes dos declaraciones son equivalentes, ya que el parámetro hash defecto es TRUE :

H <- new.env(hash = TRUE)
H <- new.env() 

Además, se puede especificar que la tabla hash interna se asigne previamente con un tamaño particular a través del parámetro size , que tiene un valor predeterminado de 29. Como todos los demás objetos R, los environment administran su propia memoria y aumentarán su capacidad según sea necesario Entonces, si bien no es necesario solicitar un valor de size no predeterminado, puede haber una ligera ventaja de rendimiento al hacerlo si el objeto (eventualmente) contendrá una gran cantidad de elementos. Vale la pena señalar que la asignación de espacio adicional a través del size no resulta, en sí mismo, en un objeto con una huella de memoria más grande:

object.size(new.env())
# 56 bytes

object.size(new.env(size = 10e4))
# 56 bytes 

Inserción

La inserción de elementos se puede hacer usando cualquiera de los métodos [[<- o $<- proporcionados para la clase de environment , pero no usando la asignación de "corchete único" ( [<- ) :

H <- new.env()

H[["key"]] <- rnorm(1)

key2 <- "xyz"
H[[key2]] <- data.frame(x = 1:3, y = letters[1:3])

H$another_key <- matrix(rbinom(9, 1, 0.5) > 0, nrow = 3)

H["error"] <- 42
#Error in H["error"] <- 42 : 
#  object of type 'environment' is not subsettable 

Como otras facetas de R, el primer método ( object[[key]] <- value ) generalmente se prefiere al segundo ( object$key <- value ) porque en el primer caso, se puede usar una variable en lugar de un valor literal (por ejemplo, key2 en el ejemplo anterior).

Como suele ser el caso con las implementaciones de mapeo hash, el objeto de environment no almacenará claves duplicadas. El intento de insertar un par clave-valor para una clave existente reemplazará el valor previamente almacenado:

H[["key3"]] <- "original value"

H[["key3"]] <- "new value"

H[["key3"]]
#[1] "new value"

Búsqueda de claves

Del mismo modo, se puede acceder a los elementos con [[ o $ , pero no con [ :

H[["key"]]
#[1] 1.630631
 
H[[key2]]   ## assuming key2 <- "xyz"
#   x y
# 1 1 a
# 2 2 b
# 3 3 c

H$another_key
#       [,1]  [,2]  [,3]
# [1,]  TRUE  TRUE  TRUE
# [2,] FALSE FALSE FALSE
# [3,]  TRUE  TRUE  TRUE

H[1]
#Error in H[1] : object of type 'environment' is not subsettable

Inspeccionando el mapa de hash

Al ser solo un environment normal, el mapa hash puede ser inspeccionado por medios típicos:

names(H)
#[1] "another_key" "xyz"         "key"         "key3"       

ls(H)
#[1] "another_key" "key"         "key3"        "xyz"        
 
str(H)
#<environment: 0x7828228> 
 
ls.str(H)
# another_key :  logi [1:3, 1:3] TRUE FALSE TRUE TRUE FALSE TRUE ...
# key :  num 1.63
# key3 :  chr "new value"
# xyz : 'data.frame':    3 obs. of  2 variables:
#  $ x: int  1 2 3
#  $ y: chr  "a" "b" "c"

Los elementos se pueden eliminar usando rm :

rm(list = c("key", "key3"), envir = H)

ls.str(H)
# another_key :  logi [1:3, 1:3] TRUE FALSE TRUE TRUE FALSE TRUE ...
# xyz : 'data.frame':    3 obs. of  2 variables:
#  $ x: int  1 2 3
#  $ y: chr  "a" "b" "c"

Flexibilidad

Uno de los principales beneficios de usar objetos de environment como tablas hash es su capacidad para almacenar virtualmente cualquier tipo de objeto como valor, incluso otros environment :

H2 <- new.env()

H2[["a"]] <- LETTERS
H2[["b"]] <- as.list(x = 1:5, y = matrix(rnorm(10), 2))
H2[["c"]] <- head(mtcars, 3)
H2[["d"]] <- Sys.Date()
H2[["e"]] <- Sys.time()
H2[["f"]] <- (function() {
    H3 <- new.env()
    for (i in seq_along(names(H2))) {
        H3[[names(H2)[i]]] <- H2[[names(H2)[i]]]
    }
    H3
})()

ls.str(H2)
# a :  chr [1:26] "A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K" ...
# b : List of 5
#  $ : int 1
#  $ : int 2
#  $ : int 3
#  $ : int 4
#  $ : int 5
# c : 'data.frame':    3 obs. of  11 variables:
#  $ mpg : num  21 21 22.8
#  $ cyl : num  6 6 4
#  $ disp: num  160 160 108
#  $ hp  : num  110 110 93
#  $ drat: num  3.9 3.9 3.85
#  $ wt  : num  2.62 2.88 2.32
#  $ qsec: num  16.5 17 18.6
#  $ vs  : num  0 0 1
#  $ am  : num  1 1 1
#  $ gear: num  4 4 4
#  $ carb: num  4 4 1
# d :  Date[1:1], format: "2016-08-03"
# e :  POSIXct[1:1], format: "2016-08-03 19:25:14"
# f : <environment: 0x91a7cb8> 

ls.str(H2$f)
# a :  chr [1:26] "A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K" ...
# b : List of 5
#  $ : int 1
#  $ : int 2
#  $ : int 3
#  $ : int 4
#  $ : int 5
# c : 'data.frame':    3 obs. of  11 variables:
#  $ mpg : num  21 21 22.8
#  $ cyl : num  6 6 4
#  $ disp: num  160 160 108
#  $ hp  : num  110 110 93
#  $ drat: num  3.9 3.9 3.85
#  $ wt  : num  2.62 2.88 2.32
#  $ qsec: num  16.5 17 18.6
#  $ vs  : num  0 0 1
#  $ am  : num  1 1 1
#  $ gear: num  4 4 4
#  $ carb: num  4 4 1
# d :  Date[1:1], format: "2016-08-03"
# e :  POSIXct[1:1], format: "2016-08-03 19:25:14"

Limitaciones

Una de las principales limitaciones de usar objetos de environment como mapas hash es que, a diferencia de muchos aspectos de R, la vectorización no es compatible con la búsqueda / inserción de elementos:

names(H2)
#[1] "a" "b" "c" "d" "e" "f"

H2[[c("a", "b")]]
#Error in H2[[c("a", "b")]] : 
#  wrong arguments for subsetting an environment
 
Keys <- c("a", "b")
H2[[Keys]]
#Error in H2[[Keys]] : wrong arguments for subsetting an environment

Dependiendo de la naturaleza de los datos que se almacenan en el objeto, puede ser posible usar vapply o list2env para asignar muchos elementos a la vez:

E1 <- new.env()
invisible({
    vapply(letters, function(x) {
        E1[[x]] <- rnorm(1)
        logical(0)
    }, FUN.VALUE = logical(0))
})

all.equal(sort(names(E1)), letters)
#[1] TRUE

Keys <- letters
E2 <- list2env(
    setNames(
        as.list(rnorm(26)),
        nm = Keys), 
    envir = NULL,
    hash = TRUE
)

all.equal(sort(names(E2)), letters)
#[1] TRUE

Ninguno de los anteriores es particularmente conciso, pero puede ser preferible a usar un bucle for , etc. cuando el número de pares clave-valor es grande.

paquete: hash

El paquete hash ofrece una estructura de hash en R. Sin embargo, los términos de tiempo para ambas inserciones y lecturas se comparan desfavorablemente con el uso de entornos como hash. Esta documentación simplemente reconoce su existencia y proporciona un código de tiempo de muestra a continuación por las razones mencionadas anteriormente. No hay un caso identificado donde el hash sea una solución apropiada en el código R hoy.

Considerar:

# Generic unique string generator
unique_strings <- function(n){
    string_i <- 1
    string_len <- 1
    ans <- character(n)
    chars <- c(letters,LETTERS)
    new_strings <- function(len,pfx){
    for(i in 1:length(chars)){
        if (len == 1){
        ans[string_i] <<- paste(pfx,chars[i],sep='')
        string_i <<- string_i + 1
        } else {
        new_strings(len-1,pfx=paste(pfx,chars[i],sep=''))
        }
        if (string_i > n) return ()
    }
    }
    while(string_i <= n){
    new_strings(string_len,'')
    string_len <- string_len + 1
    }
    sample(ans)
}

# Generate timings using an enviornment
timingsEnv <- plyr::adply(2^(10:15),.mar=1,.fun=function(i){
    strings <- unique_strings(i)
    ht1 <- new.env(hash=TRUE)
    lapply(strings, function(s){ ht1[[s]] <<- 0L})
    data.frame(
    size=c(i,i),
    seconds=c(
        system.time(for (j in 1:i) ht1[[strings[j]]]==0L)[3]),
    type = c('1_hashedEnv')
    )
})

timingsHash <- plyr::adply(2^(10:15),.mar=1,.fun=function(i){
    strings <- unique_strings(i)
    ht <- hash::hash()
    lapply(strings, function(s) ht[[s]] <<- 0L)
    data.frame(
    size=c(i,i),
    seconds=c(
        system.time(for (j in 1:i) ht[[strings[j]]]==0L)[3]),
    type = c('3_stringHash')
    )
})

paquete: listenv

Aunque package:listenv implementa una interfaz similar a una lista para los entornos, su rendimiento en relación con los entornos con fines similares a hash es pobre en la recuperación de hash . Sin embargo, si los índices son numéricos, puede ser bastante rápido en la recuperación. Sin embargo, tienen otras ventajas, por ejemplo, compatibilidad con el package:future . Cubrir este paquete para ese propósito va más allá del alcance del tema actual. Sin embargo, el código de tiempo proporcionado aquí se puede usar junto con el ejemplo para el paquete: hash para los tiempos de escritura.

timingsListEnv <- plyr::adply(2^(10:15),.mar=1,.fun=function(i){
    strings <- unique_strings(i)
    le <- listenv::listenv()
    lapply(strings, function(s) le[[s]] <<- 0L)
    data.frame(
    size=c(i,i),
    seconds=c(
        system.time(for (k in 1:i) le[[k]]==0L)[3]),
    type = c('2_numericListEnv')
    )
})