R Language
ハッシュマップ
サーチ…
ハッシュマップとしての環境
注:以降の節では、 ハッシュマップとハッシュテーブルという用語は同じ意味で使用され、 同じ概念 、つまり内部ハッシュ関数を使用して効率的なキールックアップを提供するデータ構造を指しています。
前書き
Rはネイティブのハッシュテーブル構造を提供しませんが、 new.env
(デフォルト)から返されたenvironment
オブジェクトがハッシュされたキー参照を提供するという事実を利用することで、同様の機能を実現できます。次の2つの文は同等です。 hash
パラメータのデフォルトはTRUE
です。
H <- new.env(hash = TRUE)
H <- new.env()
さらに、内部ハッシュテーブルが、デフォルト値29を有するsize
パラメータを介して特定のサイズで事前割り当てされることを指定することができる。他のすべての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
)が2番目の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
オブジェクトをハッシュテーブルとして使用する主な利点の1つは、 他の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
オブジェクトをハッシュマップとして使用する際の主な制限の1つは、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
互換性package:future
。その目的のためにこのパッケージをカバーすることは、現在の話題の範囲を超えています。ただし、ここで提供されるタイミングコードは、write:タイミングのためのpackage:hashの例と組み合わせて使用できます。
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')
)
})