以前、こういう記事を書いた。
Rでハッシュテーブルを使う方法はいくつかあるが、
- サイズが 1000 以下ならば名前付きベクトルが速い
- それ以上なら環境を使った方法が速い
- hash パッケージは遅いが記述がわかりやすい
ということがわかった。
今回はさらに高速なハッシュテーブルを実装するパッケージを3つ見つけたのでこれらを加えて比較してみる。
使用するデータは前回と同じく次のコードで生成した。
generate_random_labels <- function(num, length = 10) {
apply(Vectorize(sample, "size")(letters, rep(num, length), replace = TRUE), 1, function(row) paste(row, collapse = ""))
}
generate_random_values <- function(labels, digits = 1) {
format <- paste0("%s%0", digits, "d")
sprintf(format, labels, Vectorize(sample, "size")(seq_len(10^digits-1), rep(1,length(labels))))
}
N <- 1000
labels <- generate_random_labels(N)
values <- generate_random_values(labels)
df <- data.frame(labels, values, stringsAsFactors = FALSE)
target <- sample(labels, 5)
target
1. 名前付きベクトル
名前付きベクトルは最もシンプルなハッシュテーブルの実装である。
named_values <- values
names(named_values) <- labels
named_values[target]
2. 環境
『R言語徹底解説』第8章 (p.160) には、R における環境 (environment) の特別な使用方法としてハッシュマップとして使えると書いてある。
前回の記事ではやや複雑に書いたが、list2env(setNames()) イディオムを使うとやや簡潔に書ける。
hash_env <- list2env(setNames(as.list(values), labels), hash = TRUE)
unlist(mget(target, envir = hash_env))
3. hash パッケージ
hash パッケージを使うと直感的で簡潔な記法でハッシュテーブルを扱える。
結果の順序が保証されないことには注意が必要である。
library(hash)
h <- hash(labels, values)
values(h[target])
4. collections パッケージ
collections は高速なコンテナデータ型を提供するパッケージであり、ハッシュテーブルは辞書型 Dict として提供される。
メソッドはベクトル化されていないことに注意が必要である。
library(collections)
d <- Dict$new()
invisible(Vectorize(d$set)(labels, values))
Vectorize(d$get)(target)
5. datastructures
datastructures パッケージはいくつかの高度なデータ型を提供する。
ハッシュテーブルは hashmap で提供される。
library(datastructures)
hm <- hashmap("character")
hm[labels] <- values
unlist(hm[target])
6. hashmap パッケージ
hashmap パッケージはキーとバリューに特定の型しか使えないが環境より速いとのこと。
library(hashmap)
H <- hashmap(labels, values)
H[[target]]
速度比較
上で紹介した 6 つの方法について速度を比較してみる。
テーブルサイズ N を 100～100000 まで変化させて速度を調べている。
library(magicfor)
magic_for()
for(N in 10^(2:5)) {
labels <- generate_random_labels(N)
values <- generate_random_values(labels)
df <- data.frame(labels, values, stringsAsFactors = FALSE)
target <- sample(labels, 100)
named_values <- values
names(named_values) <- labels
hash_env <- list2env(setNames(as.list(values), labels), hash = TRUE)
library(hash)
h <- hash(labels, values)
library(collections)
d <- Dict$new()
invisible(Vectorize(d$set)(labels, values))
library(datastructures)
hm <- datastructures::hashmap("character")
hm[labels] <- values
library(hashmap)
HH <- hashmap::hashmap(labels, values)
library(microbenchmark)
mb_result <- microbenchmark(
named_vector = {
named_values[target]
},
environment = {
unlist(mget(target, envir = hash_env))
},
hash = {
hash::values(h[target])
},
collections = {
Vectorize(d$get)(target)
},
datastructure = {
unlist(hm[target])
},
hashmap = {
HH[[target]]
}
)
time_df <- data.frame(N=as.character(N), mb_result)
time_df
}
result <- Reduce(rbind, magic_result()$time_df)
結果を可視化する。
library(ggplot2)
ggplot(result, aes(x=N, y=time, fill=expr)) +
geom_boxplot() + scale_y_log10() + facet_wrap(~expr)
library(dplyr)
result_mean <- result %>%
group_by(N, expr) %>%
summarise(mean=mean(time))
ggplot(result_mean, aes(x=N, y=mean, group=expr, color=expr)) +
geom_line() + scale_y_log10()
テーブルサイズが数百程度であれば名前付きベクトルが速い。
それ以上は環境が一番速いようである。
hashmap は環境と遜色ない速度であり、直感的で簡潔な記述ができる。
hash パッケージを使う理由はもはや無いようである。
