如何在不搜索整个列表的情况下在列表中搜索距离低于F到P的项目

本文关键字：列表 搜索 项目 距离 情况下 | 更新日期: 2023-09-27 17:54:53


我必须在结构列表中搜索XZPos更接近Vector2(或PointF(P的每个项目。该列表按XZPos的x和y排序。它看起来像这样：

项目1(XZPos:0,0(
项目2(XZPos:0,1(
项目3(XZPos:0,2(项目12(XZPos:1,0(
项目13(XZPos:1,1(
项目14(XZPo:1,2(

2.249.984个元素之后

现在我有一个点P(4,4(，并且我想要上面列表中的每个项目的结构列表，这些项目比5,66f更接近P。我的算法搜索列表中的每一项，如下所示：

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

我的问题是，方式需要太长时间才能完成，现在我正在寻找一种方法，在不搜索整个列表的情况下找到我要查找的字段。22秒的搜索是太长。如果有人能帮我把时间缩短到1到2秒，那就太好了。

感谢您的帮助，Alex

如何在不搜索整个列表的情况下在列表中搜索距离低于F到P的项目

您的列表已排序，您可以使用它来缩小问题空间。不要搜索整个列表，而是搜索列表中在5,66f内跨越x个值的子集，因为无论另一个坐标是什么，任何在一个坐标上比最大值更远的东西都会比你想要的更远。然后，如果你在列表中存储每个值的起始位置(即，在你的示例中，"0"元素从1开始，"1"元素从12开始(，你可以很快找到你关心的部分。因此，您可以迭代项目175839到226835，而不是迭代项目0到200万。

示例：

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[][]。如果两个数组的索引是包含在集合中的一个点，则该值为true。例如，如果该集是你在帖子中包含的六个点，那么points[0][1]将为true，points[0][3]将为false。

如果不满足这些假设，同样的想法仍然可以使用，但需要推特。如果你发布假设应该是什么，我会更新问题的答案。

一个不必满足的假设是，这些点接近于顺序。如果他们不这样做，那么当涉及到记忆时，这将是相当贪婪的。如果点不是(接近(连续的，可以进行更改，如果我的假设是错误的，可以再次发布不变量，我会更新。

我不知道您的原始代码在做什么。我看到你已经定义了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.Y - 4| >= 5.66。这将剩余子列表拆分为两个连续的子列表。抛出带有|point.Y - 4| >= 5.66的子列表。然后线性搜索剩余的子列表。

这个问题与此有关：

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

看看亚线性解。

也看看这个问题

哪个数据结构适合查询"；距离点p〃距离d内的所有点；

相关文章：