c# - 删除大数据集的关闭点 C#

Question

我正在做一个项目，我必须收到大量记录(大约 20K)，每条记录代表一个小数点 (x,y)。 我有 Point 对象和一个 double 值 m = user input 我需要消除所有比 m 更近的点，例如如果 m = 0.1 和 p1 = {1.21,1.32}, p2 = {1.21,1.31} p3 = {1.20, 1.32} p4 = {1.55, 1.31} 我需要消除 p2、p3(接近 p1 的点)但我会保留 p4，因为它与任何其他点的距离都大于 0.1。

我实现了一个算法，但是检查它需要 3 个多小时(对于 20K 的记录，我认为这很荒谬，有没有办法使用 .NET 框架 4.5 来做到这一点？

Answer 1

这里有一些尝试

1. 删除 Console.WriteLine声明。将 20K x 20K = 400M 行输出到控制台，这本身就需要数小时，即使程序什么都不做。如果您绝对必须保留某种输出，可以通过 outputting to the same line instead of scrolling 节省大量处理时间。 .

2. 考虑在遍历列表之前对列表进行排序，并修改循环，以便您只需要比较已排序列表中彼此靠近的项目。例如，如果您按 Y 排序，您的外部循环将保持不变，但您可以替换内部 for带有 while (full[j].Y < full[i].Y + maxVal) 的语句.一旦到达列表的某个部分，其中 maxVal 内可能没有任何元素，您可以退出内部循环并转到下一个值 i。 .这会将您的性能配置文件从 O(N^2) 更改为 O(N)... 更好。

3. 如果您不需要超过七位有效数字，请考虑使用 float而不是 double ，这将大大加快数学计算速度。

4. 考虑为 duplicated 预分配内存.每当该列表超出其分配的大小时，.NET 将不得不分配一个新列表(可能触发垃圾收集)并从旧列表中复制所有字节。您可以使用这种语法预分配空间:

   var list = new List<Point>(20000);