Preallocation hiệu quả mảng trong MATLAB

Question

Một trong những điều đầu tiên người ta học về lập trình hiệu quả trong MATLAB là tránh các mảng thay đổi kích thước động. Ví dụ tiêu chuẩn như sau.

N = 1000; 

% Method 0: Bad 
clear a 
for i=1:N 
    a(i) = cos(i); 
end 

% Method 1: Better 
clear a; a = zeros(N,1); 
for i=1:N 
    a(i) = cos(i) 
end 

Các 'Bad' biến thể ở đây đòi hỏi O (N^2) thời gian để chạy, vì nó phải phân bổ một mảng mới và sao chép các giá trị cũ tại mỗi lần lặp của vòng lặp.

Thực hành ưa thích của riêng tôi khi gỡ lỗi là phân bổ một mảng với NaN, khó gây nhầm lẫn hơn với giá trị hợp lệ hơn 0.

% Method 2: Easier to Debug 
clear a; a = NaN(N,1); 
for i=1:N 
    a(i) = cos(i) 
end 

Tuy nhiên, một ngây thơ nghĩ rằng một khi mã của chúng tôi là sửa lỗi, chúng tôi đang lãng phí thời gian bằng cách phân bổ một mảng và sau đó điền nó với 0 hoặc NaN. Như đã đề cập here, bạn có lẽ có thể tạo một mảng chưa được khởi tạo như sau

% Method 3 : Even Better? 
clear a; a(N,1) = 0; 
for i=1:N 
    a(i) = cos(i); 
end 

Tuy nhiên, trong các thử nghiệm của riêng tôi (MATLAB R2013a), tôi nhận thấy có sự khác biệt đáng kể giữa các phương pháp 1 và 3, trong khi phương pháp 2 mất nhiều thời gian hơn. Điều này cho thấy rằng MATLAB đã tránh việc khởi tạo một cách rõ ràng mảng thành 0 khi gọi a = zeros(N,1).

Vì vậy, tôi tò mò muốn biết

• cách tối ưu để preallocate một mảng (chưa được khởi tạo) trong MATLAB là gì? (Quan trọng nhất, mảng lớn)
• Điều này cũng có giữ trong Octave không?

Answer 1

Làm cách nào để Matlab quản lý việc phân bổ cho bạn?

clear a; 
for i=N:-1:1 
    a(i) = cos(i); 
end 

Sau đó, Matlab có thể phân bổ và lấp đầy mảng bằng bất kỳ thứ gì mà nó cho là tối ưu (có thể là không). Tuy nhiên, bạn không có lợi thế gỡ lỗi là NaNs.

Answer 2

Bài kiểm tra

Sử dụng Matlab 2013b I và một 3.6GHz Intel Xeon + 16GB RAM Tôi chạy đoạn code dưới đây để cấu hình. Tôi phân biệt 3 phương pháp và chỉ xem xét mảng 1D, tức là vectơ. Phương pháp 1 và 2 đã được thử nghiệm bằng cách sử dụng cả vectơ cột và vectơ hàng, tức là (n, 1) và (1, n).

Phương pháp 1 (M1R, M1C)

a = zeros(1,n); 

Phương pháp 2 M2R, M2C

a = NaN(1,n); 

Phương pháp 3 (M3)

a(n) = 0; 

Kết quả

Kết quả tính thời gian và số lượng phần tử đã được vẽ trên thang đo logarit trong hình thời gian1D.

Như đã trình bày phương pháp thứ ba có nhiệm vụ gần như không phụ thuộc vào kích thước vector trong khi người kia đều đặn tăng cho thấy một định nghĩa tiềm ẩn của vector.

Thảo luận

MatLab hiện rất nhiều tối ưu hóa mã sử dụng JIT (Just in time), ví dụ: mã tối ưu hóa trong thời gian chạy. Vì vậy, nó là một câu hỏi hợp lệ để đặt ra có hay không một phần của mã chạy nhanh hơn là do lập trình (luôn luôn giống nhau hay không được tối ưu hóa) hoặc do tối ưu hóa. Để kiểm tra tối ưu hóa này có thể được tắt bằng cách sử dụng tính năng ('tăng tốc', 'tắt'). Kết quả của chạy mã lại khá thú vị:

Nó được hiển thị mà bây giờ Phương pháp 1 là tối ưu, cho cả hàng và cột vectơ. Và phương pháp 3 hoạt động giống như các phương pháp khác trong bài kiểm tra đầu tiên.

Kết luận

Tối ưu hóa bộ nhớ trước khi phân bổ là vô ích và lãng phí thời gian kể từ Matlab sẽ tối ưu hóa cho bạn anyway.

Lưu ý rằng bộ nhớ nên được phân bổ trước nhưng cách bạn làm việc đó không quan trọng. Hiệu suất của bộ nhớ phân bổ trước phần lớn phụ thuộc vào việc trình biên dịch JIT của MatLab có chọn tối ưu hóa mã của bạn hay không. Điều này hoàn toàn phụ thuộc vào tất cả nội dung khác của tệp .m của bạn vì trình biên dịch xem xét các đoạn mã tại thời điểm đó và sau đó cố gắng tối ưu hóa (nó thậm chí có bộ nhớ để chạy tệp nhiều lần có thể dẫn đến việc thực thi thậm chí thấp hơn thời gian). Việc phân bổ trước bộ nhớ thường là một quá trình rất ngắn để xem xét hiệu năng so với tính toán được thực hiện sau đó

Trong bộ nhớ ý kiến ​​của tôi nên được phân bổ trước bằng cách sử dụng phương pháp 1 hoặc phương pháp 2 để duy trì mã có thể đọc được và sử dụng hàm mà MatLab giúp gợi ý vì đây là những khả năng được cải thiện nhất trong tương lai.

Mã sử ​​dụng

clear all 
clc 
feature('accel','on') 

number1D=30; 

nn1D=2.^(1:number1D); 

timings1D=zeros(5,number1D); 

for ii=1:length(nn1D); 
    n=nn1D(ii); 
    % 1D 
    tic 
    a = zeros(1,n); 
    a(randi(n,1))=1; 
    timings1D(1,ii)=toc; 
    fprintf('1D row vector method1 took: %f\n',timings1D(1,ii)) 
    clear a 

    tic 
    b = zeros(n,1); 
    b(randi(n,1))=1; 
    timings1D(2,ii)=toc; 
    fprintf('1D column vector method1 took: %f\n',timings1D(2,ii)) 
    clear b 

    tic 
    c = NaN(1,n); 
    c(randi(n,1))=1; 
    timings1D(3,ii)=toc; 
    fprintf('1D row vector method2 took: %f\n',timings1D(3,ii)) 
    clear c 

    tic 
    d = NaN(n,1); 
    d(randi(n,1))=1; 
    timings1D(4,ii)=toc; 
    fprintf('1D row vector method2 took: %f\n',timings1D(4,ii)) 
    clear d 

    tic 
    e(n) = 0; 
    e(randi(n,1))=1; 
    timings1D(5,ii)=toc; 
    fprintf('1D row vector method3 took: %f\n',timings1D(5,ii)) 
    clear e 
end 
logtimings1D = log10(timings1D); 
lognn1D=log10(nn1D); 
figure(1) 
clf() 
hold on 
plot(lognn1D,logtimings1D(1,:),'-k','LineWidth',2) 
plot(lognn1D,logtimings1D(2,:),'--k','LineWidth',2) 
plot(lognn1D,logtimings1D(3,:),'-.k','LineWidth',2) 
plot(lognn1D,logtimings1D(4,:),'-','Color',[0.6 0.6 0.6],'LineWidth',2) 
plot(lognn1D,logtimings1D(5,:),'--','Color',[0.6 0.6 0.6],'LineWidth',2) 
xlabel('Number of elements (log10[-])') 
ylabel('Timing of each method (log10[s])') 
legend('M1R','M1C','M2R','M2C','M3','Location','NW') 
title({'Various methods of pre-allocation in 1D','nr. of elements vs timing'}) 
hold off 

Note

Các dòng chứa c(randi(n,1))=1; không làm bất cứ điều gì ngoại trừ việc gán giá trị một cho một phần tử ngẫu nhiên trong mảng được phân bổ trước để mảng được sử dụng để thử thách trình biên dịch JIT một chút. Những dòng này không ảnh hưởng đáng kể đến đo lường phân bổ trước đáng kể, nghĩa là chúng không thể đo lường được và không ảnh hưởng đến thử nghiệm.