My guess is in the first code, the intermediate result does have to be stored in memory. It can be in processor register or in the first level of cache. So even the operation is performed twice it is still faster.
I made an algo_3 & 4 that replace min by if, and they seem even faster.
N = 1e8;
B = rand(1,N);
R = rand(1,N);
tic;A = alg1( B, R, 1/3 );toc % Elapsed time is 0.819863 seconds.
tic;A= alg2( B, R, 1/3 );toc % Elapsed time is 0.852902 seconds.
tic;A= alg3( B, R, 1/3 );toc % Elapsed time is 0.619154 seconds.
tic;A= alg4( B, R, 1/3 );toc % Elapsed time is 0.564323 seconds.
function B = alg1( B, R, alpha )
% Fast computation of L1 distance transform
K = numel(B);
% forward pass
for k=2:K
B(k) = min( B(k), B(k-1) + alpha * (R(k) - R(k-1)));
end
% backward pass
for k=K-1:-1:1
B(k) = min( B(k), B(k+1) + alpha * (R(k+1) - R(k)));
end
end
function B = alg2( B, R, alpha )
% Fast computation of L1 distance transform
alphaRdiff = alpha*diff(R);
K = numel(B);
% forward pass
for k=2:K
B(k) = min( B(k), B(k-1) + alphaRdiff(k-1));
end
% backward pass
for k=K-1:-1:1
B(k) = min( B(k), B(k+1) + alphaRdiff(k));
end
end
function B = alg3( B, R, alpha )
% Fast computation of L1 distance transform
alphaRdiff = alpha*diff(R,1,2);
K = numel(B);
% forward pass
for k=2:K
C = B(k-1) + alphaRdiff(k-1);
if C < B(k)
B(k) = C;
end
end
% backward pass
for k=K-1:-1:1
C = B(k+1) + alphaRdiff(k);
if C < B(k)
B(k) = C;
end
end
end
function B = alg4( B, R, alpha )
K = numel(B);
% forward pass
for k=2:K
C = B(k-1) + alpha * (R(k) - R(k-1));
if C < B(k)
B(k) = C;
end
end
% backward pass
for k=K-1:-1:1
C = B(k+1) + alpha * (R(k+1) - R(k));
if C < B(k)
B(k) = C;
end
end
end
