Рассчитать расстояние между двумя целочисленными списками

Question

Я использую C #, и у меня есть два list<AACoordinate>, где каждый элемент в этих списках представляет трехмерную точку в пространстве по x, y и z.

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

Каждый список может содержать 2000 или более точек, и моя цель состоит в том, чтобы сравнить каждую точку списка1 со всеми точками списка2, и если расстояние меньше определенного числа, я веду его учет. на данный момент я использую 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) Вы строите свое kd-дерево для первого списка в O (n log n).Это должно быть сделано в одном потоке.

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, aбольшая разница!

Используя параллельный алгоритм, если у вас есть 4 процессора, нормальный алгоритм O (n * n) потребует 1000000 на процессор, и я думаю, что это будет слишком много, если вам нужно что-то быстроеили почти в режиме реального времени.

Answer 2

Если вы действительно хотите сравнить каждый элемент list1 с каждым из list2, вы не избавитесь от вложенного для.Но вы можете ускорить его, используя Parallel.ForEach .

Answer 3

Ваш текущий метод проверяет каждую упорядоченную пару в L x R, простой алгоритм O (n ^ 2).На ум приходит пара идей.

Сначала вы можете попробовать разбить каждый из двух массивов, скажем, на кубы стороны, равные вашему максимальному расстоянию;тогда вам нужно будет только вычислить расстояния между элементами в L и R, если они находятся на расстоянии не более 1 куба.Это все равно O (n ^ 2) в худшем случае, но если ваши точки в среднем намного дальше друг от друга, чем ваше максимальное расстояние, вы можете сэкономить на множестве ложных сравнений здесь.

Во-вторых, вы можетемикро-оптимизировать, как вы делаете функцию расстояния.Вам никогда не нужно использовать sqrt (), например;Сравнение квадрата расстояния с максимальным квадратом расстояния достаточно.Кроме того, вы можете избежать целочисленных умножений для получения квадрата расстояния, если сначала проверите, | dx |, | dy |или | дз |удовлетворить определенные свойства (т. е. они уже превышают максимальное расстояние).

Распараллеливание, как упоминалось другими авторами, всегда является хорошей ставкой.В частности, сложная стратегия распараллеливания + бокса (обрисованная в общих чертах в первом предложении) должна обеспечить особенно масштабируемое и эффективное решение.

Answer 4

Вы можете использовать параллельные библиотеки, где вы можете найти Parallel.ForEach . Пример Paralel