创建包含大量元素的列表

Question

我需要创建一个包含10^5个元素的列表。 这是我的代码：

gamma1 <- 2.2 
C1 <- zeta(x = gamma1) 
C1inverse <- 1/C1 

listN <- c((10^3), (10^4), (10^5)) 

for(N in listN) { 
    listKseq <- vector(mode = "list", length = 0) 

    for(k in 1:N) { 
    ki <- N * C1inverse * k^(-gamma1) 
    listKseq <- c(listKseq, ki) 
    } 

    print(paste("I created list with N = ", length(listKseq), " nodes.", sep = "")) 
} 

此代码为N = 10^3和N = 10^4但不为N = 10^5。 事实上print的结果是：

[1] "I created list with N = 1000 nodes." 
[1] "I created list with N = 10000 nodes." 

真的是不会产生错误，但执行时间太长，一段时间后，我停止（15分钟是不够的）。

有没有更快的方式来生成这样的列表？

感谢

Answer 1

你有一个“复制并追加”的策略，你分配一个零长度列表，然后在每次迭代

listKseq <- vector(mode = "list", length = 0) 
... 
    listKseq <- c(listKseq, ki) 

反而增长了，“预分配和填充“

listKseq <- vector(mode = "list", length = N) 
... 
    listKseq[[k]] = ki 

的‘复制并追加’的策略，使所有已经计算出的数据，通过每一次循环中的一个副本，因此它具有多项式复杂（如鳞N * (N - 1)/2，大约是N^2）。预分配和填充不会导致副本，并且与N线性缩放。

这里的原始和改进实现

f0 <- function(N) { 
    gamma1 <- 2.2 
    C1 <- zeta(x = gamma1) 
    C1inverse <- 1/C1 
    listKseq <- vector(mode = "list", length = 0) 
    for(k in 1:N) { 
     ki <- N * C1inverse * k^(-gamma1) 
     listKseq <- c(listKseq, ki) 
    } 
    listKseq 
} 

f1 <- function(N) { 
    gamma1 <- 2.2 
    C1 <- zeta(x = gamma1) 
    C1inverse <- 1/C1 
    listKseq <- vector(mode = "list", length = N) 
    for(k in 1:N) { 
     ki <- N * C1inverse * k^(-gamma1) 
     listKseq[[k]] <- ki 
    } 
    listKseq 
} 

，他们返回相同的结果

> identical(f0(1000), f1(1000)) 
[1] TRUE 

，他们扩展描述

> library(microbenchmark) 
> microbenchmark(f0(1000), f0(10000), f1(1000), f1(10000), times=10) 
Unit: milliseconds 
     expr  min   lq  mean  median   uq   max 
    f0(1000) 9.017734 9.128453 9.779840 9.242001 9.275092 14.975256 
f0(10000) 954.733153 965.318717 1002.789735 969.329023 1002.291013 1125.090369 
    f1(1000) 2.332049 2.417364 2.462379 2.461930 2.488568 2.583112 
f1(10000) 22.220757 22.393636 22.725043 22.503726 22.797767 24.376800 
neval cld 
    10 a 
    10 b 
    10 a 
    10 a 

在f1()示范，负担预先分配并填写代码编写人员。使用lapply()得到这个行为自由搭配更富有表现力，结构紧凑，坚固的代码

f1a <- function(N) { 
    gamma1 <- 2.2 
    C1 <- zeta(x = gamma1) 
    C1inverse <- 1/C1 
    lapply(seq_len(N), function(k) N * C1inverse * k^(gamma1)) 
} 

此外，您的计算可以“矢量”，而不是写成循环

f2 <- function(N) { 
    gamma1 <- 2.2 
    C1 <- zeta(x = gamma1) 
    C1inverse <- 1/C1 
    as.list(N * C1inverse * seq_len(N)^(-gamma1)) 
} 

...和它没有意义返回一个列表的长度1个元素，当一个简单的载体会做

f3 <- function(N) { 
    gamma1 <- 2.2 
    C1 <- zeta(x = gamma1) 
    C1inverse <- 1/C1 
    N * C1inverse * seq_len(N)^(-gamma1) 
} 

身份和时间

> identical(unlist(f1(1000)), f3(1000)) 
[1] TRUE 
> microbenchmark(f1(10000), f2(10000), f3(10000), times=10) 
Unit: microseconds 
     expr  min  lq  mean median  uq  max neval 
f1(10000) 22330.886 22482.578 24223.9281 22939.443 24100.424 30414.666 10 
f2(10000) 1196.715 1217.937 1256.7939 1242.236 1256.622 1401.922 10 
f3(10000) 887.824 909.951 981.8528 979.900 996.471 1201.596 10 
cld 
    b 
    a 
    a 

看到这些改进如何帮助 - 算法的扩展对大数据最重要，然后使用矢量化，最后是适当的表示。在某些时候，人们可能会停止考虑代码，因为它足够好。

很明显copy-and-append是一个非常糟糕的策略，所以在未知长度的情况下会过度分配和修剪大小为res = vector("list", 1e7); ...; length(res) = actual_length，或者以大块分配，以便复制并追加，但仅限于几次。