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

概述如何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

使用Console.Writeline（C＃）或printfn（F＃）编写粗体文本？

带有ToolStripStatusLabel的UIautomation

Powershell Get-Content + Invoke-Expression单独执行语句，还是一次执行所有语句？

使DataGrID单元只读

是否有.NET接口来编辑windows DNS服务器区域？

在.NET中编写虚拟打印机

分布式locking机制.NET

windows内存和页面文件的使用情况

控制从C＃应用程序的其他窗口

本地消息传递到windows上的.NET应用程序

您的列表已排序，您可以使用它来缩小问题空间。 不要搜索整个列表，而是搜索列表中的跨越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。 如果你发布了什么假设，我会更新问题的答案。

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

我不知道你的原代码在做什么。 我看到你已经定义了x和y ，从来没有使用它们，你指的是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内的所有点”

总结

以上是内存溢出为你收集整理的如何search列表的距离低于F到P的项目，而不search整个列表？全部内容，希望文章能够帮你解决如何search列表的距离低于F到P的项目，而不search整个列表？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。