Discussion :

[timbrochier]

Bonjour,
J'ai dans mon code trois boucles imbriquée qui font ramer mon programme à mort, pour un truc pas si compliqué. Je me dit qu'il doit exister une façon plus intelligente de coder ça en utilisant mieux les subtilité de java concernant les arraylist, mais je ne maitrise pas...
voila le topo: j'ai une ArrayList "Pop" contenant des objet (disons "Po") ayant chacun a une coordonée spatiale x et y (Po.x et Po.y). il y a BEAUCOUP d'objets dans Pop (genre 120 000) ce que je veux, c'est connaitre pour chaque objet Po la distance qui le sépare du plus proche de ses voisins...
si ya des balaises en algorythme, ils n'aurons surement pas de mal à trouver mieux que moi : voir mon code ci dessous (j'espère que c'est compréhensible?)

merci aux éventuels courageux!!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    public void calculGREG() {
// recherche de la distance entre 2 individus contigus :         
        System.out.println("Gregarisme : calculating distances between individuals ...");
        double r_min;
        for (int p = 0; p < Pop.size(); p++) {
            Poissons Po = (Poissons) Pop.get(p);
            int nbre_voisins = 0;
            // Rayon minimum pour avoir un seul voisin :
            r_min = 0; //on le fixe a 0, puis on l'augmentera dans la boucle while jusqu'a ce qu'on trouve un voisin
            // nombre de voisins dans ce rayon r_min:
            while (nbre_voisins < 2) { 
                r_min = r_min + 0.1;
                nbre_voisins = 0;
                for (int v = 0; v < Pop.size(); v++) {
                    Poissons voisin_potentiel = (Poissons) Pop.get(v);
 
                        double Px = voisin_potentiel.x - Po.x;
                        double Py = voisin_potentiel.y - Po.y;
                        double rayonCarre = (Px * Px + Py * Py);
                        if (rayonCarre < r_min * r_min) {
                            nbre_voisins = nbre_voisins + 1;
                        }                    
                }
            }
            Po.DistVoisin_init = r_min;
            // fin de la recherche de dist entre indiv contigus
            //System.out.println("Po.DistVoisin_init   =" + Po.DistVoisin_init);
        }
    }

[Nil_ct]

Bonjour,

Ce sont des suggestions. Sans pouvoir faire tourner ton code, je ne garantis rien :
1- ne fait pas de déclaration de variables dans les boucles (enfin peut-être que la jvm corrige ça automatiquement)
2- un arrayList n'a d'interêt que si tu y insères/retires souvent des éléments. Sinon c'est vraiment plus lent qu'un array. A la limite (en dernier recours), je ferais une copie de l'arrayList dans un array (uniquement copie des pointeurs pas des objets Po), avant de lancer l'algo
3- je ne comprends pas pourquoi tu fais une boucle r_min... si tu veux la distance la plus courte ce n'est pas nécessaire (et ça t'enlève une bonne partie de l'itération)

Voilà, j'espère que c'est utile.

Nil

Edit : si tu veux deux voisins, mémorise deux minimums (pas besoin de r_min non plus)

[merill]

Tu peux utiliser un KD-tree, c'est fait pour la détection de collision entre objet.
Apres, je sais pas comment ca marche, tout ce que je sais c'est que tu construit ton arbre, tu fait un pre-processing et ensuite tu peux chercher dedans rapidement, en fonction de la position.

[timbrochier]

merci pour vos conseil,
pour le r_min : tu a 10 000 fois raisons, je sais pas ce que j'ai foutu la, c'était n'importe quoi effectivement!! en virant cette boucle inutile je gagne déja 30% de temps!

j'ai bien noté aussi le fait que les array sont beaucoup plus rapide,
et pour le KD-tree je connaissais pas, il faudra que j'explore ça aussi.

encore merci les gars,
Tim

[tchize_]

Salut,

les algorithmes de plus proches voisins, c'est toujours assez difficile à optimiser, car tout dépend de ton type de donnée.

Basiquement tu vas devoir toruver un moyen de comparer chaque PO à l'ensemble des autres. Tu as déjà correctement fait l'optimisation la plus basique, retire les sqrt

Maitenant, tu peux aussi modifier ton algo (si t'as assez de place mémoire) pour ne pas faire distance(x,y) et dans une autre itération distance (y,x):

soit POO tableau
soit DIST tableau (distances)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
mettre DIST à +infinity
pour x de 0 à taille POO-1
  pour y de x+1 à taille POO
    dist = distance carrée de (POO(x),(y))
    si dist < DIST(x), DIST(x) = dist
    si dist < DIST(y), DIST(y) = dist

C'est basique maistu gagne un peu de temps
Sinon, il y a quelque année, j'avais un ensemble de milliers de points dans un espace à N dimensions et pour chaque point, je devais trouver N points le plus proche possible qui 'entourent' ce point, autant te dire que les algo étaient tordu. Ca pourrais te servir, je suis parti de l'algorithme de Mc Names qui prétraitait les donnée dans une arbre d'axe principaux

Je me suis même fendu à l'époque d'expliquer sur wikipedia l'algo de mc names
http://fr.wikipedia.org/wiki/Principal_axis_tree

[timbrochier]

Merci pour le Wikipédia, c'est très intéressant.
Par ailleurs j'ai modifié mon algo comme tu le suggérais pour ne pas calculer deux fois les distances (x-y et y-x), c'est clair que ça fait gagner beaucoup de temps (genre 50%)

bon, mon code est désormais suffisamment rapide pour mes besoins, en tout cas tout ces commentaires étaient vraiment intéressants et utiles