タイプのオブジェクトがどのように実装されているのか興味がありますlist。それは...ですか
- いっぱいになると自動的にサイズが大きくなる動的ベクトル。
- アイテムの追加は です
O(1)が、アイテムへのアクセスは ですO(n)。 O(log(n))アイテムにアクセスできるツリー構造。O(1)アイテムにアクセスできるハッシュテーブル。
リストにはハッシュ テーブルのように見えるキーと値のペアを含めることができるため、興味がありますが、要素はベクトルのように順番に並んでいます。
編集:length(list(runif(1e4)))は 1 であるため、要素をリストに追加すると、毎回リスト全体をコピーするように見え、非常に遅くなります:
ただし、アクセス速度はベクトルよりもはるかに遅くなります。
z1 <- runif(1e4)
system.time({
for(i in 1:10000) z1[[1 + i]] <- 1
})
出力:
user system elapsed
0.060 0.000 0.062
しかし：
z1 <- list(runif(1e4))
system.time({
for(i in 1:10000) z1[[1 + i]] <- 1
})
出力:
user system elapsed
1.31 0.00 1.31
10000 要素のリストを初期化します。
z1 <- as.list(runif(1e4))
system.time({
for(i in 1:10000) z1[[1 + i]] <- 1
})
出力:
user system elapsed
0.060 0.000 0.065
キーと値のアクセスの場合:
z1 <- list()
for(i in 1:10000){key <- as.character(i); z1[[key]] <- i}
system.time({
for(i in 1:10000) x <- z1[["1"]]
})
system.time({
for(i in 1:10000) x <- z1[["10000"]]
})
出力は次のとおりです。
user system elapsed
0.01 0.00 0.01
user system elapsed
1.78 0.00 1.78
アクセスではないO(1)ので、ハッシュテーブルではありません。私の結論は、アイテムを追加すると毎回メモリアクセスが発生するため、動的配列ではないということです。キーによるアクセスは ではないため、ハッシュテーブルではありませんO(1)。