Jestem ciekawy, jak obiekt typulist jest zaimplementowane. To jest

dynamiczny wektor, który automatycznie zwiększy swój rozmiar, gdy będzie pełny.połączona lista, do której dołączany jest elementO(1), ale dostęp do elementu jestO(n).struktura drzewa zO(log(n)) dostęp do przedmiotu.hashtable zO(1) dostęp do przedmiotu.

Jestem ciekawy, ponieważ listy mogą mieć pary klucz-wartość, które sprawiają, że wyglądają jak tablice mieszające, ale elementy są uporządkowane, co wygląda jak wektor.

Edytować: bolength(list(runif(1e4))) ma wartość 1, więc podczas dodawania elementu do listy wygląda na to, że za każdym razem kopiuje całą listę, co czyni ją bardzo wolną:

Ale szybkość dostępu jest znacznie wolniejsza niż wektor:

z1 <- runif(1e4)
system.time({
  for(i in 1:10000) z1[[1 + i]] <- 1
})

wyjścia:

user  system elapsed 
0.060   0.000   0.062 

ale:

z1 <- list(runif(1e4))
system.time({
  for(i in 1:10000) z1[[1 + i]] <- 1
})

wyjścia:

user  system elapsed 
1.31    0.00    1.31 

zainicjuj listę zawierającą 10000 elementów:

z1 <- as.list(runif(1e4))
system.time({
  for(i in 1:10000) z1[[1 + i]] <- 1
})

wyjścia:

user  system elapsed 
0.060   0.000   0.065 

Aby uzyskać dostęp do klucza i wartości:

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"]]
})

Dane wyjściowe to:

user  system elapsed 
0.01    0.00    0.01 
user  system elapsed 
1.78    0.00    1.78 

To nie jestO(1) dostęp, więc nie jest to tablica mieszania. Mój wniosek jest taki, że nie jest to tablica dynamiczna, ponieważ elementy dołączające spowodują za każdym razem dostęp do pamięci; nie jest hashtable, ponieważ nie ma dostępu do kluczaO(1).