什么是向数组追加元素的最快方法？

Question

这是对如何在MATLAB中将元素添加到数组的进一步问题。该问题解决了如何向数组中添加元素的方法。那里讨论了两种方法：

A = [A elem]  % for a row array
A = [A; elem] % for a column array

并且

A(end+1) = elem;

第二种方法的明显优点是它与行和列数组都兼容。

然而，问题是：哪种方法更快？我的直觉告诉我第二个方法更快，但我想要一些证据来支持或反驳这一点。有什么想法吗？

- jub0bs

---

我刚刚看到了以下问题，其中一个答案涉及性能问题：https://dev59.com/ZWQo5IYBdhLWcg3wR9nD - jub0bs

Answer 1

第二种方法(A(end+1) = elem)更快

根据下面使用File Exchange的timeit基准测试函数运行的结果，第二种方法(A(end+1) = elem)更快，因此应该被优先选择。

有趣的是，在旧版本的MATLAB中，这两种方法之间的性能差距比它们在更近期的版本中要小得多。

R2008a

R2013a

测试代码

function benchmark

    n = logspace(2, 5, 40);
    % n = logspace(2, 4, 40); 
    tf = zeros(size(n));
    tg = tf;

    for k = 1 : numel(n)
        x = rand(round(n(k)), 1);

        f = @() append(x);
        tf(k) = timeit(f);

        g = @() addtoend(x);
        tg(k) = timeit(g);
    end

    figure
    hold on
    plot(n, tf, 'bo')
    plot(n, tg, 'ro')
    hold off
    xlabel('input size')
    ylabel('time (s)')
    leg = legend('y = [y, x(k)]', 'y(end + 1) = x(k)');
    set(leg, 'Location', 'NorthWest');
end

% Approach 1: y = [y, x(k)];
function y = append(x)
    y = [];
    for k = 1 : numel(x);
        y = [y, x(k)];
    end
end

% Approach 2: y(end + 1) = x(k);
function y = addtoend(x)
    y = [];
    for k = 1 : numel(x);
        y(end + 1) = x(k);
    end
end

- jub0bs

Answer 2

这个怎么样？

function somescript

RStime = timeit(@RowSlow)
CStime = timeit(@ColSlow)
RFtime = timeit(@RowFast)
CFtime = timeit(@ColFast)

function RowSlow

rng(1)

A = zeros(1,2);
for i = 1:1e5
    A = [A rand(1,1)];
end

end

function ColSlow

rng(1)

A = zeros(2,1);
for i = 1:1e5
    A = [A; rand(1,1)];
end

end

function RowFast

rng(1)

A = zeros(1,2);
for i = 1:1e5
    A(end+1) = rand(1,1);
end

end

function ColFast

rng(1)

A = zeros(2,1);
for i = 1:1e5
    A(end+1) = rand(1,1);
end

end

end

对于我的机器，这将产生以下时间：

RStime =

30.4064

CStime =

29.1075

RFtime =

0.3318

CFtime =

0.3351

向量的方向似乎并不那么重要，但第二种方法在我的计算机上快了约100倍。

- Wouter Kuijsters

---

你应该使用 timeit 而不是 tic/toc，因为后者并不是一种可靠的测量执行时间的方法。 - jub0bs

感谢您的建议。奇怪的是，对我来说速度仍然是一个约100倍的因素，而运行您的代码只能加快约6倍的速度。 - Wouter Kuijsters

嗯...奇怪。我会在我的机器上尝试运行你的基准测试，然后回报结果。无论如何，点个赞。 - jub0bs

@Jubobs：真的吗？那很奇怪，rng是控制rand、randi和randn输出的函数，也是Matlab的核心函数。我在我的（R2014b）代码中包含了它，以确保所有的计时都使用同一个随机向量。也许你使用的是旧版本的Matlab，该命令不可用，那么你可以在这里找到旧语法：http://nl.mathworks.com/help/matlab/math/updating-your-random-number-generator-syntax.html - Wouter Kuijsters

我只在MATLAB R2008a中运行了你的代码，可能那个功能还没有出现。我会尝试在更新的版本中再次运行。 - jub0bs

Answer 3

除了上述快速增长的方法（即A(k+1)），您还可以通过将数组大小增加多个来获得速度提升，以便随着大小的增加分配减少。

在我的笔记本电脑上使用R2014b，条件加倍大小大约可以获得6倍的速度提升：

>> SO

GATime =
    0.0288

DWNTime =
    0.0048

在实际应用中，A的大小需要限制在所需的大小范围内，或以某种方式过滤未填充的结果。

以下是“SO”函数的代码。我注意到我改用了“cos(k)”函数，因为在我的计算机上，“rand()”和“rand(1,1)”之间存在巨大的性能差异，原因未知。但我认为这不会对结果产生太大影响。请注意保留HTML标签。

function [] = SO()

    GATime  = timeit(@GrowAlways)
    DWNTime = timeit(@DoubleWhenNeeded)

end


function [] = DoubleWhenNeeded()

    A     = 0;
    sizeA = 1;
    for k = 1:1E5
        if ((k+1) > sizeA)
            A(2*sizeA) = 0;
            sizeA = 2*sizeA;
        end
        A(k+1) = cos(k);
    end

end

function [] = GrowAlways()

    A     = 0;
    for k = 1:1E5
        A(k+1) = cos(k);
    end

end

- TroyHaskin

---

没错，说得好（+1）。问题在于，有时候你只想添加一个元素，而不想用零填充。 - jub0bs

正确。在我看来，知道数组的最终大小是最佳实践。但由于问题是要求如何高效地增长数组，我认为数组的最终大小是未知的。我从观看一次讲座中学到了这种技术，该讲座讨论了Python如何在不知道数组大小的情况下以恒定时间增长列表。 - TroyHaskin