Preallocation của mảng tế bào trong MATLAB

Question

Đây là một câu hỏi để hiểu một hành vi hơn là một vấn đề cụ thể.

Mathworks tuyên bố rằng số được lưu trữ liên tục, điều này làm cho sự hấp dẫn quan trọng. Đây không phải là trường hợp cho mảng ô.

Có phải chúng tương tự như vector hoặc mảng con trỏ trong C++ không? Điều này có nghĩa là prealocation không quá quan trọng vì một con trỏ bằng một nửa kích thước của một đôi (theo whos - nhưng chắc chắn là ở trên đâu đó để lưu trữ kiểu dữ liệu của mxArray).

Chạy mã này:

clear all 
n = 1e6; 

tic 
A = []; 
for i=1:n 
    A(end + 1) = 1; 
end 
fprintf('Numerical without preallocation %f s\n',toc) 

clear A 

tic 
A = zeros(1,n); 
for i=1:n 
    A(i) = 1; 
end 
fprintf('Numerical with preallocation %f s\n',toc) 

clear A 
tic 
A = cell(0); 
for i=1:n 
    A{end + 1} = 1; 
end 
fprintf('Cell without preallocation %f s\n',toc) 

tic 
A = cell(1,n); 
for i=1:n 
    A{i} = 1; 
end 
fprintf('Cell with preallocation %f s\n',toc) 

lợi nhuận: bằng số mà không preallocation 0,429240 s bằng số với preallocation 0,025236 s thoại di động mà không cần preallocation 4,960297 s di động với preallocation 0,554257 s

Không có bất ngờ dành cho các giá trị số. Nhưng tôi đã làm tôi ngạc nhiên vì chỉ chứa các con trỏ và không phải dữ liệu chính nó sẽ cần tái phân bổ. Nên (vì con trỏ nhỏ hơn một con số) dẫn đến sự khác biệt của < .2s. Chi phí này đến từ đâu?

Một câu hỏi có liên quan sẽ là, nếu tôi muốn tạo vùng chứa dữ liệu cho dữ liệu không đồng nhất trong Matlab (không thể lấy trước được vì kích thước cuối cùng không được biết trong phần đầu). Tôi nghĩ rằng các lớp học xử lý không tốt vì cũng có chi phí rất lớn.

đã mong muốn được học một cái gì đó

magu_

Edit: tôi đã cố gắng ra khỏi danh sách liên kết bởi Eitan T đề nghị nhưng tôi nghĩ rằng các chi phí từ matlab vẫn còn khá lớn. Tôi đã thử một cái gì đó với một mảng đôi như dữ liệu (rand (200000,1)).

tôi đã thực hiện một âm mưu nhỏ để minh họa:

mã cho đồ thị: (tôi đã sử dụng lớp dlnode từ Trang chủ của matlab như đã nêu trong bài trả lời)

D = rand (200000, 1);

s = linspace(10,20000,50); 
nC = zeros(50,1); 
nL = zeros(50,1); 

for i = 1:50 
a = cell(0); 

tic 
for ii = 1:s(i) 
    a{end + 1} = D; 
end 
nC(i) = toc; 

a = list([]); 

tic 
for ii = 1:s(i) 
    a.insertAfter(list(D)); 
end 
nL(i) = toc; 

end 

figure 
plot(s,nC,'r',s,nL,'g') 
xlabel('#iter') 
ylabel('time (s)') 
legend({'cell' 'list'}) 

Đừng làm cho tôi sai Tôi thích ý tưởng danh sách được liên kết, vì có khá linh hoạt, nhưng tôi nghĩ rằng chi phí có thể lớn.

Answer 1

Các mảng ô có gì đó tương tự như vectơ hoặc một mảng con trỏ trong C++ không?

Mảng di động cho phép lưu trữ dữ liệu các loại và kích cỡ khác nhau, nhưng mỗi ô cũng thêm phí trên không đổi 112 byte (xem this other answer of mine). Điều này là nhiều hơn một 8-byte đôi, và điều này là không đáng kể, đặc biệt là khi giao dịch với mảng tế bào lớn như trong ví dụ của bạn.

Giả sử rằng một mảng ô được triển khai như là một mảng liên tục của con trỏ, mỗi trỏ đến nội dung thực tế của ô.

Điều này có nghĩa là bạn có thể sửa đổi nội dung của từng ô riêng lẻ mà không thực sự thay đổi kích thước vùng chứa ô của ô. Tuy nhiên, điều này cũng có nghĩa là việc thêm các ô mới vào mảng ô yêu cầu phân bổ lưu trữ động và đây là lý do tại sao việc preallocating bộ nhớ cho một mảng ô cải thiện hiệu suất.

Một câu hỏi có liên quan sẽ là, nếu tôi muốn thực hiện một container dữ liệu cho dữ liệu không đồng nhất trong Matlab (preallocation là không thể vì kích thước cuối cùng vẫn chưa được biết ở phần đầu)

Không biết kích thước cuối cùng thực sự có thể là một vấn đề, nhưng bạn luôn có thể preallocate một mảng tế bào với kích thước tối đa được hỗ trợ cần thiết (nếu có), và loại bỏ các tế bào trống cuối cùng. Tôi cũng khuyên bạn nên xem xét implementing linked lists in MATLAB.