Clear Filters
Clear Filters

Quickly find points in a vector bounded by another vector pair of different size

2 views (last 30 days)
My time vector "c" is a series of asynchronous events. Vectors "a" and "b" bound regions of time where a different event happens. I want to know which elements of "c" occur duing an event bounded by "a" and "b". The real calculation takes hours, so I am looking for any tricks people have to speed it up. I feel like this should be simple, but I am struggling with phrasing my Google searches correctly to find help.
Sample code is below, along with 4 "too slow" solutions that I attempted. I'm not looking for clever tricks that work with this exact data set (like MOD), but rather a general solution. Any speedups to the calculation that you can provide would be very much appreciated. Thanks!
EDIT: Removed transpose on input vectors and added noise to better verify solution validity.
%% Define Sample Data
% Need to find which "c" elements fall within some set of bounds defined by "a" and "b". Goal is
% to produce this answer as fast as possible (without running out of memory).
n = 75000; % NOTE: Actual size is >250,000. Reduced for speed & memory limits.
a = ( 0.3 : 1.0 : n); % NOTE: "a" and "b" are the same size and act as bounds. Do NOT take
b = ( 0.7 : 1.0 : n); % advantage of the uniform spacing; it is artificial for testing.
c = (-9.5 : 0.5 : n+10); % NOTE: "c" partially overlaps above, but is not the same size
% Added Noise for testing
a = a + rand(size(a));
b = b + rand(size(b));
c = c + rand(size(c));
%% Loop
tic;
d0 = NaN(size(c));
for n=1:numel(c)
d0(n) = any( c(n)>a & c(n)<b );
end
fprintf('For Loop: %g\n',toc()); % 8.06249
%% Array Fun
tic;
d1 = arrayfun((@(x) any(x>a & x<b)), c );
fprintf('Arrayfun: %g\n',toc()); % 8.54237
assert(isequal(d0,d1),'Delta Found');
%% Array Math
% NOTE: Not an option; using real data sizes will lead to out-of-memory
tic;
d2 = any( c>a.' & c<b.' );
fprintf('Array Math: %g\n',toc()); % 12.8263
assert(isequal(d0,d2),'Delta Found');
%% Combo: Loop with Array
tic;
n2 = 10;
d3 = NaN(size(c));
for n=1:n2:numel(c)
nTop = min(numel(d3),n+n2-1);
d3(n:nTop) = any( c(n:nTop)>a.' & c(n:nTop)<b.' );
end
fprintf('Loop with Array: %g\n',toc()); % 10.5251
assert(isequal(d0,d3),'Delta Found');
  2 Comments
Matt J
Matt J on 18 May 2023
Edited: Matt J on 18 May 2023
Are a(i) and b(i) always monotonic sequences? Are the [a(i), b(i)] intervals always non-overlapping?
Matthew Pepich
Matthew Pepich on 18 May 2023
Edited: Matthew Pepich on 18 May 2023
Yes, "a" and "b" are both monotonically increasing. Based on a quick look at the data, I don't think intervals can overlap. Fortunately I came up with a solution last night using interp1, and the solution tolerates (some) overlap. I did think of an overlap case it doesn't work with, but the gap between "a" and "b" is fairly stable so it wouldn't occur in my data set. I'll post my new version in the Answers section. Thanks for your response!

Sign in to comment.

Accepted Answer

Matthew Pepich
Matthew Pepich on 18 May 2023
Edited: Matthew Pepich on 18 May 2023
I found a solution last night by playing around with interp1. This is over a thousand times faster, reducing my runtime from hours to seconds. While a better solution may exist, this is good enough for my needs so I will probably close this question out.
%% Interpolation #2
tic;
iA = interp1(a,1:numel(a),c,'previous','extrap');
ii = ~isnan(iA); % Handle NaN points before 1st "a"
d5 = false(size(c));
% d5 = c>=a(iA)' & c<=b(iA)'; <-- Rechecking c>a(iA)' is redundant
d5(ii) = c(ii)<=b(iA(ii));
fprintf('Interpolation #2: %g\n',toc()); % 0.0048266
assert(isequal(d0,d5),'Delta Found');

More Answers (0)

Categories

Find more on MATLAB in Help Center and File Exchange

Products


Release

R2022a

Community Treasure Hunt

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

Start Hunting!