R Language
HashMaps

Ambienti come mappe di hash

Nota: nei passaggi successivi, i termini hash map e hash table sono usati in modo intercambiabile e si riferiscono allo stesso concetto , vale a dire una struttura dati che fornisce una efficiente ricerca di chiavi attraverso l'uso di una funzione hash interna.

introduzione

Sebbene R non fornisca una struttura di tabella hash nativa, è possibile ottenere funzionalità simili sfruttando il fatto che l'oggetto environment restituito da new.env (per impostazione predefinita) fornisce ricerche di chiavi con hash. Le seguenti due istruzioni sono equivalenti, poiché il parametro hash impostato su TRUE :

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

Inoltre, si può specificare che la tabella hash interna sia pre-allocata con una dimensione particolare tramite il parametro size , che ha un valore predefinito di 29. Come tutti gli altri oggetti R, l' environment s gestisce la propria memoria e aumenterà di capacità come necessario quindi, anche se non è necessario richiedere un valore non predefinito per le size , potrebbe esserci un leggero vantaggio in termini di prestazioni se l'oggetto contiene (eventualmente) un numero molto elevato di elementi. Vale la pena notare che l'allocazione di spazio aggiuntivo tramite le size non comporta, di per sé, un oggetto con un ingombro di memoria maggiore:

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

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

Inserimento

L'inserimento di elementi può essere fatto utilizzando uno dei [[<- o $<- metodi forniti per la classe environment , ma non usando l'assegnazione "parentesi quadra" ( [<- ) :

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 

Come altri aspetti di R, il primo metodo ( object[[key]] <- value ) è generalmente preferito al secondo ( object$key <- value ) perché nel primo caso, una variabile può essere usata al posto di un valore letterale (ad es. key2 nell'esempio sopra).

Come generalmente accade con le implementazioni delle mappe hash, l'oggetto environment non memorizza le chiavi duplicate. Il tentativo di inserire una coppia chiave-valore per una chiave esistente sostituirà il valore memorizzato in precedenza:

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

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

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

Ricerca chiave

Allo stesso modo, è possibile accedere agli elementi con [[ o $ , ma non 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

Ispezione della mappa hash

Essendo solo un environment ordinario, la mappa hash può essere ispezionata con i mezzi tipici:

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"

Gli elementi possono essere rimossi 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"

Flessibilità

Uno dei principali vantaggi dell'utilizzo di oggetti di environment come tabelle hash è la loro capacità di memorizzare virtualmente qualsiasi tipo di oggetto, anche altri 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"

limitazioni

Uno dei principali limiti dell'utilizzo di oggetti di environment come mappe hash è che, a differenza di molti aspetti di R, la vettorizzazione non è supportata per la ricerca / inserimento di elementi:

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

A seconda della natura dei dati memorizzati nell'oggetto, può essere possibile utilizzare vapply o list2env per assegnare più elementi contemporaneamente:

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

Nessuno dei precedenti è particolarmente conciso, ma può essere preferibile utilizzare un ciclo for , ecc. Quando il numero di coppie chiave-valore è elevato.

Pacchetto: hash

Il pacchetto hash offre una struttura hash in R. Tuttavia, i termini di sincronizzazione per entrambi gli inserimenti e le letture si confrontano sfavorevolmente con gli ambienti di utilizzo come hash. Questa documentazione riconosce semplicemente la sua esistenza e fornisce un codice temporale di esempio per i motivi sopra indicati. Non esiste un caso identificato in cui l'hash è una soluzione appropriata nel codice R oggi.

Tenere conto:

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

Pacchetto: listenv

Sebbene package:listenv implementa un'interfaccia list-like per gli ambienti, le sue prestazioni relative agli ambienti per scopi hash sono scarse per il recupero hash . Tuttavia, se gli indici sono numerici, può essere abbastanza veloce durante il recupero. Tuttavia, hanno altri vantaggi, ad esempio la compatibilità con il package:future . Coprire questo pacchetto per questo scopo va oltre lo scopo del tema attuale. Tuttavia, il codice temporale fornito qui può essere utilizzato insieme all'esempio per il pacchetto: hash per i tempi di scrittura.

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