Calculer la distance entre deux listes de nombres entiers

Question

J'utilise C# et j'ai deux list<AACoordinate> où chaque élément de ces listes représente un point 3D dans l'espace par x, y et z.

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

Chaque liste peut contiennent 2000 ou plus et mon objectif est de comparer chaque point de la liste 1 à tous les points de la liste 2 et si la distance est inférieure à un nombre spécifique, j'en garde une trace. pour l'instant, j'utilise foreach pour comparer chaque élément de la liste1 à tous ceux de la liste2. Cette opération est assez lente en raison du nombre de points. Avez-vous une suggestion pour le rendre plus rapide ?

ma boucle est :

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

Merci d'avance pour votre aide.

Answer 1

C'est peut-être un peu compliqué à mettre en œuvre, mais je n'ai pas d'autre idée que celle-ci :

Pour réduire la complexité de calcul, vous devez probablement utiliser une structure de données comme KD-Tree ou QuadTree.

Vous pouvez utiliser un KD-Tree pour effectuer la recherche du plus proche voisin, et c'est ce dont vous avez besoin.

1) Vous construisez votre arbre kd pour la première liste en O(n log n). Ceci doit être fait dans un seul thread.

2) Pour chaque élément de votre deuxième liste, vous recherchez dans l'arbre kd le plus proche voisin (le point le plus proche du point que vous recherchez), en O(m log n). Si la distance entre le point actuel et le point le plus proche trouvé est inférieure à votre delta, vous l'avez. Si vous le souhaitez, vous pouvez effectuer cette étape en utilisant plusieurs threads.

Ainsi, à la fin, la complexité de l'algorithme sera O(max(n, m) * log n) où n est le nombre d'éléments dans la première liste, m est le nombre d'éléments dans la deuxième liste.

Pour les arbres KD, voir :

Ver http://home.wlu.edu/~levys/software/kd/ Cela semble être une bonne mise en œuvre, en Java et en C#.

Ver http://www.codeproject.com/KB/architecture/KDTree.aspx

Pour les arbres quadruples, voir :

Ver http://csharpquadtree.codeplex.com/

Ver http://www.codeproject.com/KB/recipes/QuadTree.aspx

Et bien sûr, regardez sur Wikipédia ce qu'est un quadtree et un kd-tree

Considérons que (2000 * log base 2(2000)) est environ 21931.5

Au lieu de cela, 2000*2000 est 4000000, une grande différence !

En utilisant un algorithme parallèle, si vous avez 4 processeurs, l'algorithme normal O(n*n) nécessitera 1000000 par processeur, et je suppose que ce sera encore trop si vous avez besoin de quelque chose de rapide ou presque en temps réel.

Answer 2

Vous pouvez utiliser les bibliothèques parallèles où vous pouvez trouver Parallèle.ForEach . Exemple de Paralel

Answer 3

Si vous voulez vraiment comparer chaque élément de la liste 1 avec chaque élément de la liste 2, vous ne vous débarrasserez pas des for imbriqués. Mais vous pouvez accélérer le processus en utilisant Parallèle.ForEach .

Answer 4

Votre méthode actuelle vérifie chaque paire ordonnée dans L x R, un algorithme simple O(n^2). Quelques idées me viennent à l'esprit.

Tout d'abord, vous pouvez essayer de diviser chacun des deux tableaux en, disons, des cubes de côté égal à votre distance maximale ; alors vous n'aurez à calculer les distances entre les éléments de L et R que s'ils ne sont pas éloignés de plus d'un cube. Cela reste O(n^2) dans le pire des cas, mais si vos points sont en moyenne beaucoup plus éloignés les uns des autres que votre distance maximale, vous pouvez économiser beaucoup de comparaisons inutiles.

Deuxièmement, vous pouvez micro-optimiser la façon dont vous réalisez la fonction de distance. Vous n'avez jamais besoin d'utiliser sqrt(), par exemple ; comparer la distance au carré à la distance maximale au carré est suffisant. De même, vous pouvez éviter d'effectuer des multiplications entières pour obtenir la distance au carré si vous vérifiez d'abord si |dx|, |dy| ou |dz| satisfont certaines propriétés (c'est-à-dire si elles sont déjà supérieures à la distance maximale).

La parallélisation, telle que mentionnée par les autres posters, est toujours un bon pari. En particulier, une stratégie sophistiquée de parallélisation + boxing (décrite dans la première suggestion) devrait constituer une solution particulièrement évolutive et efficace.