最优搜索在给定区域（web服务）

问题描述：

我有一种算法&性能问题与Java解决2D点。我收集了大量的2D点（假设其中大约有10万个点）。我想获得一组在搜索点SP（X_sp，Y_sp）周围给定区域中的那些，以便我想获得满足条件的点P（xy）：最优搜索在给定区域（web服务）

x是X_sp之间 - constValue和X_sp + constValue和Y是Y_sp之间 - constValue和Y_sp + constValue

为了让您的数字关系的想法，constValue会像2,5或10，和X，Y将范围在0到1000之间。它意味着是一个web服务，因此必须考虑到同时搜索许多不同点的可能性。

由于这些固定点（不改变由于计算或东西），我认为这将是最佳的，提供由X和另外一个分类对象之一名单，而是由Y.排序，那我就首先获取X范围内的点，然后使用引用从另一个列表中获取这些点的集合（按Y排序）。然后，我将通过Y缩小这个选择范围，并在结果中获得特定区域中的点。

我不知道Java的由内而外的，所以我想和你商量最优化的方法。我应该使用哪些对象来存储排序的点，以便快速搜索范围内的对象？或者，也许我必须为此任务实现我的自定义算法？另外，在存储数据库中的点时，SQL查询是否足够快以提供结果？或者，也许NoSQL dbs对此更好？

我要履行我自己的测试，但我正在寻找一个首发人选。

这太宽泛了。 – tnw

除非您对此问题的尝试解决方案有具体问题，否则此问题不适合SO。这不是免费的编码服务。 –

你在那里有一个问题陈述。首先找到一个优化的算法来完成任务，然后如果您需要帮助优化您的代码，请到这里。 – digidude

答

我可能会使用一个TreeMap<Integer, TreeSet<Integer>>，其中关键的地图是x协调和各x坐标，你有y坐标列表。然后，您可以使用floorEntry和ceilingEntry来查找在您的范围内的x坐标。然后，每TreeSet<Integer>组你，你可以使用ceiling和能得到相应的条目。

当然，这只是给你你的盒子（四角）的边界的坐标。但TreeSet也有一个subset，它会给你一个值的范围。你将不得不使用这两次;一次的x坐标列表（你可以使用地图的keySet方法按键）是你的范围之内，然后为每个x协调，是y坐标的范围之内。因此，伪代码将是排序是这样的：

List<Point> result = new ArrayList<>(); 
int lowerX = points.ceilingKey(x - c); 
int upperX = points.floorKey(x + c); 
for each x coordinate in points.entrySet().subset(lowerX, upperX) 
    TreeSet<Integer> yCoordinates = points.get(x); 
    lowerY = yCoordinates.ceiling(y - c); 
    upperY = yCoordinates.ceiling(y + c); 

    for each y coordinate in yCoordinates.subset(lowerY, upperY) 
     result.add(new Point(x, y))

我没有测试过这一点，所以有可能是一些错误或什么我已经错过了。让我知道，我会纠正答案。

的floor和ceiling电话是log(n)我相信 - 这是你得到的性能优势，因为如果你使用一个清单，这将是O(n)看这件事。

注：我不知道这是否是最高效的。 SO通常不是这样一个开放式问题的地方，所以你可能在其他地方有更多的运气。

最优搜索在给定区域（web服务）

相关推荐