R Language
Hashmaps
Zoeken…
Omgevingen als hash-kaarten
Opmerking: in de volgende passages worden de termen hashmap en hashtabel onderling uitwisselbaar gebruikt en verwijzen ze naar hetzelfde concept , namelijk een gegevensstructuur die efficiënte sleutelopzoeking biedt door het gebruik van een interne hashfunctie.
Invoering
Hoewel R geen native hashtabelstructuur biedt, kan vergelijkbare functionaliteit worden bereikt door gebruik te maken van het feit dat het environment wordt geretourneerd door new.env (standaard) hashed key-lookups biedt. De volgende twee instructies zijn equivalent, omdat de hash parameter standaard TRUE :
H <- new.env(hash = TRUE)
H <- new.env()
Bovendien kan men aangeven dat de interne hash tabel is die al zijn toegewezen met een bepaalde grootte via de size parameter, die een standaard waarde van 29. Net als alle andere R objecten heeft, environment en het beheer van hun eigen geheugen en groeien in capaciteit als dat nodig is , dus hoewel het niet nodig is om een niet-standaardwaarde voor de size , kan dit een klein prestatievoordeel hebben als het object (uiteindelijk) een zeer groot aantal elementen zal bevatten. Het is vermeldenswaard dat het toewijzen van extra ruimte via size zichzelf niet resulteert in een object met een grotere geheugenvoetafdruk:
object.size(new.env())
# 56 bytes
object.size(new.env(size = 10e4))
# 56 bytes
Invoeging
Het invoegen van elementen kan worden gedaan met behulp van een van de [[<- of $<- methoden die zijn opgegeven voor de environment , maar niet met de toewijzing van "enkele haakjes" ( [<- ) :
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
Net als andere facetten van R, heeft de eerste methode ( object[[key]] <- value ) over het algemeen de voorkeur boven de tweede ( object$key <- value ) omdat in het eerste geval een variabele kan worden gebruikt in plaats van een letterlijke waarde (bijvoorbeeld key2 in het bovenstaande voorbeeld).
Zoals meestal het geval is bij hash-kaartimplementaties, slaat het environment geen dubbele sleutels op. Als u probeert een sleutel / waarde-paar in te voegen voor een bestaande sleutel, wordt de eerder opgeslagen waarde vervangen:
H[["key3"]] <- "original value"
H[["key3"]] <- "new value"
H[["key3"]]
#[1] "new value"
Sleutel opzoeken
Evenzo kunnen elementen worden geopend met [[ of $ , maar niet met [ :
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
De hashkaart inspecteren
Omdat het een gewone environment , kan de hashkaart op typische manieren worden geïnspecteerd:
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"
Elementen kunnen worden verwijderd met behulp van 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"
Flexibiliteit
Een van de grote voordelen van het gebruik van environment als hashtabellen is hun mogelijkheid om vrijwel elk type object als waarde op te slaan, zelfs andere 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"
beperkingen
Een van de belangrijkste beperkingen van het gebruik van environment als hash-kaarten is dat, in tegenstelling tot veel andere aspecten van R, vectorisatie niet wordt ondersteund voor het zoeken / invoegen van elementen:
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
Afhankelijk van de aard van de gegevens die in het object worden opgeslagen, kan het mogelijk zijn om vapply of list2env te gebruiken om veel elementen tegelijk toe te wijzen:
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
Geen van beide is bijzonder beknopt, maar kan de voorkeur hebben boven het gebruik van een for lus, enz. Wanneer het aantal sleutel / waarde-paren groot is.
pakket: hash
Het hash-pakket biedt een hash-structuur in R. Het is echter qua timing voor beide inserts en leest dat het ongunstig is in vergelijking met het gebruik van omgevingen als hash. Deze documentatie erkent eenvoudig het bestaan ervan en biedt onderstaande voorbeeld timingcode om de bovengenoemde redenen. Er is geen geval geïdentificeerd waarin hash vandaag een geschikte oplossing in R-code is.
Overwegen:
# 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')
)
})
pakket: listenv
Hoewel package:listenv een package:listenv interface implementeert voor omgevingen, presteert deze ten opzichte van omgevingen voor hash-achtige doeleinden slecht bij het ophalen van hash . Als de indexen echter numeriek zijn, kan het vrij snel zijn bij het ophalen. Ze hebben echter andere voordelen, bijvoorbeeld compatibiliteit met package:future . Daartoe gaat dit pakket buiten het bereik van het huidige onderwerp. De hier opgegeven timingcode kan echter worden gebruikt in combinatie met het voorbeeld voor pakket: hash voor schrijftimings.
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')
)
})
