arrays - MATLAB迭代添加数组元素: time behavior

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 还没有针对这个 Code Pattern 进行优化!