Rの配列/リストのランダムアクセスのパフォーマンスを調べてみた

  • ????????????????????

よくRでは配列/リストに対してfor文+インデックスでアクセスしてはいけない、ということが言われますが、そうせざるを得ない場面にも時々遭遇します。少し気になってインデックスでアクセスした時のパフォーマンスの特性を調べて見ました。

通常、データ構造の意味で配列といえばランダムアクセスは定数時間、つまり O(1) で、リストのランダムアクセスは O(n) です。ところが、Rの場合は必ずしもそうなっていないようです

実験条件

2つのアクセスパターンで実験をしました。

■ アクセスパターン1
配列とリストの i 番目の成分に100万回 1 を加える。i=1,2000,4000,6000,…,20000 に対して実行時間を調べる。

■ アクセスパターン2
配列とリストの 1~i 番目の中のランダムに選んだ添字の成分に 1 を加える操作を100万回行う。i=1,2000,4000,6000,…,20000 に対して実行時間を調べる。

結果

2つのアクセスパターンに対する結果を表したのが次の図(使ったスクリプトは記事の一番最後):

縦軸は100万回のランダムアクセスに要した時間、横軸は上の実験条件の所で述べた i を示しています。

考察

はっきり言ってうまく実験がうまく制御されているかどうかについては自信がありませんが(定数分のオーバーヘッドがどこに起因しているのかよくわからない)、この実験の結果を真とすればアクセスパターン1では配列/リストともに定数時間であり、一方、アクセスパターン2では配列は定数時間ですが、リストの方は長さが増加するとアクセス時間が増加することになります。
この実験をする前は

  • リストと名のつくものは無条件で所要時間が線形に増えるだろう

と思っていたので少し新鮮な結果でした。

疑問・まとめ

  • リストの同じ添字にアクセスするのは定数時間なのは、最近アクセスした要素を何らかの方法でキャッシュしているから?
  • 配列に関して、パターン1よりもパターン2のほうが所要時間が短い理由はなぜ?

まあ、100万回程度のアクセスにこんなに時間がかかるならやっぱりできるだけ使わないほうがよいということでしょう(100万次元のベクトルの足し算などはこの実験よりもはるかに高速に行うことができる)。どうしても使う場合は、特にリストの場合はキャッシュが効くように同じ添字になるべく連続してアクセスすべし、ということを頭の片隅にいれておくことにします。

実験に使ったスクリプト

ntry <- 1000000 # Number of repeat

ary.len <- 20000

# Defining index for test
idx <- seq(0,ary.len,ary.len/10)
idx[1] <- 1

# Array access time --- Pattern 1
ary <- rep(0,ary.len)
durations.ary <- matrix(0,length(idx),5)
j <- 1
for(i in idx){
  n <- sample(1:i,ntry,T)
  start <- proc.time()
  for(k in 1:ntry)
    ary[i] <- ary[i] + 1
  durations.ary[j,] <- as.numeric(proc.time() - start)
  j <- j+1
  gc();gc();gc();
}

# List access time --- Pattern 1
lst <- list(0)
for(i in 1:ary.len)
  lst[[i]] <- 0
durations.lst <- matrix(0,length(idx),5)
j <- 1
for(i in idx){
  n <- sample(1:i,ntry,T)
  start <- proc.time()
  for(k in 1:ntry)
    lst[[i]] <- lst[[i]] + 1
  durations.lst[j,] <- as.numeric(proc.time() - start)
  j <- j+1
  gc();gc();gc();
}

tmp <- c(durations.ary[,3],durations.lst[,3])
par(mfrow=c(1,2))
plot(idx,durations.ary[,3],type="n",ylim=c(7,8),xlab="Index of array/list",ylab="Excution time")
lines(idx,durations.ary[,3],type="o",lw=2,col="steelblue")
lines(idx,durations.lst[,3],type="o",lw=2,col="pink")
legend("bottomright",legend=c("Array access time","List access time"),col=c("steelblue","pink"),pch=1,lw=2)
title("Access pattern 1")


# Array access time --- Pattern 2
ary <- rep(0,ary.len)
durations.ary2 <- matrix(0,length(idx),5)
j <- 1
for(i in idx){
  n <- sample(1:i,ntry,T)
  start <- proc.time()
  for(m in n){
    ary[m] <- ary[m] + 1
  }
  durations.ary2[j,] <- as.numeric(proc.time() - start)
  j <- j+1
  gc();gc();gc();
}

# List access time --- Pattern 2
lst <- list(0)
for(i in 1:ary.len)
  lst[[i]] <- 0
durations.lst2 <- matrix(0,length(idx),5)
j <- 1
for(i in idx){
  n <- sample(1:i,ntry,T)
  start <- proc.time()
  for(m in n){
    lst[[m]] <- lst[[m]] + 1
  }
  durations.lst2[j,] <- as.numeric(proc.time() - start)
  j <- j+1
  gc();gc();gc();
}


tmp <- c(durations.ary2[,3],durations.lst2[,3])
plot(idx,durations.ary2[,3],type="n",ylim=c(7,8),xlab="Index of array/list",ylab="Excution time")
lines(idx,durations.ary2[,3],type="o",lw=2,col="steelblue")
lines(idx,durations.lst2[,3],type="o",lw=2,col="pink")
legend("bottomright",legend=c("Array access time","List access time"),col=c("steelblue","pink"),pch=1,lw=2)
title("Access pattern 2")
はてなブックマーク - Rの配列/リストのランダムアクセスのパフォーマンスを調べてみた
Pocket