【2018年版】R でハッシュテーブルの速度比較

以前、こういう記事を書いた。

• R でハッシュテーブルの速度比較 #rstatsj

Rでハッシュテーブルを使う方法はいくつかあるが、

• サイズが 1000 以下ならば名前付きベクトルが速い
• それ以上なら環境を使った方法が速い
• hash パッケージは遅いが記述がわかりやすい

ということがわかった。

今回はさらに高速なハッシュテーブルを実装するパッケージを3つ見つけたのでこれらを加えて比較してみる。

• collections
• datastructures
• hashmap

使用するデータは前回と同じく次のコードで生成した。

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 パッケージを使う理由はもはや無いようである。

R言語徹底解説