R Language
Hashmaps
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')
)
})
