r - 追加（向量/列表）的时间复杂度是多少？

Question

https://www.programmingr.com/fast-r-append-list/

我没有发现对向量或列表进行附加操作的时间复杂度。

这在任何地方都有记录吗？

假设我有 n 个元素，我必须一个一个地追加。是否存在时间复杂度为 n 的数据结构来追加 n 个元素？

标签： r

Answer 1

这是一个函数，用于测试将值分配给向量的三种不同方式的运行时间。
前两个通过将新元素附加到其末尾来扩展向量。最后一个通过创建包含元素的向量来分配空间，n然后用新元素填充向量。
用包装测量时间，用图形microbenchmark绘制中位数。ggplot2

原子向量计时

fun <- function(N = 1:10, times = 100){
  if(!require(microbenchmark)){
    stop("Package 'microbenchmark' is not installed")
  }
  out <- lapply(2^N, function(n){
    mb <- microbenchmark(
      c = {
        x <- NULL
        for(i in seq_len(n)) x <- c(x, i)
      },
      append = {
        x <- NULL
        for(i in seq_len(n)) append(x, i)
      },
      allocate = {
        x <- numeric(n)
        for(i in seq_len(n)) x[i] <- i
      },
      times = times
    )
    mb$n <- n
    aggregate(time ~ expr + n, mb, median)
  })
  out <- do.call(rbind, out)
  row.names(out) <- NULL
  out
}

library(ggplot2)

times <- fun(1:12)

ggplot(times, aes(n, time, color = expr)) +
  geom_line() +
  geom_point() +
  theme_bw()

---

list计时

这个函数与上面的函数几乎相同，但创建和扩展类“list”的对象。

令人惊讶的是，现在通过在当前最后一个元素之后分配新元素来扩展列表比append.

funList <- function(N = 1:10, times = 100){
  if(!require(microbenchmark)){
    stop("Package 'microbenchmark' is not installed")
  }
  out <- lapply(2^N, function(n){
    mb <- microbenchmark(
      List = {
        x <- list()
        for(i in seq_len(n)) x[[i]] <- i
      },
      append = {
        x <- list()
        for(i in seq_len(n)) append(x, i)
      },
      allocate = {
        x <- vector("list", n)
        for(i in seq_len(n)) x[[i]] <- i
      },
      times = times
    )
    mb$n <- n
    aggregate(time ~ expr + n, mb, median)
  })
  out <- do.call(rbind, out)
  row.names(out) <- NULL
  out
}

library(ggplot2)

times <- funList(1:12)

ggplot(times, aes(n, time, color = expr)) +
  geom_line() +
  geom_point() +
  theme_bw()