如何search列表的距离低于F到P的项目,而不search整个列表?

我必须searchXZPos更接近Vector2(或PointF) P每个项目的结构列表。 该列表是由XZPos的x和ysorting的。 它看起来像这样:

第1项(XZPos:0,0) 
第2项(XZPos:0,1)
第3项(XZPos:0,2)
...
第12项(XZPos:1,0)
项目13(XZPos:1,1)
第14项(XZPos:1,2)
...
2.249.984个元素
...

现在我有一个点P (4,4),我想在上面的列表中每个项目比P更接近5,66f的结构列表。 我的algorithm像这样search列表中的每个项目:

  List<Node> res = new List<Node>(); for (int i = 0; i < Map.Length; i++) { Vector2 xzpos = new Vector2(Map[i].X, Map[i].Z);//Map is the list containing 2.250.000 elements //neighbourlength = 5,66f in our example if ((xzpos - pos).Length() <= neighbourlength && xzpos != pos)//looking for every item except the item which is P itself, therefore checking whether "xzpos != pos" { res.Add(new Node() { XZPos = xzpos, /*Other fields*/ }); } } return res.ToArray(); 

我的问题是,它需要太长时间才能完成,现在我正在寻找一种方法来查找我正在寻找的字段,而不search整个列表。 22秒的search是太长 。 如果有人能帮我把它弄到1或2秒,那将是非常好的。

感谢您的帮助,Alex

您的列表已排序,您可以使用它来缩小问题空间。 不要搜索整个列表,而是搜索列表中的跨越566f内x值的子集,因为任何一个坐标上的最大值远远超过你想要的值,而不管其他的坐标值是多少。 然后,如果你存储了每个值在列表中的起始位置(即在你的例子中,“0”元素从1开始,“1”元素从12开始),你可以快速到达你关心的列表部分。 因此,不要遍历项目0到200万,而是可以迭代项目175839到226835。

例:

 The List 1: (0,1) 2: (0,2) 3: (1,0) 4: (1,1) 5: (2,1) 6: (2,3) 7: (3,1) 8: (3,5) 9: (4,2) 10: (4,5) 11: (5,1) 12: (5,2) 13: (6,1) 14: (6,2) 15: (6,3) 16: (7,1) 17: (7,2) Start Locations (0,1) (1,3) (2,5) (3,7) (4,9) (5,11) (6,13) (7,16) 

如果我有一个点(3,5),我想在列表中搜索其中的2个点,我只需要遍历x在1和5之间的点。所以我看我的开始位置,看看1从列表中的位置3开始,5结束于位置(13-1)。 因此,不是从1到17迭代,我只需要从3到12进行迭代。如果数据中的值范围很大,但检查的距离很短,这将减少需要大量迭代的条目数。

下面的解决方案有一些假设。 这些假设没有在您的问题中说明,解决方案可能需要调整。 如果假设持有这个解决方案是非常快的,但要求你保持在不同的结构的数据。 但是,如果你可以改变结构,那么这将在(几乎)恒定的时间看看每个有效的点。 那就是在一个包含M个点的集合中找到M个有效点的时间总和只取决于N.

假设是:

  • 只有正整数用于X和Y的值
  • 在列表中没有重复的点

`private IEnumerable> GetPointsByDistance(int xOrigin,int yOrigin,double maxDistance){

  var maxDist = (int) Math.Floor(maxDistance); //Find the lowest possible value for X var minX = Math.Min(0, xOrigin - maxDist); //Find the highest possible value for X var maxX = Math.Min(MaxX, xOrigin + maxDist); for (var x = minX; x <= maxX; ++x){ //Get the possible values for Y with the current X var ys = points[x]; if (ys.Length > 0){ //Calculate the max delta for Y var maxYDist =(int)Math.Floor(Math.Sqrt(maxDistance*maxDistance - x*x)); //Find the lowest possible Y for the current X var minY = Math.Min(0, yOrigin - maxYDist); //Find the highest possible Y for the current X var maxY = Math.Min(ys.Length, yOrigin + maxYDist); for (var y = minY; y <= maxY; ++y){ //The value in the array will be true if a point with the combination (x,y,) exists if (ys[y]){ yield return new KeyValuePair<int, int>(x, y); } } } } }` 

这个代码中的点的内部表示是bool[][] 。 如果两个数组的索引是包含在集合中的一个点,则该值将为真。 例如,如果集合是包含在帖子中的六个点,并且点[0] [3]将是假的,则点[0] [1]将是正确的。

如果这些假设没有得到满足,那么仍然可以使用相同的想法,但是需要使用tweeking。 如果你发布了什么假设,我会更新问题的答案。

一个不需要满足的假设是这些点是接近顺序的。 如果不是这样的话,记忆就会相当贪婪。 如果点不是(靠近)连续的,可以做出改变,如果我的假设是错误的,我会更新不变量。

我不知道你的原代码在做什么。 我看到你已经定义了xy ,从来没有使用它们,你指的是pos但没有定义。 所以,相反,我要对你想要解决的问题进行口头描述

现在我有一个点P (4,4) ,我想在上面的列表中每个项目比P更接近5,66f的结构列表。

并解决它。 这很容易:

 var nearbyNeighbors = Map.Where( point => (point.X - 4) * (point.X - 4) + (point.Z - 4) * (point.Z - 4) < 5.66f * 5.66f ); foreach(var nearbyNeighbor in nearbyNeighbors) { // do something with nearbyNeighbor } 

在这里,我假设你正在使用标准的欧几里得规范。

为了利用集合按照字典顺序排序的事实:

二进制搜索直到|point.X - 4| >= 5.66 |point.X - 4| >= 5.66 。 这将列表分成两个连续的子列表。 用|point.X - 4| >= 5.66抛出子列表 |point.X - 4| >= 5.66 。 从剩下的子列表中,二进制搜索直到|point.Y - 4| >= 5.66 |point.Y - 4| >= 5.66这将剩余的子列表分成两个连续的子列表。 用|point.Y - 4| >= 5.66抛出子列表 |point.Y - 4| >= 5.66 。 然后线性搜索剩下的子列表。

这个问题与此有关:

http://en.wikipedia.org/wiki/Nearest_neighbor_search

看看亚线性解决方案。

也看看这个问题

该数据结构适合于查询“从点p起的距离d内的所有点”