以前、こういう記事を書いた。
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] "eguiqhmukh" "yuvlnhfvba" "cjbcajffur" "nttsfcuszh" "ibvgfrjnro"
1. 名前付きベクトル
名前付きベクトルは最もシンプルなハッシュテーブルの実装である。
named_values <- values names(named_values) <- labels named_values[target] #> eguiqhmukh yuvlnhfvba cjbcajffur nttsfcuszh ibvgfrjnro #> "eguiqhmukh2" "yuvlnhfvba2" "cjbcajffur1" "nttsfcuszh8" "ibvgfrjnro6"
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)) #> eguiqhmukh yuvlnhfvba cjbcajffur nttsfcuszh ibvgfrjnro #> "eguiqhmukh2" "yuvlnhfvba2" "cjbcajffur1" "nttsfcuszh8" "ibvgfrjnro6"
3. hash パッケージ
hash パッケージを使うと直感的で簡潔な記法でハッシュテーブルを扱える。 結果の順序が保証されないことには注意が必要である。
library(hash) h <- hash(labels, values) values(h[target]) #> cjbcajffur eguiqhmukh ibvgfrjnro nttsfcuszh yuvlnhfvba #> "cjbcajffur1" "eguiqhmukh2" "ibvgfrjnro6" "nttsfcuszh8" "yuvlnhfvba2"
4. collections パッケージ
collections は高速なコンテナデータ型を提供するパッケージであり、ハッシュテーブルは辞書型 Dict
として提供される。
メソッドはベクトル化されていないことに注意が必要である。
library(collections) d <- Dict$new() invisible(Vectorize(d$set)(labels, values)) Vectorize(d$get)(target) #> eguiqhmukh yuvlnhfvba cjbcajffur nttsfcuszh ibvgfrjnro #> "eguiqhmukh2" "yuvlnhfvba2" "cjbcajffur1" "nttsfcuszh8" "ibvgfrjnro6"
5. datastructures
datastructures パッケージはいくつかの高度なデータ型を提供する。
ハッシュテーブルは hashmap
で提供される。
library(datastructures) hm <- hashmap("character") hm[labels] <- values unlist(hm[target]) #> [1] "eguiqhmukh2" "yuvlnhfvba2" "cjbcajffur1" "nttsfcuszh8" "ibvgfrjnro6"
6. hashmap パッケージ
hashmap パッケージはキーとバリューに特定の型しか使えないが環境より速いとのこと。
library(hashmap) H <- hashmap(labels, values) H[[target]] #> [1] "eguiqhmukh2" "yuvlnhfvba2" "cjbcajffur1" "nttsfcuszh8" "ibvgfrjnro6"
速度比較
上で紹介した 6 つの方法について速度を比較してみる。 テーブルサイズ N を 100~100000 まで変化させて速度を調べている。
library(magicfor) magic_for() for(N in 10^(2:5)) { # Create Data ------------------------------------------------------------- labels <- generate_random_labels(N) values <- generate_random_values(labels) df <- data.frame(labels, values, stringsAsFactors = FALSE) target <- sample(labels, 100) # Preparation ------------------------------------------------------------- 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) # Benchmark --------------------------------------------------------------- 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 パッケージを使う理由はもはや無いようである。

- 作者: Hadley Wickham,石田基広,市川太祐,高柳慎一,福島真太朗
- 出版社/メーカー: 共立出版
- 発売日: 2016/02/10
- メディア: 単行本
- この商品を含むブログ (29件) を見る