PHP - 优化查找数组中的最近点
PHP - Optimize finding closest point in an Array
我创建了一个脚本,它获取了大量的点,然后根据有限的选定点数组在 3D-space 中找到最近的点。它很好用。然而,有时我会得到超过 200 万个点来与 256 个项目的数组进行比较,所以它超过 5.3 亿次计算! 这需要相当多的时间和精力(考虑到它会每分钟比较几次这样的东西)。
我有这样一组有限的 3D 坐标:
array (size=XXX)
0 => 10, 20, 30
1 => 200, 20, 13
2 => 36, 215, 150
3 => ...
4 => ...
... // this is limited to max 256 items
然后我有另一组非常大的随机 3D 坐标,其大小可以从 2,500 -> ~ 2,000,000 多个项目变化。基本上,我需要做的是遍历每个点并找到最近的点。为此,我使用欧氏距离:
sq((q1-p1)2 +(q2-p2)2+(q3-p3)2)
这给了我距离,我将它与当前最近的距离进行比较,如果更近,则替换最近的距离,否则继续下一组。
我一直在研究如何改变它,这样我就不用做那么多计算了。我一直在查看 Voronoi 图,然后可能将点放在该图中,然后查看它属于哪个部分。但是,我不知道如何在 PHP.
中实现这样的事情
知道如何优化它吗?
从臀部快速射门;-)
如果你不将每个点与其他点进行比较,你应该能够获得很好的加速。许多点可以跳过,因为如果您只看 x/y/z 坐标之一,它们已经很远了。
<?php
$coord = array(18,200,15);
$points = array(
array(10,20,30),
array(200,20,13),
array(36,215,150)
);
$closestPoint = $closestDistance= false;;
foreach($points as $point) {
list($x,$y,$z) = $point;
// Not compared yet, use first poit as closest
if($closestDistance === false) {
$closestPoint = $point;
$closestDistance = distance($x,$y,$z,$coord[0],$coord[1],$coord[2]);
continue;
}
// If distance in any direction (x/y/z) is bigger than closest distance so far: skip point
if(abs($coord[0] - $x) > $closestDistance) continue;
if(abs($coord[1] - $y) > $closestDistance) continue;
if(abs($coord[2] - $z) > $closestDistance) continue;
$newDistance = distance($x,$y,$z,$coord[0],$coord[1],$coord[2]);
if($newDistance < $closestDistance) {
$closestPoint = $point;
$closestDistance = distance($x,$y,$z,$coord[0],$coord[1],$coord[2]);
}
}
var_dump($closestPoint);
function distance($x1,$y1,$z1,$x2,$y2,$z2) {
return sqrt(pow($x1-$x2,2) + pow($y1 - $y2,2) + pow($z1 - $z2,2));
}
可在 http://sandbox.onlinephpfunctions.com/code/8cfda8e7cb4d69bf66afa83b2c6168956e63b51e
找到工作代码示例
我创建了一个脚本,它获取了大量的点,然后根据有限的选定点数组在 3D-space 中找到最近的点。它很好用。然而,有时我会得到超过 200 万个点来与 256 个项目的数组进行比较,所以它超过 5.3 亿次计算! 这需要相当多的时间和精力(考虑到它会每分钟比较几次这样的东西)。
我有这样一组有限的 3D 坐标:
array (size=XXX)
0 => 10, 20, 30
1 => 200, 20, 13
2 => 36, 215, 150
3 => ...
4 => ...
... // this is limited to max 256 items
然后我有另一组非常大的随机 3D 坐标,其大小可以从 2,500 -> ~ 2,000,000 多个项目变化。基本上,我需要做的是遍历每个点并找到最近的点。为此,我使用欧氏距离:
sq((q1-p1)2 +(q2-p2)2+(q3-p3)2)
这给了我距离,我将它与当前最近的距离进行比较,如果更近,则替换最近的距离,否则继续下一组。
我一直在研究如何改变它,这样我就不用做那么多计算了。我一直在查看 Voronoi 图,然后可能将点放在该图中,然后查看它属于哪个部分。但是,我不知道如何在 PHP.
中实现这样的事情知道如何优化它吗?
从臀部快速射门;-)
如果你不将每个点与其他点进行比较,你应该能够获得很好的加速。许多点可以跳过,因为如果您只看 x/y/z 坐标之一,它们已经很远了。
<?php
$coord = array(18,200,15);
$points = array(
array(10,20,30),
array(200,20,13),
array(36,215,150)
);
$closestPoint = $closestDistance= false;;
foreach($points as $point) {
list($x,$y,$z) = $point;
// Not compared yet, use first poit as closest
if($closestDistance === false) {
$closestPoint = $point;
$closestDistance = distance($x,$y,$z,$coord[0],$coord[1],$coord[2]);
continue;
}
// If distance in any direction (x/y/z) is bigger than closest distance so far: skip point
if(abs($coord[0] - $x) > $closestDistance) continue;
if(abs($coord[1] - $y) > $closestDistance) continue;
if(abs($coord[2] - $z) > $closestDistance) continue;
$newDistance = distance($x,$y,$z,$coord[0],$coord[1],$coord[2]);
if($newDistance < $closestDistance) {
$closestPoint = $point;
$closestDistance = distance($x,$y,$z,$coord[0],$coord[1],$coord[2]);
}
}
var_dump($closestPoint);
function distance($x1,$y1,$z1,$x2,$y2,$z2) {
return sqrt(pow($x1-$x2,2) + pow($y1 - $y2,2) + pow($z1 - $z2,2));
}
可在 http://sandbox.onlinephpfunctions.com/code/8cfda8e7cb4d69bf66afa83b2c6168956e63b51e
找到工作代码示例