1

有没有办法优化这种搜索方法？

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]是 x 坐标，dots[x][2]是 y 坐标。

我有 1000 个点，需要找到每个点周围的点，这样会导致

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))

每秒运行一百万次，有没有办法优化呢？

4

3 回答 3

1

也许尝试像这样为您的点使用数据结构

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
 };
};

然后像这样使用它

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

显然，需要添加和配置更多内容以匹配您的情况。但是，这将允许您做的是遍历点，然后检查天气是否存在一个附近的点，使时间 O(n) 而不是 O(n^2)，从而为您节省 900,000 次检查。

于 2012-12-11T00:27:50.550 回答
0

将时间减半的一种方法是不要仔细检查每一对：

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);
        }
    }
}

注意循环边界的变化。这使我可以只检查每对一次并跳过(n === i)检查。

我也缓存dot.length，可能没什么大不了的，但值得做一个紧密的循环。

不过，这应该是 50% 以上的改进。虽然这可能会有所帮助，但这并不是此类问题可能需要的数量级变化。

于 2012-12-11T12:15:52.777 回答
0

这是解决方案的草图。这可能与 TravisJ 提出的想法相同，尽管我不清楚。它实际上只是一个草图，并且需要大量代码来实现。

如果您将空间划分为 90 个单位 x 90 个单位的部分，则特定部分中的点只能与该部分中的一个点或该部分的八个邻居之一中的一个点足够接近。这可以显着减少您必须比较的对数。代价当然是算法复杂度：

  • 首先创建一个数据结构来表示您的网格部分。它们可能仅由左上角表示，因为它们的高度和宽度将固定为 90，除了可能在后缘处，这可能无关紧要。假设一个矩形表面，每个表面可以有三个、五个或八个邻居（分别是角、边缘、内部部分）。
  • 遍历您的点，确定它们所在的部分。如果您的总网格从 0 开始，这应该相对简单，使用一些Math.floor(something / 90)操作。
  • 对于每个部分，在其自身及其每个邻居上运行上面的循环以找到匹配集。您可以使用我之前回答中的循环的缩短版本。
  • 为了进一步优化，您还可以减少要检查的邻居数量。如果 Section3,7 与 Section3,8 进行比较，则 Section3,8 没有理由也与 Section3,7 进行比较。因此，您只检查邻居的某个子集，例如那些其部分编号的 x 和 y 分量大于或等于自己的邻居。

我没有测试过这个，除了在我的脑海里。它应该可以工作，但我没有尝试编写任何代码。并且代码不会是微不足道的。我认为这不是几周的工作，但也不是几分钟就能完成的事情。

我相信它可以显着提高速度，但这取决于有多少匹配，有多少点相对于部分的数量。

于 2012-12-12T13:40:29.923 回答