Какова внутренняя реализация списков?

Мне любопытно, как реализуется объект типа 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).

Ответ 1