在MATLAB中预分配数组的替代方法是什么？

Question

可能重复:
MATLAB中的可扩展数据结构

所以在我目前的MATLAB脚本中,我有一个非常大的不确定大小的增长数组.目前我无能为力,因为如果我实际上预分配,它将需要比它应该需要的内存多很多倍的内存(最大可能的值是每像素640,但通常它是2的线上的东西5).

通常在这种情况下,我将使用C++中的向量或其他东西,它在给定容量方面呈指数级增长.但我认为Matlab中的矩阵开始碎片比目的驱动的C++向量快得多.

你们认为这是什么样的最佳选择？或者我应该坚持使用普通数组并希望顺序添加大约100k个元素会起作用吗？

提前致谢.

Answer 1

增加阵列通常是一件坏事,至少如果你多次这样做的话.可以使用一些技巧.(我已经尝试过所有这些,并且如果你愿意,可以自动为你编写工具.)

问题是与阵列增长相关的时间是O(N ^ 2)操作.如果您需要稍后创建一个大型数组,它也会使您的内存碎片化,从而使您遇到潜在问题.

一种方法是将数组预分配到某个固定大小,然后在超出数组大小时附加大块零.现在使用矩阵索引将新值插入现有数组中.我们的想法是在需要重新分配数组时将其大小加倍.这只会导致一些重新分配,但最终会附加很多你不需要填充的零.最后,您将转储无关和未使用的数组元素.

第二个技巧是使用单元阵列.每次要添加新元素或其块时,只需添加包含这些元素的新单元格.然后在最后,你做一个cell2mat操作.单元技巧的一个问题是它仍然是一个O(N ^ 2)操作,因为单元数组本身本质上是一个指针数组,并且当你追加新元素时必须重新分配指针列表.

你可以做我喜欢的组合技巧,但它需要一个工具来实现操作.我们的想法是创建包含10000个元素块的单元格.用零填充第一个块.然后使用矩阵索引在生成元素时插入新元素.矩阵索引当然很快.当您在该单元格中用完房间时,会附加一个新的大单元格.然后在最后,您将所有单元格连接在一起,小心地丢弃未使用的元素.

最后一种方案涉及相对较少的要附加的新单元元素,因此如果可能存在数百万个附加步骤,则总体上效率最高.

您可以在我多年来发布的多个文件交换提交中找到这些方法中的每一种.第一个可以找到grow_array,它在内部管理附加步骤,担心矩阵索引.

后来,我使用函数句柄或持久变量构建了最后一个方案来维护存储的信息.包含这些实现的工具可以找到growdata和growdata2.

Answer 2

您可以尝试std::vector在重新分配元素时做什么- 每次填满时其容量加倍,其摊销成本为O(1).

测试:

function test_MAT_vector

    LIM = 5e4;
    %%# Normal
    tic;
    A = zeros(1,1);
    for i = 1:LIM
        A(end+1) = i;
    end
    toc

    %%# std::vector clone
    tic;
    B = zeros(1,1);
    for i = 1:LIM
        if(i > numel(B))
            B = [B;zeros(numel(B),1)];
        end
        B(i) = i;
    end
    toc

end

输出:

经过的时间是3.489820秒.

经过时间为0.006710秒.

使用细胞

%%# cell
tic;
A = cell(1,1);
for i = 1:LIM
    A(end+1) = {i};
end
toc

经过的时间是2.740792秒.