CODEWITHSUNDEEP
javascriptoptimization
Liam Bigelow
Liam Bigelow

Reputation: 799

How to efficiently check a list item with all other list items?

Is there any way to optimize this method of searching?

for (var i=0;i<dots.length;i++) {
        var blist = [];
        for (var n=0;n<dots.length;n++) {
            if (dots[n][1]>(dots[i][1]-90) 
            && dots[n][1]<(dots[i][1]+90) 
            && dots[n][2]>(dots[i][2]-90) 
            && dots[n][2]<(dots[i][2]+90)) {
                if (!(n === i)) blist.push(n);
            }
        }

dots[x][1] is the x-coordinate and dots[x][2] is the y-coordinate.

I have 1000 dots, and need to find the dots surrounding each dot, so that results in the

if (dots[n][1]>(dots[i][1]-90) 
&& dots[n][1]<(dots[i][1]+90) 
&& dots[n][2]>(dots[i][2]-90) 
&& dots[n][2]<(dots[i][2]+90))

Running a million times a second, so is there a way to optimize this?

Upvotes: 1

Views: 97

Answers (3)

Scott Sauyet
Scott Sauyet

Reputation: 50807

Here's a sketch of a solution. It may be the same idea TravisJ was suggesting, although that's not clear to me. It really is only a sketch, and would take significant code to implement.

If you partition your space into 90 unit x 90 unit sections, then a dot in a particular section can only be close enough to a dot in that section or to a dot in one of that section's eight neighbors. This could significantly reduce the number of pairs you have to compare. The cost, of course is algorithmic complexity:

  • First create a data structure to represent your grid sections. They can probably be represented just by top-left corners, since their heights and widths would be fixed at 90, except maybe at the trailing edges, where it probably wouldn't matter. Assuming a rectangular surface, each one could have three, five, or eight neighbors (corners, edges, inner sections respectively).
  • Loop through your dots, determining which section they live in. If your total grid starts at 0, this should be relatively straightforward, using some Math.floor(something / 90) operations.
  • For each section, run the loop above on itself and each of its neighbors to find the set of matches. You can use the shortened version of the loop from my earlier answer.
  • For a further optimization, you can also reduce the number of neighbors to check. If Section3,7 does a comparison with Section3,8, then there is no reason for Section3,8 to also do the comparison with Section3,7. So you check only a certain subset of the neighbors, say those whose x and y components of their section numbers are greater than or equal to their own.

I have not tested this, except in my head. It should work, but I have not tried to write any code. And the code would not be trivial. I don't think it's weeks of work, but it's not something to whip together in a few minutes either.

I believe it could significantly increase the speed, but that will depend upon how many matches there are, how many dots there are relative to the number of sections.

Upvotes: 0

Scott Sauyet
Scott Sauyet

Reputation: 50807

One way to cut your time in half would be not to double-check each pair:

for (var i = 0, len = dots.length; i < len - 1; i++) {
    var blist = [];
    for (var n = i + 1; n < len; n++) {
        if (dots[n][1]>(dots[i][1]-90) 
        && dots[n][1]<(dots[i][1]+90) 
        && dots[n][2]>(dots[i][2]-90) 
        && dots[n][2]<(dots[i][2]+90)) {
            blist.push(i);
            blist.push(n);
        }
    }
}

Note the change in loop boundaries. This allows me to check each pair only once and skip the (n === i) check.

I also cache dot.length, probably not a big deal, but worth doing for a tight loop.

Still, that should be an improvement of more than 50%. While that could help, it's not the orders of magnitude change that might be required for this sort of issue.

Upvotes: 0

Travis J
Travis J

Reputation: 82297

Perhaps try using a data structure for your dots like this

var Dot = function(){
 var x = 0;
 var y = 0;
 var Up;
 var Right;
 var Left;
 var Down;

 function init(xVal,yVal)
 {
  x = xVal;
  y = yVal;
 }

 function GetUp()
 {
  return Up;
 }

 function SetUp(UpDot)
 {
  Up = UpDot;
 }

 return 
 {
  init: init,
  GetUp: GetUp,
  SetUp: SetUp
 };
};

and then use it like this

var Dots = [];
var firstDot = new Dot();
Dots.push(firstDot);
var secondDot = new Dot();
secondDot.init(0,90);
secondDot.SetUp(firstDot);
Dots.push(secondDot);

Obviously, more would need to be added and configured to match your situation. However, what this would allow you to do was iterate through dots and then check weather there existed a near dot making the time O(n) instead of O(n^2) and thus saving you 900,000 checks.

Upvotes: 1

Related Questions