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

Question

可能重复： MATLAB中的可增长数据结构

所以在我当前的MATLAB脚本中，我有一个非常大的不确定大小的增长数组。目前我对它无能为力，因为如果我真的预先分配，它将需要比它应该需要的内存多很多倍(最大可能的值是每像素640个，但通常是2-5的范围)。

通常，在这种情况下，我会在C++或什么地方使用向量，在这里它与给定的容量成指数增长。但是我认为Matlab中的矩阵比目标驱动的C++向量更快地开始分解。

你们认为什么是最好的替代办法？或者，我应该坚持使用普通数组，并希望按顺序添加大约100 k元素就可以了？

提前谢谢。

Answer 1

您可以尝试一下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秒。

Answer 2

增长数组通常是一件坏事，至少如果你要做很多次的话。有几个窍门可以用。(我都试过了，如果你愿意的话，我会自动为你写一些工具。)

问题是与数组增长相关的时间是O(N^2)操作。它也倾向于分割您的内存，如果您以后需要创建一个大数组，就会留下潜在的问题。

一种方法是将数组预先分配到某个固定大小，然后在超过数组大小时追加大量的零块。现在使用矩阵索引将新值插入到现有数组中。这样做的目的是在需要重新分配数组时将数组的大小翻一番。这只会导致少量的重新分配，但最终可能会追加大量不需要填充的零。最后，转储无关的和未使用的数组元素。

第二个技巧是使用单元格数组。每次要追加新元素或其块时，只需将这些元素附加到新单元格中即可。最后，执行一个cell2mat操作。单元格技巧的一个问题是，它仍然是O(N^2)操作，因为单元格数组本身本质上是一个指针数组，在追加新元素时必须重新分配指针列表。

有一个组合技巧，您可以这样做，我喜欢，但它需要一个工具，以实现该操作。其想法是创建包含10000个元素块的单元格。用零填充第一个块。然后使用矩阵索引在生成新元素时插入它们。当然，矩阵索引是快速的。当你在那个牢房里的空间用完时，你会追加一个新的大牢房。最后，你把所有的细胞连在一起，小心地丢弃未使用的元素。

最后一个方案所涉及的新增单元元素相对较少，因此，如果可能有数百万个附加步骤，那么总体上是最有效的。

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

稍后，我构建了最后一个方案，使用函数句柄或持久变量来维护存储的信息。包含这些实现的工具被发现为生长数据与growdata2。

Answer 3

在前一个问题中，我已经将类似的解发布到了@Jacob提议的内容中。

后来，我比较了大多数可用选项的性能(上面的@木片很好地总结了这些选项)。这是我在我的机器上得到的结果：

NUM = 50000;

%%# ========== MINE: ~0.07sec ==========
tic
BLOCK_SIZE = 2000;                           %# initial & increment size
listSize = BLOCK_SIZE;                       %# current list capacity
list = zeros(listSize, 2);                   %# actual list
listPtr = 1;                                 %# pointer to last free position
for i=1:NUM
    %# push items on list
    list(listPtr,:) = [rand rand];           %# store new item
    listPtr = listPtr + 1;                   %# increment position pointer
    %# add new block of memory if needed
    if( listPtr+(BLOCK_SIZE/10) > listSize ) %# less than 10%*BLOCK_SIZE free
        listSize = listSize + BLOCK_SIZE;    %# add new BLOCK_SIZE slots
        list(listPtr+1:listSize,:) = 0;
    end
end
list(listPtr:end,:) = [];                    %# remove unused slots
toc

%%# ========== PREALLOCATION (matrix): ~0.05sec ==========
tic
list = zeros(NUM,2);
for i=1:NUM
    list(i,:) = [rand rand];
end
toc

%%# ========== PREALLOCATION (cell): ~1.1sec ==========
tic
list = cell(NUM,1);
for i=1:NUM
    list{i} = [rand rand];
end
list = vertcat( list{:} );
toc

%%# ============ NO-PREALLOCATION (grow cell): ~5sec ========
tic
list = {};
for i=1:NUM
    list{i} = [rand rand];
end
list = vertcat( list{:} );
toc

%%# ============ NO-PREALLOCATION (grow matrix): ~24sec ========
tic
list = [];
for i=1:NUM
    list(i,:) = [rand rand];
end
toc

%%# ========== GROWDATA (by John D'Errico): ~3.3sec =========
tic
growdata                             %# The initialization call
for i = 1:NUM
    growdata( [rand rand] )          %# push items
end
list = growdata;                     %# unpacking step
toc