function vec = testfun2(vec, threshold)
idx = 1;
n = length(vec);
keep = false(1, n);
while ~isempty(idx)
keep(idx) = true;
iThresh = vec(idx) + threshold;
idx = find(vec > iThresh, 1);
end
vec = vec(keep);
[EDITED, 2017-02-17 08:24 UTC]:
A version which runs in linear time:
function vec = testfun3(vec, threshold)
n = length(vec);
keep = false(1, n);
lim = vec(1) + threshold;
keep(1) = true;
for k = 2:n
if vec(k) > lim
keep(k) = true;
lim = vec(k) + threshold;
end
end
vec = vec(keep);
Timings under R2016b/64:
numval = 1e5;
threshold = 25;
vec = sort(rand(numval,1).*numval*1e2);
tic; r1 = testfun(vec, threshold); toc
tic; r2 = testfun2(vec, threshold); toc
tic; r3 = testfun3(vec, threshold); toc
isequal(r1, r2, r3)
Elapsed time is 44.117896 seconds.
Elapsed time is 10.090938 seconds.
Elapsed time is 0.003627 seconds.
1
Whoooops.
Could you please cross-check this? A speedup of factor 12000 usually means, that something important has been overseen.
Best Answer