Удалить Close Points C# для большого набора данных

Question

Я работаю над проектом, где мне нужно получить большое количество записей (приложение 20K), каждый из которых представляет точку (x, y), которые находятся в десятичной точке , У меня есть объект Point и двойное значение 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 часа, чтобы проверить это (для 20К записи, которую я считаю, что смешно, есть ли способ сделать это с помощью рамки .NET до 4.5?

Answer 1

Вот несколько вещей, чтобы попробовать

1. Удалите Console.WriteLine заявления. Выведение 20K х 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);