Sök…


Miljöer som hashkarta

Obs: i de efterföljande passagerna används termerna hashkarta och hashtabellen utbytbart och hänvisar till samma koncept , nämligen en datastruktur som ger effektiv nyckeluppslagning genom användning av en intern hashfunktion.

Introduktion

Även om R inte ger en nativ hashtabell struktur, kan liknande funktion uppnås genom att utnyttja det faktum att environment objektet returneras från new.env (som standard) tillhandahåller hashas nyckeluppslagningar. Följande två påståenden är likvärdiga eftersom hash parametern är standard för TRUE :

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

Dessutom kan man specificera att den interna hashtabellen är fördelad med en viss storlek via size , som har ett standardvärde på 29. Liksom alla andra R-objekt hanterar environment sitt eget minne och kommer att växa i kapacitet efter behov , så även om det inte är nödvändigt att begära ett icke-standardvärde för size , kan det vara en liten prestationsfördel att göra det om objektet (så småningom) kommer att innehålla ett mycket stort antal element. Det är värt att notera att tilldelning av extra utrymme via size inte i sig leder till ett objekt med ett större minnesfotavtryck:

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

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

Införande

Infogning av element kan göras med hjälp av någon av [[<- eller $<- metoderna som tillhandahålls för environment , men inte med hjälp av "single bracket" -uppdrag ( [<- ) :

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 

Liksom andra fasetter av R föredras den första metoden ( object[[key]] <- value ) generellt framför den andra ( object$key <- value ) eftersom i det förra fallet kan en variabel användas istället för ett bokstavsvärde (t.ex. key2 i exemplet ovan).

Som vanligen är fallet med hash kart implementeringar, den environment kommer objektet inte att lagra dubbla nycklar. Att försöka infoga ett nyckelvärdespar för en befintlig nyckel kommer att ersätta det tidigare lagrade värdet:

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

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

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

Nyckeluppslag

På samma sätt kan element nås med [[ eller $ , men inte med [ :

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

Inspekterar Hash-kartan

Eftersom det bara är en vanlig environment kan haschkarta inspekteras på typiska sätt:

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"

Element kan tas bort med 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"

Flexibilitet

En av de stora fördelarna med att använda environment som hashtabeller är deras förmåga att lagra nästan alla typer av objekt som ett värde, även andra environment s:

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"

begränsningar

En av de huvudsakliga begränsningarna med att använda environment objekt som hash-kartor är att, till skillnad från många aspekter av R, är vektorisering stöds inte för elementet lookup / insättning:

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

Beroende på vilken typ av data som lagras i objektet kan det vara möjligt att använda vapply eller list2env för att tilldela många element på en gång:

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

Inget av ovanstående är särskilt kortfattat, men kan vara att föredra framför att använda en for slinga, etc. när antalet nyckelvärdespar är stort.

paket: hash

Hashpaketet erbjuder en hashstruktur i R. Men det är tidsbestämning för båda skärmen och läser det jämförs negativt med att använda miljöer som hash. Denna dokumentation bekräftar helt enkelt dess existens och tillhandahåller en exempeltidskod nedan av ovanstående skäl. Det finns inget identifierat fall där hash är en lämplig lösning i R-koden idag.

Överväga:

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

paket: listenv

Även om package:listenv implementerar ett package:listenv gränssnitt till miljöer, är dess prestanda i förhållande till miljöer för hashliknande ändamål dålig vid hashhämtning . Men om indexen är numeriska kan det vara ganska snabbt vid hämtning. Men de har andra fördelar, t.ex. kompatibilitet med package:future . Att täcka detta paket för detta ändamål överskrider omfattningen av det aktuella ämnet. Den tidkod som anges här kan emellertid användas i samband med exemplet för paketet: hash för skrivtider.

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


Modified text is an extract of the original Stack Overflow Documentation
Licensierat under CC BY-SA 3.0
Inte anslutet till Stack Overflow