MATLAB迭代地添加数组元素:时间行为

Question

所以我知道这不是推荐的技术(预分配更好),但我对这种计时行为非常好奇; 我很好奇底下会发生什么.

在我的脑海中,向数组中添加一个元素可能会在内存中产生几个不同的合理行为,具体取决于实现:(1)分摊,在链接列表中添加元素需要相同的时间来维护指针到最后一个元素,(2)它可能需要花费很长一段时间,然后预先分配足够的内存,比如,当前列表中的元素数量的两倍(如Java数组),(3)更聪明的东西比我能想到.

MATLAB似乎做了一些我不太满意的事情.偶尔出现峰值,成本似乎呈线性增长.它可能在做什么的任何猜测(或智能解释)？我平均模拟(我提交,可能会隐藏一些有趣的模式).

当您将一个元素迭代地添加到最初为空的列表的末尾时会发生这种情况.为什么线性增加？那些看似周期性的尖峰是否有一个很酷的原因？

我用来生成它的代码:

% for averaging over
num_averages = 100000;
% number of simulations
num_sims = 10000;
% the time it takes to add one more item, array
time_store = nan(num_sims, num_averages);

% averaging count
for i = 1:num_averages

    % an array that grows with every loop
    building_array = [];

    for j = 1:num_sims
        tic;
        building_array = [building_array 1];
        time_store(j, i) = toc;
    end
end

plot(mean(time_store, 2)); hold all;
xlabel('Element num'); ylabel('Time');

Answer 1

这真的很有趣!在非常规则的交织处存在峰值,并且曲线之间或多或少是平坦的.在每个峰值之后,该线上升了一点.整齐!我认为这与缓存行有关.您正在测量复制阵列的成本,这可能与读取和写入缓存行的成本有关.

如果你更换线

building_array = [building_array 1];

同

building_array(end+1) = 1;

那么你不会在每个迭代循环中复制数据,而是实际将一个元素附加到数组中.通过这种变化,我获得了一条大致平坦的线,在对数增加的距离(以及对数增加高度)的峰值,这与需要时加倍阵列大小的常识实现一致:

只是一些更多的解释:building_array = [building_array 1]创建新的数组,一个元素大于building_array,并复制building_array和1进去.然后将其分配给building_array.似乎MATLAB的JIT尚未针对此代码模式进行优化!