c# - 如何在列表中搜索距离小于 F 到 P 的项目而不搜索整个列表？

Question

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

Item 1 (XZPos: 0,0)
Item 2 (XZPos: 0,1)
Item 3 (XZPos: 0,2)
...
Item 12 (XZPos: 1,0)
Item 13 (XZPos: 1,1)
Item 14 (XZPos: 1,2)
...
2.249.984 elements later
...

Now I have a point P (4,4) and I want a list of structs in the above list of every item closer to P than 5,66f. My algorithm searches every item in the list like this:

        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 秒，那就太好了。

谢谢你的帮助，亚历克斯

Answer 1

您的列表已排序，您可以使用它来缩小问题空间。不要搜索整个列表，而是搜索跨越 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。如果数据中的值范围很大，但要检查的距离很短，这将大大减少需要迭代的条目数。