performance - How to speed up this object comparison algorithm? -
this question has answer here:
consider matrix of dimension nx2, each row contains lower , upper bound of uniform pdf (i.e., probability density function).
i want count number of overlaps, overlap defined condition in 2 pdfs overlapping, e.g.:
- pdf1:
[2,5] - pdf2:
[3,6] - the 2 pdfs overlapping in interval
[3,5].
obviously, if 3 pdfs p1, p2 , p3 overlapping, count 3 overlaps: p1 vs. p2, p1 vs. p3, p2 vs. p3.
i created following matlab code counts overlaps:
for m = 1:n-1 k = m+1:n l1 = dataservice.getobjectcoordinate(m,1); l2 = dataservice.getobjectcoordinate(k,1); u1 = dataservice.getobjectcoordinate(m,2); u2 = dataservice.getobjectcoordinate(k,2); if (l1 <= l2 && l2 <= u1) || (l2 <= l1 && l1 <= u2) numoverlaps = numoverlaps + 1; end end end however, can imagine, goes o(n^2), reeeeeally bad when n big. started execution 3 hours ago n=10000 , still running.
may suggest way of reducing complexity of proposed algorithm, maybe excluding of comparisons priori?
thanks in advance.
i take comment left earlier. can in shorter amount of time. based on link provided rody , shoelzer, can use following code operation in under second
tic numintervals = 10000; ranges = sort(randi(100,[numintervals,2]),2); [vals,idx] = sort(ranges(:,1)); ranges = ranges(idx,:); overlaps = false(numintervals); = 1:numintervals temp = [ranges(:,1) <= ranges(i,2),ranges(:,1) >= ranges(i,1)]; overlaps(:,i) = logical(all(temp,2)); end overlaps = tril(overlaps,-1); toc ranges array of interval start , end points.
the purpose of lower triangle portion @ end remove duplicate pairs. if p1 overlaps p2 p2 overlap p1. remove fact p1 overlaps removing diagonal
do careful running large numbers, amount of storage uses fill ram, depending on amount have. tried keeping logical array in this, still adds fast.
you remove storage portion , save ton of time, have handle in each loop.
Comments
Post a Comment