cumsum với giới hạn trên và dưới?

Question

Tôi muốn tìm một cách được vectorized để tính tổng tích lũy của một vectơ, nhưng với giới hạn trên và dưới.

Trong trường hợp của tôi, đầu vào chỉ chứa 1 và -1. Bạn có thể sử dụng giả định này trong câu trả lời của bạn. Tất nhiên, một giải pháp tổng quát hơn cũng được chào đón.

Ví dụ:

x  = [1 1 1 1 -1 -1 -1 -1 -1 -1]; 
upper = 3; 
lower = 0; 
s  = cumsum(x)     %// Ordinary cumsum. 
s = 
    1  2  3  4  3  2  1  0 -1 -2 

y  = cumsumlim(x, upper, lower) %// Cumsum with limits. 
y = 
    1  2  3  3  2  1  0  0  0  0 
       ^     ^
       |      | 
      upper limit    lower limit 

Khi tổng tích lũy đạt đến giới hạn trên (ít yếu tố thứ 3), nó sẽ không tăng nữa. Tương tự như vậy, khi tổng tích lũy đạt đến giới hạn dưới (ở phần tử thứ 7), thì nó sẽ không giảm nữa. Phiên bản cho vòng lặp sẽ giống như sau:

function y = cumsumlim(x, upper, lower) 

y = zeros(size(x)); 
y(1) = x(1); 

for i = 2 : numel(x) 
    y(i) = y(i-1) + x(i); 
    y(i) = min(y(i), upper); 
    y(i) = max(y(i), lower); 
end 

end 

Bạn có ý tưởng nào không?

Answer 1

Đây là một giải pháp phần mềm hackish, nhưng có lẽ đáng nói đến.

Bạn có thể thực hiện tổng bằng cách sử dụng loại dữ liệu số nguyên đã ký và khai thác các giới hạn vốn có của loại dữ liệu đó. Để làm việc này, đầu vào cần phải được chuyển đổi thành loại số nguyên đó và nhân với hệ số thích hợp và cần áp dụng số bù trừ ban đầu. Yếu tố và bù đắp được chọn làm chức năng của lower và upper. Sau cumsum, phép nhân và bù được hoàn tác để có được kết quả mong muốn.

Trong ví dụ của bạn, loại dữ liệu int8 đủ; và các yếu tố cần thiết và bù đắp là 85 và -128 tương ứng:

x = [1 1 1 1 -1 -1 -1 -1 -1 -1]; 
result = cumsum([-128 int8(x)*85]); %// integer sum, with factor and initial offset 
result = (double(result(2:end))+128)/85; %// undo factor and offset 

mang đến cho

result = 
    1  2  3  3  2  1  0  0  0  0 

Answer 2

Tôi sẽ không cung cấp cho bạn một cách vector hóa ma thuật để thực hiện việc này, nhưng tôi sẽ cung cấp cho bạn một số dữ liệu có thể giúp bạn tiếp tục công việc của mình.

Chức năng cumsumlim của bạn là rất nhanh!

tic 
for ii = 1:100 
    y = cumsumlim(x,3,0); 
end 
t = toc; 
disp(['Length of vector: ' num2str(numel(x))]) 
disp(['Total time for one execution: ' num2str(t*10), ' ms.']) 
Length of vector: 65000 
Total time for one execution: 1.7965 ms. 

Tôi thực sự nghi ngờ đây là nút cổ chai của bạn. Bạn đã thử profiling the code chưa?