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

Popular posts from this blog

html - How to style widget with post count different than without post count -

i have border below li elements in wordpress widget types appropriate. element inside set block gives them nice easy click full width. the problem, when choose option "show post count" when adding widget such categories or archives displays post count plain text after tag , because tag block pushes post number text line below. whether choose show post count or not show post count still gives exact same element identifyer example "widget_categories". how style post count not on next line still keep links non post count list items full width? here's example on sidebar www.bbmthemes.com/themes/modular/blog-standard/ in order solve problem need remove display:block; for ul.widgets ul a , add in it's place line-height: 33px; what going achieve have same visual effect. what going lose doing links going work on text , not on "box". the other way out of find post count coming , make changes this. example change text count i
Read more

How to remove text and logo OR add Overflow on Android ActionBar using AppCompat on API 8? -

have researched death , cannot find answer. i have actionbar using appcompat. supporting api v7 (api v8 do). actionbar works api v11. api < v11 has problem of removing icon (and feature) actionbar without supplying overflow. big picture have app logo, app title, , 3 icons squidging same actionbar on low end phone. trying make room! i happy 1 of 2 solutions. either: a method of getting overflow functionality can retrieved pull down. (preferred) method of removing icon , text actionbar below current xml api 11+: <resources> <!-- base application theme api 11+. theme replaces appbasetheme res/values/styles.xml on api 11+ devices. --> <style name="appbasetheme" parent="theme.appcompat.light.darkactionbar"> <item name="android:actionbarstyle">@style/liteactionbarstyle</item> <item name="actionbarstyle">@style/liteactionbarstyle</item> </st
Read more

javascript - storing input from prompt in array and displaying the array -

i want take the inputs user prompt, store input in array, , display it. want take 10 inputs user using for loop. have tried do-while shown below. var givennames = new array(); var pattern = /[\w\d]{1,}/ig; do{ var name = prompt("enter names. letters , digits accepted!\nentering empty field stops asking",""); if(name && name.match(pattern)){givennames.push(name);} } while(name != ""); function displaynames(){ if(givennames.length > 0){ document.getelementbyid("list").innerhtml = "<span style='color:navy;font- weight:bold;'>given names are:<\/span><br><br>" + givennames.join("<br><br>"); } else { document.getelementbyid("list").innerhtml = "<span style='color:navy;font-weight:bold;'>nothing has been given!<\/span>"; } } how replace for loop? var givennames = new array();
Read more