c# - 计算两个整数列表之间的距离

Question

我正在使用 C#，我有两个 list<AACoordinate>其中，这些列表中的每个元素都代表 x、y 和 z 空间中的一个 3D 点。

 class AACoordinate
    {
        public  int ResiNumber { get; set; }
        public double x { get; set; }
        public double y { get; set; }
        public double z { get; set; }
    }

每个列表可以包含 2000 或更多点，我的目标是将 list1 的每个点与 list2 的所有点进行比较，如果距离小于特定数字，我会记录下来.目前我正在使用 foreach 将 list1 的每个元素与 list2 的所有元素进行比较。由于点数，这非常慢。您有什么建议可以让它更快吗？

我的循环是:

 foreach (var resiSet in Program.atomList1)
        {
            foreach (var res in Program.atomList2)
            {
                var dis = EuclideanDistance(resiSet, res);
                if (dis < 5)
                    temp1.Add(resiSet.ResiNumber); 
            }
        }

预先感谢您的帮助。

Answer 1

也许实现起来有点复杂，但我没有其他想法:

要降低计算复杂度，您可能必须使用一些数据结构，例如 KD-Tree 或 QuadTree。

您可以使用 KD 树进行最近邻搜索，而这正是您所需要的。

1) 你为 O(n log n) 中的第一个列表构建你的 kd 树。这必须在单个线程中完成。

2) 对于第二个列表中的每个项目，您在 kd 树中查找最近的邻居(距离您要查找的点最近的点)，时间复杂度为 O(m log n)。如果从当前点到最近找到的点的距离小于你的增量，你就有了。如果您愿意，可以使用多个线程执行此步骤。

所以最后算法的复杂度将是 O(max(n, m) * log n) 其中 n 是第一个列表中的项目数，m 是第二个列表中的项目数。

对于 KD 树，请参阅:

参见 http://home.wlu.edu/~levys/software/kd/在 Java 和 C# 中，这似乎是一个很好的实现。

参见 http://www.codeproject.com/KB/architecture/KDTree.aspx

四叉树，见:

参见 http://csharpquadtree.codeplex.com/

参见 http://www.codeproject.com/KB/recipes/QuadTree.aspx

当然，看看维基百科什么是四叉树和 kd 树

考虑 (2000 * log base 2(2000)) 大约是 21931.5

相反，2000*2000 是 4000000，差别很大!

使用并行算法，如果你有 4 个处理器，普通的 O(n*n) 算法将需要每个处理器 1000000，我想，如果你需要快速或几乎实时的东西，它仍然太多了。