R Language
Hashmaps
Suche…
Umgebungen als Hash-Maps
Hinweis: In den folgenden Passagen werden die Begriffe Hash-Map und Hash-Tabelle austauschbar verwendet und beziehen sich auf dasselbe Konzept , nämlich auf eine Datenstruktur, die eine effiziente Schlüsselsuche durch Verwendung einer internen Hash-Funktion ermöglicht.
Einführung
Obwohl R keine native Hashtabellenstruktur bereitstellt, kann eine ähnliche Funktionalität erreicht werden, indem die Tatsache genutzt wird, dass das environment , das von new.env (standardmäßig), Hash-Schlüsselsuchen bietet. Die folgenden beiden Anweisungen sind gleichwertig, da der hash Parameter standardmäßig TRUE :
H <- new.env(hash = TRUE)
H <- new.env()
Darüber hinaus kann angegeben werden, dass die interne Hashtabelle über den Parameter size mit einer bestimmten Größe vorab zugewiesen wird. Der Parameter hat den Standardwert 29. Wie alle anderen R-Objekte verwaltet auch die environment ihren eigenen Speicher und nimmt bei Bedarf mit der Kapazität zu Obwohl es nicht erforderlich ist, einen nicht voreingestellten Wert für size anzufordern, kann dies einen geringfügigen Leistungsvorteil zur Folge haben, wenn das Objekt (möglicherweise) eine sehr große Anzahl von Elementen enthält. Es ist erwähnenswert, dass das Zuweisen von zusätzlichem Speicherplatz über die size sich nicht zu einem Objekt mit einem größeren Speicherbedarf führt:
object.size(new.env())
# 56 bytes
object.size(new.env(size = 10e4))
# 56 bytes
Einfügung
Das Einfügen von Elementen kann entweder mit der für die environment bereitgestellten [[<- oder $<- Methode durchgeführt werden, jedoch nicht mit der Zuweisung einer einzelnen Klammer ( [<- ) :
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
Wie bei anderen Facetten von R wird die erste Methode ( object[[key]] <- value ) im Allgemeinen der zweiten Methode ( object[[key]] <- value object$key <- value ) vorgezogen, da im ersten Fall eine Variable anstelle eines Literalwerts verwendet werden kann (zB key2 im obigen Beispiel).
Wie bei Hash-Map-Implementierungen im Allgemeinen wird das environment keine doppelten Schlüssel speichern. Der Versuch, ein Schlüsselwertpaar für einen vorhandenen Schlüssel einzufügen, ersetzt den zuvor gespeicherten Wert:
H[["key3"]] <- "original value"
H[["key3"]] <- "new value"
H[["key3"]]
#[1] "new value"
Schlüsselsuche
Ebenso kann auf Elemente mit [[ oder $ ] zugegriffen werden, jedoch nicht mit [ :
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
Überprüfen der Hashkarte
Da es sich um eine gewöhnliche environment , kann die Hash-Karte mit typischen Mitteln überprüft werden:
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"
Elemente können mit rm entfernt werden:
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"
Flexibilität
Ein Hauptvorteil der Verwendung von environment als Hashtabellen besteht darin, dass praktisch alle Arten von Objekten als Wert gespeichert werden können, selbst in anderen 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"
Einschränkungen
Eine der größten Einschränkungen bei der Verwendung von environment als Hash-Maps besteht darin, dass im Gegensatz zu vielen Aspekten von R die Vektorisierung für das Suchen / Einfügen von Elementen nicht unterstützt wird:
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
Abhängig von der Art der im Objekt gespeicherten Daten kann es möglich sein, vapply oder list2env für die gleichzeitige Zuweisung vieler Elemente zu verwenden:
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
Keines der obigen Punkte ist besonders knapp, kann jedoch der Verwendung einer for Schleife usw. vorzuziehen sein, wenn die Anzahl der Schlüsselwertpaare groß ist.
Paket: Hash
Das Hash-Paket bietet eine Hash-Struktur in R. Allerdings ist das Timing für beide Einfügungen und Lesevorgänge ungünstig mit der Verwendung von Umgebungen als Hash. Diese Dokumentation bestätigt lediglich das Vorhandensein und enthält aus den oben genannten Gründen einen Beispiel-Timing-Code. Es gibt keinen identifizierten Fall, in dem Hash heute eine geeignete Lösung im R-Code ist.
Erwägen:
# 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
Obwohl package:listenv eine package:listenv Schnittstelle für Umgebungen implementiert, ist seine Leistung im Vergleich zu Umgebungen für Hash-ähnliche Zwecke beim Abrufen von Hashes schlecht . Wenn die Indizes jedoch numerisch sind, kann es beim Abrufen recht schnell gehen. Sie haben jedoch andere Vorteile, z. B. Kompatibilität mit package:future . Das Abdecken dieses Pakets zu diesem Zweck geht über den Rahmen des aktuellen Themas hinaus. Der hier angegebene Timing-Code kann jedoch in Verbindung mit dem Beispiel für package: hash für Schreib-Timings verwendet werden.
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')
)
})