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

Question

在这个页面上,它说方法push!()并且append!()非常有效.

我的问题是它们的效率如何？

也就是说,

如果有人知道最终数组的大小,那么预先分配数组还是使用append!()/ 增量增长它push!()会更快吗？

现在考虑一个人不知道最终数组大小的情况.例如,将多个数组合并为一个大数组(称之为A).

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

1. append!()-ing每个数组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!较少的步骤添加较大的块,则乘数几乎肯定会更少.

在解释这些数字时,抵制"什么!？慢6倍!？"的下意识反应.这个数字需要放在数组构建对整个程序/函数/子程序的重要性的上下文中.例如,如果阵列建筑物包括只有1%的你的程序的运行时(对于大多数典型例程,阵列建筑物将包括许多小于1%),然后,如果您的100秒例程运行,1秒花费建筑物阵列.乘以6得到6秒.99秒+6秒= 105秒.因此,使用push!而不是预分配会使整个程序的运行时间增加5%.除非你在高频交易中工作,否则你可能不会关心这一点.

对我自己来说,我通常的规则就是这样:如果我可以轻松预先分配,那么我就预先分配了.但是,如果push!使例程更容易编码,引入错误的可能性更低,并且更少考虑预先确定适当的数组大小,那么我就push!不用再考虑了.

最后的注意事项:如果你想真正了解工作方式的具体细节push!,你需要深入研究C例程,因为julia源代码只包含了一个ccall.

更新: OP在评论中质疑push!和array(end+1) = nMATLAB 之间的差异.我最近没有在MATLAB中编码,但是我在我的机器上保留了一份副本,因为我所有旧论文的代码都在MATLAB中.我目前的版本是R2014a.我的理解是,在这个版本的MATLAB中,添加到数组的末尾将重新分配整个数组.相比之下,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倍.鉴于时序方法中存在极端的非严格性,人们可能会倾向于说这相当于朱莉娅案例.但是等一下,如果我们在朱莉娅重新进行练习N = 10000000,时间是0.01和0.07秒.这些数字的大小与MATLAB数字的巨大差异让我非常担心会对实际发生的事情做出声明,以及将MATLAB中的5倍减速与6倍减速进行比较是否合理.朱莉娅.基本上,我现在已经超出了我的深度.也许有人更了解MATLAB实际上做了什么,可以提供更多的见解.关于朱莉娅,我不是一个C编码器,所以我怀疑通过查看源代码可以获得更多的洞察力(与MATLAB不同,这是公开的).

Answer 2

push!如果没有其他原因push!(1)插入元素,就像手动操作一样,并且(2)增加数组的长度,则总是比插入预先分配的数组慢.当一个是两个操作的一部分时,两个操作不能快于一个.

然而,正如其他答案中所指出的那样,差距通常不会大到需要关注的事情.在内部(上次检查代码时),Julia使用了一个2因子增长策略,因此您只需要log2(N)重新分配.

如果您事先知道数组的大小,则可以通过使用来消除重新分配sizehint!.由于您可以轻松地自行测试,这并不能消除相对于插入预分配阵列的性能损失,但它可以减少它.