MATLAB迭代添加数组元素的时序行为探究

Great question—this gets right to the heart of how MATLAB manages array memory, and it’s a perfect example of why preallocating arrays is so strongly recommended. Let’s break down the two key behaviors you’re seeing:

Linear Time Growth #

First, it’s critical to understand that MATLAB arrays are stored as contiguous blocks of memory—they’re not linked lists, so you can’t just tack on a new element at the end without checking for space. Every time you run building_array = [building_array 1], here’s what happens under the hood:

• MATLAB checks if there’s unused space immediately after the existing array (almost never the case in practice, especially with iterative appends).
• Since there isn’t enough space, it allocates a new, larger memory block to hold the expanded array.
• It copies all existing elements from the old array to the new block.
• It adds the new element to the end of the new block.
• It frees up the memory used by the old array.

As you add more elements, each copy operation has to move more data (1 element, then 2, then 3, ..., up to N elements). The total time to build an array of size N ends up being O(N²), which means the average time per append grows linearly with N—this is the steady upward trend in your plot.

Periodic Spikes #

The spikes come from MATLAB’s dynamic memory allocation strategy. MATLAB doesn’t resize the array every single time you add an element. Instead, when it needs to resize, it allocates extra space beyond what’s immediately needed (a "buffer") to reduce how often it has to perform the expensive copy operation.

• For small arrays, the buffer size might be just a few extra elements. So you’ll get a spike when you hit the end of the buffer, then several fast appends until you fill the new buffer, and another spike.
• As the array grows, MATLAB increases the size of the buffer (not by a fixed doubling like Java, but with a more adaptive rule). This means the time between spikes gets longer, but each spike becomes more pronounced because more elements need to be copied.

Your averaging across 100,000 simulations smooths out some of the jaggedness of individual runs, but the periodic pattern still shines through because the resizing behavior is consistent enough across runs.

Quick Note on Preallocation #

This is exactly why preallocating arrays with building_array = zeros(1, num_sims); is the recommended practice. When you preallocate, MATLAB allocates the entire contiguous block upfront, so every append is just a single write operation—no copying, no resizing, and you get a flat, O(N) time curve with no spikes.

Your Test Code (Formatted) #

% 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');

内容的提问来源于stack exchange，提问作者Peter Barrett Bryan