Quicker way to subtract large vectors using a sliding window?

2 views (last 30 days)
goc3
goc3 on 21 Jan 2022
Below is code with comments for two versions of vector subtraction using a sliding window. I got the math to work (first method for each version) and then was able to optimize it (second method for each version). However, I wonder if there is an even faster way to accomplish this sort of calculation, perhaps a vectorized method. I realize that this post is lengthy, but I figured that it would be helpful to clearly state the entire problem. Any suggestions or feedback are appreciated.
First, variables are initialized for both versions:
% initialize variables
rng(42);
nr = 100000;
A = rand(nr,1);
B = rand(nr,1);
w = 10; % window length
D1 = zeros(nr,1); % initialize results vector
D2 = zeros(nr,1); % initialize results vector
This is the first example, wherein a window slides over the first vector to perform subtraction at each value in the second vector, which results are then summed to populate the ith value. Two loop methods are presented and timing results are displayed on running the code.
%% Example 1: sliding window over one vector
%% First loop method
tic
for t_loop = 10; % is typically 1,000's to 1,000,000s for my application
for i = w:nr
D1(i) = sum(A((i-w+1):i) - B(i));
end
end
t1 = toc
t1 = 0.0473
%% Second loop method
tic
for t_loop = 10; % is typically 1,000's to 1,000,000s for my application
A_arr = zeros(nr,w);
for i = 1:w
A_arr(w:end,i) = A(i:(end-w+i));
end
D2 = sum( bsxfun(@minus, A_arr, B), 2);
D2(1:(w-1)) = 0; % mimic initialization in D1
end
t2 = toc
t2 = 0.0146
%% Check that the results are the same
assert(sum(abs(D1-D2)>1e-6)==0)
disp(['Method 2 is ',num2str(t1 / t2),' times faster than method 1.'])
Method 2 is 3.2295 times faster than method 1.
The second method is about faster than the first method (the amount varies each time I run it), which is very helpful when running thousands to millions of iterations for combinatoric studies. But, as stated above, I would like to know if this can be optimized further.
This is the second example, wherein windows slide over both vectors to perform similar subtractions.
%% Example 2: sliding window over both vectors
D1 = zeros(nr,1); % initialize results vector
D2 = zeros(nr,1); % initialize results vector
%% First loop method
tic
for i = w:nr
s = 0; % initialize sum for the window at each iteration
for j = 1:(w-1)
s = s + sum(A(i-j) - B((i-j+1):i));
end
D1(i) = s;
end
t1 = toc
t1 = 0.4423
%% Second loop method
tic
B_arr = zeros(nr,w-1);
for i = 1:(w-1)
B_arr_slice = zeros(nr-w+1,i);
for j = 1:i
B_arr_slice(1:end,j) = B((w-j+1):(end-j+1));
end
B_arr(w:end,i) = sum( bsxfun(@minus, A((w-i):(end-i)), B_arr_slice), 2);
end
D2 = sum(B_arr,2);
t2 = toc
t2 = 0.0433
%% Check that the results are the same
assert(sum(abs(D1-D2)>1e-6)==0)
disp(['Method 2 is ',num2str(t1 / t2),' times faster than method 1.'])
Method 2 is 10.2096 times faster than method 1.
This second method is much faster, as expected, given the improvement for the single-window case and that the sliding window operates over both vectors here.
However, as mentioned previously, these calculations are performed thousand or millions of times. Every additional optimization would be very helpful. And, I can't help but wonder if there is a faster and/or vectorized method of performing these calculations.

Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by