arrays - Julia 中的push!() 和append!() 方法的效率如何？

Question

关于this页面上说方法 push!() 和 append!() 非常高效。

我的问题是它们的效率到底有多高？

也就是说，

如果知道最终数组的大小，那么预分配数组或使用 append!()/push! 增量增长数组是否仍然更快？ () 也会同样有效吗？

现在考虑一下当一个人不知道最终数组的大小时的情况。例如，将多个数组合并为 1 个大数组(称之为 A)。

实现这一目标的两种方法:

1. append!()-将每个数组添加到 A，其大小尚未预先分配。
2. 首先对每个数组的维度进行求和，以找到合并数组 A 的最终大小。然后预分配 A 并复制每个数组的内容。

在这种情况下，哪一个效率更高？

Answer 1

此类问题的答案通常是:“视情况而定”。例如，您想要创建什么大小的数组？数组的元素类型是什么？

但是，如果您只是寻求启发式方法，为什么不运行简单的速度测试呢？例如，以下代码片段:

function f1(N::Int)
    x = Array(Int, N)
    for n = 1:N
        x[n] = n
    end
    return(x)
end

function f2(N::Int)
    x = Array(Int, 0)
    for n = 1:N
        push!(x, n)
    end
    return(x)
end

f1(2)
f2(2)

N = 5000000000
@time f1(N)
@time f2(N)

表明使用push!比预分配慢大​​约6倍。如果您使用 append! 以更少的步骤添加更大的 block ，则乘数几乎肯定会更少。

在解释这些数字时，请抵制“什么!？慢了 6 倍!？”的下意识 react 。这个数字需要考虑到数组构建对于整个程序/函数/子例程的重要性。例如，如果数组构建仅占例程运行时间的 1%(对于大多数典型例程，数组构建将远少于 1%)，那么如果您的例程运行 100 秒，1秒用于构建数组。乘以 6 得到 6 秒。 99 秒 + 6 秒 = 105 秒。因此，使用 push! 而不是预分配会使整个程序的运行时间增加 5%。除非您从事高频交易，否则您可能不会关心这一点。

对于我自己来说，我通常的规则是:如果我可以轻松地预分配，那么我就会预分配。但是，如果 push! 使例程更容易编码，引入错误的可能性更低，并且在尝试预先确定适当的数组大小方面也更少困惑，那么我使用 push!不假思索地。

最后一点:如果您想实际了解 push! 工作原理的具体细节，您需要深入研究 C 例程，因为 julia source只是包装一个ccall。

更新: OP 在评论中质疑 push! 与 MATLAB 中的 array(end+1) = n 等操作之间的区别。我最近没有使用 MATLAB 进行编码，但我在我的机器上保留了一份副本，因为我所有旧论文的代码都在 MATLAB 中。我当前的版本是R2014a。我的理解是，在这个版本的 MATLAB 中，添加到数组末尾将重新分配整个数组。相比之下，据我所知，Julia 中的 push! 的工作方式与 .NET 中的列表非常相似。随着向量大小的增长，分配给向量的内存会按 block 动态添加。这大大减少了需要执行的重新分配的数量，尽管我的理解是一些重新分配仍然是必要的(我很高兴在这一点上得到纠正)。因此，push! 的工作速度应该比在 Matlab 中添加到数组要快得多。因此我们可以运行以下 MATLAB 代码:

N = 10000000;
tic
x = ones(N, 1);
for n = 1:N
    x(n) = n;
end
toc


N = 10000000;
tic
x = [];
for n = 1:N
    x(end+1) = n;
end
toc

我得到:

Elapsed time is 0.407288 seconds.
Elapsed time is 1.802845 seconds.

因此，速度减慢了大约 5 倍。鉴于计时方法中应用的极端不严格，人们可能会想说这相当于 Julia 的情况。但是等等，如果我们使用 N = 10000000 在 Julia 中重新运行该练习，则时间分别为 0.01 和 0.07 秒。这些数字与 MATLAB 数字之间的巨大差异让我非常紧张，无法对幕后实际发生的情况做出断言，以及将 MATLAB 中的 5 倍减速与 MATLAB 中的 6 倍减速进行比较是否合理。 Julia .基本上，我现在已经超出了我的能力范围。也许更了解 MATLAB 幕后实际功能的人可以提供更多见解。关于 Julia，我不是一个 C 程序员，因此我怀疑通过查看源代码(与 MATLAB 不同，它是公开的)我能否获得很多见解。