我知道这不是推荐的技术(预分配更好),但我对这种计时行为非常好奇;我很想知道在幕后可能发生了什么。
在我的脑海中,向数组添加一个元素可能会导致内存中出现几种不同的合理行为,具体取决于实现:(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');
malloc
实验来看到是否获得相同的对数行为。虽然大小加倍非常规律。-哦,等等,你是指OP的图表吗?每个增量都有一个复制,只是在某些特定大小上,复制操作比附近大小的复制操作需要更长时间。这是一种非常奇怪的行为! - Cris Luengostd::vector
的方式,而不仅仅依赖于这种malloc行为,因此(end+1)
会向已经分配的内存添加内容,直到达到容量限制时需要重新扩展它,但我还没有能够独立证实这一点。 - Andrew Janke