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

Question

在这个页面上写道，方法push!()和append!()非常高效。

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

即，如果已知最终数组的大小，是否仍然比预先分配数组或逐步扩展使用append!()/push!()一样高效？

现在考虑当一个人不知道最终数组的大小时。例如，将多个数组合并为1个大数组（称为A）。

实现这两种方式：

1. append!()每个数组都追加到未预先分配大小的A中。
2. 首先求出每个数组的尺寸，以找到合并后的数组A的最终尺寸。然后预先分配A并复制每个数组的内容。

在这种情况下哪种更有效？

- aberdysh

---

不知道julia-lang是什么，但你最好的选择就是预先分配内存并复制。因为无论如何都需要分配内存，而预先分配是最好的选择。当然，这适用于连续数组的情况... - Selçuk Cihan

强烈推荐你去了解Julia，尤其是如果你喜欢Python的话。 - aberdysh

请查看性能提示：http://docs.julialang.org/en/release-0.4/manual/performance-tips/#pre-allocating-outputs - amrods

他们没有提到append!()/push!()的基准测试。 - aberdysh

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！添加较大的块，则乘数几乎肯定会更少。

在解释这些数字时，要抵制“什么？6倍慢！”的本能反应。这个数字需要放在整个程序/函数/子例程中构建数组的重要性的背景下。例如，如果数组构建仅占您例程运行时间的1％（对于大多数典型例程，数组构建将远远少于1％），则如果例程运行100秒，则花费1秒钟构建数组。将其乘以6得到6秒。99秒+6秒=105秒。因此，使用push！而不是预分配将使您整个程序的运行时间增加5％。除非您从事高频交易，否则您可能不会关心。

对于我自己来说，我的通常规则是：如果可以轻松地预先分配空间，则进行预分配。但是，如果使用push！可以使程序编写更加容易，减少引入错误的可能性以及避免预先确定适当数组大小时出现的混乱，则毫不犹豫地使用push！。

最后注意：如果您想查看push！的具体工作原理，您需要深入了解C例程，因为julia source只是一个ccall的包装。

更新： 在评论中，OP质疑了push！和类似于array（end + 1）= n的MATLAB操作之间的区别。我最近没有编写MATLAB代码，但是我在我的计算机上保留了一份副本，因为所有旧论文的代码都是用MATLAB编写的。 我当前的版本是R2014a。 我的理解是，在这个版本的MATLAB中，向数组末尾添加元素将重新分配整个数组。相比之下，Julia中的push！，据我所知，像.NET中的列表一样工作。向向量分配的内存会随着向量大小的增长而动态地增加块。这大大减少了需要执行的重新分配量，尽管我理解仍然需要一些重新分配（我很乐意在这一点上进行更正）。因此，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中的5倍减速与Julia中的6倍减速进行比较感到非常紧张。基本上，我现在已经超出了我的能力范围。也许了解MATLAB在幕后实际做了什么的人可以提供更多洞见。关于Julia，我不是很擅长C编程，所以我怀疑通过查看源代码（与MATLAB不同，Julia的源代码是公开的）可以获得更多见解。

- Colin T Bowers

---

这似乎并不像他们所声称的“更高效”。 当我读到这篇文章时，我感到非常兴奋，认为他们以某种不同、更高效的方法处理内存分配/垃圾回收，而不是MathWorks的开发人员。但看起来，Julia的append!() / push!()方法比它的MATLAB等效方法更快的唯一原因是Julia本身的速度更快。 - aberdysh

上次我在Matlab中编码时，没有push!和append!的等效物。如果您想要扩展它，必须重新分配整个向量。不可否认，这是很久以前的事了。显然，这比push!慢得多。关于Matlab在这方面可能具有的任何新功能，我无法提供太多评论。但我仍然坚持我的原始说法：对于大多数实际问题，在数组构建中的6倍乘数几乎不会被注意到。 - Colin T Bowers

澄清一下，我指的是MATLAB中与Julia的push！()相当的语法是array（end + 1）= val。 我认为MATLAB对这种语法的支持已经存在了一段时间，而且确实会进行重新分配，但是您怎么知道Julia中的push！()或append!()不执行重新分配呢？ 这不是6倍开销背后的原因吗？ - aberdysh

太棒了！非常感谢！非常有帮助。 - aberdysh

Answer 2

push!总比向预分配数组中插入元素要慢，即使没有其他原因，也是因为push! (1) 像手动插入一样插入元素，(2) 增加数组的长度。当一个操作是两个操作的一部分时，两个操作不可能比一个操作更快。

然而，正如其他答案中指出的那样，差距通常并不大到需要担心。在内部（上次我检查代码时），Julia使用增长倍率为2的策略，这意味着您只需要进行log2(N)次重新分配。

如果您预先知道数组的大小，则可以通过使用sizehint!来消除重新分配。正如您可以轻松测试的那样，这并不能消除相对于向预分配数组中插入的性能惩罚，但它可以减少性能惩罚。

- tholy

---

严格来说，我认为push!插入新元素的方式并不是“就像手动插入一样”。我相信C++（可能也包括Julia）会将一个特殊指针存储在每个数组的最后一个元素的内存位置之后，而push!直接写入该内存位置。另一方面，通过例如arr[5] = 1向预初始化的数组中插入元素需要将指针指向arr的第一个元素，并加上5以获取所需写入位置的指针。因此，push!需要少进行一次指针算术运算... - tparker

当然，使用push!比手动插入元素的开销少是非常不太可能的，但逻辑上push!可以通过执行更少的指针算术操作而比手动插入更快。 - tparker

@tparker，请尝试在 push!(a, x) 和 store_at_end!(a, x) = (@inbounds a[end] = x; a) 上使用 @code_llvm。 - tholy

我不认为你的store_at_end!函数与问题有关。我同意手动将新元素附加到预分配数组的末尾比使用push!更快，但OP正在询问逐个构建预分配数组的一个元素，因此您通常会写入不是在数组末尾的元素，这需要使用指针算术，这就是我的评论的全部意义。您正确地指出，在标准Julia实现中，预分配速度更快，但这不是逻辑必然性。 - tparker