在matlab中,预分配数组的替代方法是什么?[复制品]

你可以试试什么 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秒。

增加一个数组通常是一件不好的事情,至少如果你要做很多次。我们可以使用一些技巧。(我已经试过了所有的方法,如果你愿意的话,我会自动为你写一些工具。)

问题是与数组增长相关的时间是一个O(n^2)操作。它还会使您的内存碎片化,如果以后需要创建一个大型数组,则会给您留下潜在的问题。

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

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

有一个组合技巧,你可以做我喜欢的,但它需要一个工具来实现操作。我们的想法是创建包含10000个元素的单元。用零填充第一个块。然后使用矩阵索引在生成新元素时插入新元素。当然,矩阵索引很快。当该单元格空间不足时,将追加一个新的大单元格。然后在最后,将所有单元格关联在一起,小心地删除未使用的元素。

最后一个方案涉及到要附加的新单元元素相对较少,因此如果可能有数百万个附加步骤,那么总体来说效率最高。

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

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

在之前的一个问题中,我发布了 a similar solution 根据提议 @Jacob .

我后来比较了大多数可用选项的性能(总结如下 @woodchips 以上)。以下是我在机器上得到的结果:

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

您可以增加一个比阵列便宜得多的单元阵列,然后使用 cell2mat 要转换为数组(需要有两倍的内存,但如果有,这可能是最简单的方法)。

如果知道可以预先分配正确大小的单元格数组的像素数,请使用实际值数组(最多640个,但通常为2-5个)填充每个单元格,然后使用 Cy2Mad 把它转换成一个阵形。

如果你担心碎片,你可以 pack 在加载单元之后,该单元将对内存进行碎片整理(将所有内容都授权给磁盘,然后再次连续加载),然后再执行 Cy2Mad 转换。