Matlab 预分配，猜测大矩阵还是小矩阵？

Question

根据这个问题，我应该尝试在Matlab中使用预分配。

现在我遇到一个情况，不能计算出要预分配的矩阵的确切大小，只能猜测大小。

假设实际矩阵大小为100，但我不知道它。那么哪种情况更有效：

1. 我应该慷慨一些吗？我猜测一个大矩阵，最后再删除多余的行。
2. 我应该吝啬一些吗？我猜测一个较小的大小，如果错了，再添加新的行。

谢谢。

- Ramin

Answer 1

依我之见，答案比@natan所描述的要复杂一些。我认为他的回答没有考虑到两个因素：

1.可能需要复制内存的副本：当你低估矩阵大小并重新分配它时，所有旧值都应该被复制到新分配的位置。

2.内存块的连续性：有时Matlab能够在旧矩阵的末尾连续分配新内存。原则上，在这种情况下，旧值不需要被复制到新位置——因为它与旧的一样，只是更大了。但是，如果你向二维矩阵添加行，则即使在这种情况下，内容也需要被复制，因为Matlab按行主序在内存中存储矩阵。

所以，我的答案是：

首先，你到底不知道矩阵的大小是什么：如果你知道一个维度——将它作为矩阵的行数，这样，如果你已经存储的数据需要被复制，它将被复制成更大的块。

其次，这取决于你可用的空闲RAM有多少。如果你的RAM不短缺，那么过度估计没有问题。

然而，如果你的RAM短缺，考虑低估。但是，当你重新分配时，每次迭代增加新块的大小。

BASIC_SIZE = X;  % first estimate
NEW_SIZE = Y;    % if need more, add this amount
factor = 2;      
arr = zeros( m, BASIC_SIZE ); % first allocation, assuming we know number of rows
while someCondition
    % process arr ...
    if needMoreCols
        arr(:, size(arr,2) + (1:NEW_SIZE) ) = 0; % allocate another block
        NEW_SIZE = round(NEW_SIZE * factor);  % it seems like we are off in estimation, try larger chunk next time factor should be > 1
    end
end
arr = arr(:, 1:actualNumOfCols ); % resize to actual size, discard unnecessary columns

- Shai

Answer 2

+1 对于这个有趣的问题。 编辑后的答案： 最初的一项小实验表明，晚些时候添加行似乎更好，但现在看来，在您拥有正确大小信息时再次进行预分配可能更有效率。我从矩阵大小为3000开始，并猜测大小估计的误差为10％，请参见下文：

    clear all
    clc
    guess_size=3000;
    m=zeros(guess_size);
    %1. oops overesrimated, take out rows
    tic
    m(end-300:end,:)=[];
    toc

    %1b. oops overesrimated,  preallocate again
    tic
    m=zeros(guess_size-300,guess_size);
    toc

    %2. oops overesrimated, take out cols
    m=zeros(guess_size);
    tic
    m(:,end-300:end)=[];
    toc

    %2b. oops overesrimated,  preallocate again
    m=zeros(guess_size);
    tic
    m=zeros(guess_size,guess_size-300);
    toc

    %3. oops underesrimated, add rows
    m=zeros(guess_size);
    tic
    m=zeros(guess_size+300,guess_size);
    toc

    %4. oops underesrimated, add cols
    m=zeros(guess_size);
    tic
    m=zeros(guess_size,guess_size+300);
    toc

Elapsed time is 0.041893 seconds.
Elapsed time is 0.026925 seconds.
Elapsed time is 0.041818 seconds.
Elapsed time is 0.023425 seconds.
Elapsed time is 0.027523 seconds.
Elapsed time is 0.029509 seconds.

选项2b和1b比低估略微快一些，因此如果可以的话，最好高估，然后重新预分配。从数组中删除行永远不是有效的。添加列似乎更有效率，但这只是一个快速而粗略的工作。请参见@Shai详细的答案以了解内部工作原理...

- bla

---

非常感谢您提供这么详细的答案，然而我认为它并没有考虑到一些因素，这些因素可能会产生重大影响。请查看我的回答以获得更多详细信息。 - Shai

你的实验只是分配了新的空间。它们没有考虑到Matlab需要将旧的小数据复制到新分配的空间的情况。新的分配应该像这样：m=cat(1, m, zeros(300,guess_size);（示例3）。 - Shai

Answer 3

除了其他教育性的回答外，简而言之：

1. 数组的大小相对较小（高达数千字节）-> 这并不重要。
2. 数组很大，但您并没有受到系统内存数量的限制 -> 进行过度估计。
3. 数组很大，并且您受到系统内存数量的限制 -> 做Shai建议的事情。

- Tal Darom