R Language
HashMaps
Поиск…
Среды как хэш-карты
Примечание: в последующих проходах символы hash-карта и хеш-таблица используются взаимозаменяемо и относятся к одной и той же концепции , а именно к структуре данных, обеспечивающей эффективный поиск ключей с использованием внутренней хэш-функции.
Вступление
Хотя R не предоставляет собственную структуру хеш-таблицы, подобную функциональность можно достичь, используя тот факт, что объект environment возвращенный из new.env (по умолчанию), предоставляет хешированные ключевые поисковые запросы. Следующие два утверждения эквивалентны, так как hash параметр по умолчанию имеет значение TRUE :
H <- new.env(hash = TRUE)
H <- new.env()
Кроме того, можно указать, что внутренняя хеш-таблица предварительно назначается определенным размером через параметр size , который имеет значение по умолчанию 29. Как и все другие объекты R, environment управляет собственной памятью и будет увеличиваться по мере необходимости , поэтому, хотя нет необходимости запрашивать значение по умолчанию для size , может быть небольшое преимущество в производительности при этом, если объект (в конечном счете) будет содержать очень большое количество элементов. Стоит отметить, что выделение дополнительного пространства по size само по себе не приводит к созданию объекта с большим объемом памяти:
object.size(new.env())
# 56 bytes
object.size(new.env(size = 10e4))
# 56 bytes
вставка
Вставка элементов может быть выполнена с использованием любого из методов [[<- или $<- заданных для класса environment , но не с помощью назначения «одиночная скобка» ( [<- ) :
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
Как и другие грани R, первый метод ( object[[key]] <- value ) обычно предпочитается второму ( object$key <- value ), потому что в первом случае вместо литерального значения может использоваться переменная (например, key2 в примере выше).
Как правило, в случае реализации хэш-карт объект environment не будет хранить дубликаты ключей. Попытка вставить пару «ключ-значение» для существующего ключа заменит ранее сохраненное значение:
H[["key3"]] <- "original value"
H[["key3"]] <- "new value"
H[["key3"]]
#[1] "new value"
Поиск ключевых слов
Аналогичным образом, элементы могут быть доступны с помощью [[ или $ , но не с [ :
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
Проверка хэш-карты
Будучи просто обычной environment , хэш-карту можно проверить обычными способами:
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"
Элементы можно удалить с помощью 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"
гибкость
Одним из основных преимуществ использования объектов environment как хеш-таблиц является их способность хранить практически любой тип объекта в качестве значения, даже в других 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"
Ограничения
Одним из основных ограничений использования объектов environment качестве хэш-карт является то, что в отличие от многих аспектов R векторизация не поддерживается для поиска / вставки элемента:
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
В зависимости от характера данных, хранящихся в объекте, может быть возможно использовать vapply или list2env для назначения сразу нескольких элементов:
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
Ни один из вышеперечисленных не является особенно кратким, но может быть предпочтительнее использовать цикл for и т. Д., Когда число пар ключ-значение велико.
пакет: хэш
Хэш-пакет предлагает хэш-структуру в R. Однако, сроки определения времени для обеих вставок и чтения сравниваются с неблагоприятными условиями использования в качестве хеша. Эта документация просто подтверждает ее существование и предоставляет примерный временной код ниже по вышеуказанным причинам. Не существует определенного случая, когда хеш является подходящим решением в R-коде сегодня.
Рассматривать:
# 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')
)
})
пакет: listenv
Хотя package:listenv реализует список-подобный интерфейс для сред, его производительность по сравнению с средами для хэш-подобных целей невелика при хэш-поиске . Однако, если индексы являются числовыми, это может быть довольно быстро при поиске. Однако у них есть другие преимущества, например совместимость с package:future . Покрытие этого пакета для этой цели выходит за рамки текущей темы. Однако приведенный здесь код синхронизации может использоваться в сочетании с примером для пакета: хэш для таймингов записи.
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')
)
})