R Language
Hashmaps

Environnements en tant que cartes de hachage

Remarque: dans les passages suivants, les termes hash map et hash table sont utilisés indifféremment et font référence au même concept , à savoir une structure de données fournissant une recherche de clé efficace grâce à l'utilisation d'une fonction de hachage interne.

introduction

Bien que R ne fournisse pas de structure de table de hachage native, des fonctionnalités similaires peuvent être obtenues en exploitant le fait que l'objet d' environment renvoyé par new.env (par défaut) fournit des recherches de clé hachée. Les deux instructions suivantes sont équivalentes, le paramètre de hash défaut étant TRUE :

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

De plus, on peut spécifier que la table de hachage interne est pré-allouée avec une taille particulière via le paramètre size , qui a une valeur par défaut de 29. Comme tous les autres objets R, l' environment gère sa propre mémoire et sa capacité augmente , alors qu'il n'est pas nécessaire de demander une valeur autre que size par défaut pour la size , cela peut avoir un léger avantage si l'objet contient (éventuellement) un très grand nombre d'éléments. Il convient de noter que l’allocation d’espace supplémentaire via la size ne produit pas en soi un objet avec une empreinte mémoire plus importante:

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

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

Insertion

L'insertion d'éléments peut être effectuée en utilisant l'une des méthodes [[<- ou $<- fournies pour la classe d' environment , mais pas en utilisant une affectation de type «crochet unique» ( [<- ) :

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 

Comme les autres facettes de R, la première méthode ( object[[key]] <- value ) est généralement préférée à la seconde ( object$key <- value ) car dans le premier cas, une variable peut être utilisée à la place d’une valeur littérale (par exemple key2 dans l'exemple ci-dessus).

Comme c'est généralement le cas avec les implémentations de cartes de hachage, l'objet d' environment ne stockera pas les clés en double. Si vous essayez d'insérer une paire clé-valeur pour une clé existante, la valeur précédemment stockée sera remplacée:

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

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

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

Recherche de clé

De même, les éléments peuvent être accédés avec [[ ou $ , mais pas avec [ :

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

Inspection de la carte de hachage

Étant simplement un environment ordinaire, la carte de hachage peut être inspectée par des moyens typiques:

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"

Les éléments peuvent être supprimés à l'aide de 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"

La flexibilité

L'un des principaux avantages de l'utilisation d'objets d' environment comme tables de hachage est leur capacité à stocker virtuellement tout type d'objet en tant que valeur, même d'autres 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"

Limites

L'une des principales limites de l'utilisation d'objets d' environment comme cartes de hachage est que, contrairement à de nombreux aspects de R, la vectorisation n'est pas prise en charge pour la recherche / insertion d'éléments:

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

Selon la nature des données stockées dans l'objet, il est possible d'utiliser vapply ou list2env pour affecter plusieurs éléments à la fois:

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

Aucune de ces réponses n'est particulièrement concise, mais peut être préférable à l'utilisation d'une boucle for , etc. lorsque le nombre de paires clé-valeur est élevé.

paquet: hash

Le paquet de hachage offre une structure de hachage dans R. Cependant, il fait référence à la synchronisation pour les insertions et les lectures, ce qui se compare défavorablement à l'utilisation d'environnements en tant que hachage. Cette documentation reconnaît simplement son existence et fournit un exemple de code temporel ci-dessous pour les raisons indiquées ci-dessus. Il n'y a pas de cas identifié où le hachage est une solution appropriée dans le code R aujourd'hui.

Considérer:

# 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')
    )
})

package: listenv

Bien que package:listenv implémente une interface de type liste pour les environnements, ses performances par rapport aux environnements à des fins de hachage sont médiocres lors de la récupération du hachage . Cependant, si les index sont numériques, ils peuvent être assez rapides lors de la récupération. Cependant, ils présentent d'autres avantages, par exemple la compatibilité avec le package:future . Couvrir ce paquet à cette fin dépasse le cadre du sujet actuel. Cependant, le code temporel fourni ici peut être utilisé avec l'exemple de package: hash pour les timings d'écriture.

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')
    )
})