Discussion :

[comode]

Bonjour,

Imaginons une population d'éléments quelconques caractérisés par leurs identifiant unique et leurs coordonnées X et Y (non bornée).

Selon vous, quel serait la meilleur méthode pour déterminer (le plus rapidement possible) quels sont tous les éléments situés à une distance maximale x d'un élément donnée...

Alors évidemment, il existe la méthode fort peu subtile consistant à parcourir l'ensemble des éléments et récupérer ceux répondant à la formule :

x² < (Xelement2 -Xelement1)² + (Yelement2 - Yelement1)²

ce qui vous en conviendrez ne peut pas être utilisé sur un trop grand nombre d'éléments appelant eux même souvent cet algo...

Notez que la question n'est pas posé à titre de demande d'aide mais plutôt comme un défi... La structure de donnée utile pour stocker la liste de tous les éléments n'est donc pas imposée, et il est possible d'utiliser des arbres binaires, des tableaux hashés ou non, des liste chainées ou n'importe quoi d'autre, le tout étant de faire l'algo le plus rapide possible.

[Graffito]

il existe la méthode fort peu subtile ....

Ben, moi elle me plait bien, y'a vraiment pas grand chose à gagner à optimiser en éliminant par exemple les points tels que :
(Abs(Xelement2 -Xelement1)>x) OU (Abs(Yelement2 -Yelement1)>x)
d'ailleurs si la grande majorité des points sont concentrés dans un petit rayon, cette "optimisation" serait pénalisante.

[comode]

oui mais non... Cette méthode serait parfaitement inutilisable au delà d'un millier d'éléments a qui on demanderais de faire l'opération 2 ou 3 fois / secondes... Je donnais cet algo à titre d'exemple, mais c'est parfaitement irrecevable !

Perso, je pense à l'optimisation par un arbre binaire... Je découperai la surface sur laquelle se positionnent ces éléments en parcelles, et je stockerai les coordonnées X et Y de début de chaque parcelles dans 2 arbres binaires différents (1 arbre pour X, un arbre pour Y)... Ensuite, a chaque feuille de mes arbres binaires, j'associerai un tableau dynamique référençant les éléments dont la coordonnée concernée se situerai dans l'intervalle définie par cette feuille...

Ensuite, j'ai plus qu'a faire un algo de parcours de l'arbre pour récupérer les feuilles voisines (ce qui prendra une poignée d'instructions) contenant donc les références des éléments ayant des coordonnées voisines à la mienne. J'ai plus qu'a faire l'union des feuilles retournées par les arbres X et Y pour trouver tous les voisins, et appliquer ensuite l'ago sus-cité pour affiner mon résultat, et économiser des millions d'opérations par seconde.

Maintenant, la méthode est peut être plus délicate à mettre en oeuvre sur une surface non bornée, mais c'est le style de réponse que je m'attend à recevoir.

[Graffito]

Cette méthode serait parfaitement inutilisable au delà d'un millier d'éléments a qui on demanderais de faire l'opération 2 ou 3 fois / secondes...

Là, ca devient plus intéressant comme problème, puiqu'on a peut-être avantage à pré-traiter l'ensemble des éléments ou chaque élément quand on l'insère.
La solution dépendra :
- du nombre d'éléments total,
- du nombre d'éléments à traiter,
- du fait que la collection d'éléments soit variable ou fixe,
- et si la collection est variable, du taux de variation.

[comode]

éléments total : plusieurs dizaines de milliers
a traiter : tous et de façon désordonnée en temps et en ordre
collection variable dans le temps et l'espace (les éléments se déplacent et peuvent apparaitre ou disparaitre)
taux de variation faible en quantité, très importante en coordonnées

bref, un algo qu'on pourrait par exemple appliquer à une colonie de fourmis communiquant entre elles... Mais comme je disais, c'est pas une question posée dans le cadre d'un projet concret. Je le développerai surement pour le plaisir ensuite.

[Obsidian]

Le seul moyen d'optimiser un tel problème est de pouvoir trier les éléments selon un critère donné, voire les obtenir déjà triés et tâcher de maintenir cet ordre tout au long du traitement.

Dans le cas contraire, tu es obligé de tous te les palucher, pour la simple et bonne raison que tu ne peux déduire aucune information concernant un point à partir des points précédents. Sauf, bien sûr, à atteindre les limites du domaine de définition : si tu trouves un point confondu avec le point de référence, ce n'est plus la peine de chercher d'autres points plus proches, par exemple. Ce n'est donc pas applicables pour les points les plus éloignés.

J'avais eu le même problème en écrivant un petit simulateur de gravité : 300 étoiles qui interagissent toutes entre elles, ça fait 90 000 vecteurs à remettre à jour à chaque frame.

Une bonne manière d'optimiser les temps de traitement, en revanche, est d'utiliser le système approprié. Si tu passes en coordonnées polaires, par exemple, tu ne t'intéresse qu'à la distance et tu peux laisser l'angle de côté. Tu te retrouves alors avec un tableau à une dimension qu'il est très facile de trier et de maintenir classé. La recherche du premier est alors en O(1) : c'est le premier du tableau ! et la recherche d'un point quelquonque est en O(n log n).

Par contre, si tu as une idée dont la manière évoluent tes points au cours du temps, alors tu peux faire une présélection en te basant sur le fait que les autres points ne pourront pas surpasser les caractéristiques des premiers avant un nombre d'étapes donné.

Notez que la question n'est pas posé à titre de demande d'aide mais plutôt comme un défi.

Si c'est une manière de titiller les participants pour qu'il trouvent la solution à ta place sans que cela se voie, ça ne prend pas. Il y en a beaucoup qui ont essayé avant !

[comode]

Si c'est une manière de titiller les participants pour qu'il trouvent la solution à ta place sans que cela se voie, ça ne prend pas. Il y en a beaucoup qui ont essayé avant !

Lol non, comme je disais, y'a rien de concret de derrière, et c'est vraiment histoire de débattre de quelque chose d'intéressant. C'est une question que je me pose depuis un moment quand je vois certains serveur de MMO par exemple ou des IA de fourmis communiquant par férhormones.

Perso, j'ai écrit la méthode (algo, pas codé) par arbre binaire dont je parle plus haut... Je découpe ma surface en parcelles de 10*10 par exemple, et je construit un arbre que je parcours de la racine vers les feuilles en comparant la coordonnée de mon élément courant (inferieur ou superieure/égale) à chaque noeud jusqu'a arriver à une feuille qui référencera elle même tous les éléments qui sont dans cette parcelle... A chaque déplacement d'un élément, on vérifie si il change de parcelle et on met la feuille de l'arbre a jour si nécessaire.

Ensuite, je trouve que le principe de l'union entre les résultats de mes arbres X et Y est pas top optimisé...

L'idée des coordonnées polaires est intéressante, mais ça impliquerais que chaque élément connaisse les coordonnées polaire de tous les autres éléments par rapport à lui même pour être exploitable... non ?

[Obsidian]

L'idée des coordonnées polaires est intéressante, mais ça impliquerais que chaque élément connaisse les coordonnées polaire de tous les autres éléments par rapport à lui même pour être exploitable... non ?

Si. C'est pour cela que, dans tous les cas, il faudra faire le travail au moins une fois. Un des avantages, cependant, est de pouvoir dresser une matrice triangulaire : la distance de A à B est forcément la même que celle de B à A, et les azimuts opposés.

[comode]

Je suis pas expert en coordonnées polaire (j'ai même jamais bossé avec), mais de ce que je comprend, chaque déplacement d'un élément quelconque implique donc de remettre à jour ses coordonnées par rapport à tous les autres éléments !? niveau optimisation, c'est peut être pas top du coup, même pour une matrice triangulaire...

Sinon, j'ai eu une autre idée...

Si on hashait tout bêtement le terrain...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
typedef struct element{
   int X, Y;
   element * previous, next;
} elem;
 
int XMax = 1000000; // largeur du terrain, on va dire qu'il est carré
int PARCELLE = 10; // taille de parcelle
int width = (int) (XMax / PARCELLE);
int height = width;
 
terrain [width][height] *elem; // on définie un tableau 2D dont les cases contiennent un pointeur vers une structures de type element

De cette façon, on stock pour chaque parcelle et sous forme de liste chainées l'ensemble des éléments qui sont dedans...

Tout déplacement d'un élément implique alors au besoin qu'on le recherche dans le tableau et qu'on le change de parcelle. L'acces devrait néanmoins êre rapide puisqu'on accède à l'entrée de la liste chainée le contenant en faisant :

Code :

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

1
2
 
elem * debut_liste = terrain[element.x % PARCELLE][element.y % PARCELLE];

reste plus qu'a coder des fonctions de parcours, d'ajout et suppression de liste chainée...

Apres, pour trouver tous les voisins situés à moins d'une certaines distance, y'a plus qu'a faire un truc du style :

Code :

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

1
2
3
4
5
int dist = 20;
int nb = (int) dist / PARCELLE;
for(int = (elem.x % PARCELLE) - nb; i++; i <= (elem.x % PARCELLE) + nb)
   for(int = (elem.y % PARCELLE) - nb; i++; i <= (elem.y % PARCELLE) + nb)
      recuprer(terrain[i][j]);

et enfin on afine le résultat avec un calcul de distance bete et mechant sur les éléments trouvés...

Ca parait cohérent ?

[pseudocode]

oui mais non... Cette méthode serait parfaitement inutilisable au delà d'un millier d'éléments a qui on demanderais de faire l'opération 2 ou 3 fois / secondes... Je donnais cet algo à titre d'exemple, mais c'est parfaitement irrecevable !

On peut se limiter a explorer les points qui sont "potentiellement" dans la boule de rayon R souhaitée.

En première approximation on peut éliminer tous les points qui ont une distance projetée sur X ou Y supérieure à R. Puis éliminer les points qui ne sont pas dans le carré de coté 2R. Et enfin éliminer ceux qui ne sont pas dans le cercle de rayon R.

Auquel cas, l'utilisation d'une segmentation d'espace 1D semble suffisante.

[comode]

On peut se limiter a explorer les points qui sont "potentiellement" dans la boule de rayon R souhaitée.

En première approximation on peut éliminer tous les points qui ont une distance projetée sur X ou Y supérieure à R. Puis éliminer les points qui ne sont pas dans le carré de coté 2R. Et enfin éliminer ceux qui ne sont pas dans le cercle de rayon R.

Auquel cas, l'utilisation d'une segmentation d'espace 1D semble suffisante.

Et comment tu fais pour éliminer tous les éléments qui ont une distance projetée sur X ou Y supérieure à R sinon en faisant une boucle qui parcourira l'ensemble des milliers d'éléments à chaque requête ?

[pseudocode]

Et comment tu fais pour éliminer tous les éléments qui ont une distance projetée sur X ou Y supérieure à R sinon en faisant une boucle qui parcourira l'ensemble des milliers d'éléments à chaque requête ?

Bah, tu maintiens tes éléments dans une structure de liste triée sur X (ou sur Y). Par exemple une liste chainée.

La recherche des bornes min/max de ton exploration se fait par une recherche dichotomique, donc assez rapidement. Reste a examiner les éléments entre ces 2 bornes.

[comode]

Bah, tu maintiens tes éléments dans une structure de liste triée sur X (ou sur Y). Par exemple une liste chainée.

La recherche des bornes min/max de ton exploration se fait par une recherche dichotomique, donc assez rapidement. Reste a examiner les éléments entre ces 2 bornes.

En effet, ça peut être une bonne solution, mais...

Si tu tries par dichotomie, t'es obligé d'utiliser un tableau pour stocker tes éléments. Si une recherche/inversion va alors assez vite, tout nouvel ajout ou retrait d'élément oblige a ré-allouer tout le tableau... Si c'est pas en soit inhumain inordinateur, ça oblige a effectuer un tri sur l'ensemble du tableau en cas d'ajout d'élément d'une part, et ça m'amène d'autre part à une nouvelle problématique : les accès concurrents ! Imaginons en effet que chaque élément soit gérer par un thread ou un processus distinct, il faut obligatoirement un sémaphore qui vérouillera l'ensemble du tableau lors de tout nouvel ajout/retrait et donc mettre toutes les autres opérations en attente... Puis pour bien faire les choses, il faudrait presque 1 sémaphore par case du tableau afin de pouvoir effectuer plusieurs tris de façon simultanée... Enfin au dela de ça, la méthode est intéressante ^^

Au fait, question d'ordre générale, au delà des attente qu'ils provoquent, les blocage/déblocage de sémaphore, ce sont des opérations lourdent pour l'os ?

[pseudocode]

Si tu tries par dichotomie, t'es obligé d'utiliser un tableau pour stocker tes éléments. Si une recherche/inversion va alors assez vite, tout nouvel ajout ou retrait d'élément oblige a ré-allouer tout le tableau... Si c'est pas en soit inhumain inordinateur, ça oblige a effectuer un tri sur l'ensemble du tableau en cas d'ajout d'élément

Il faut juste choisir une structure qui permette à la fois la recherche par dichotomie et l'ajout par insertion. Par exemple un B+Tree

d'une part, et ça m'amène d'autre part à une nouvelle problématique : les accès concurrents ! Imaginons en effet que chaque élément soit gérer par un thread ou un processus distinct, il faut obligatoirement un sémaphore qui vérouillera l'ensemble du tableau lors de tout nouvel ajout/retrait et donc mettre toutes les autres opérations en attente... Puis pour bien faire les choses, il faudrait presque 1 sémaphore par case du tableau afin de pouvoir effectuer plusieurs tris de façon simultanée... Enfin au dela de ça, la méthode est intéressante ^^

Chercher/ajouter/supprimer un élément dans un B+Tree n'est pas vraiment une opération couteuse (log(n))

[comode]

Il faut juste choisir une structure qui permette à la fois la recherche par dichotomie et l'ajout par insertion. Par exemple un B+Tree
Chercher/ajouter/supprimer un élément dans un B+Tree n'est pas vraiment une opération couteuse (log(n))

Je connaissais pas les B-Tree ! Je viens de regarder, en effet, c'est pal mal... Je ne me fais pas encore une idée des implications qu'aurai l'utilisation des accès concurrent, mais je vais m'y pencher.

[lcfseth]

L'idée des coordonnées polaires est intéressante, mais ça impliquerais que chaque élément connaisse les coordonnées polaire de tous les autres éléments par rapport à lui même pour être exploitable... non ?

Absolument pas. Soit 3 points A B C. Si AB = X et C € D(B,R)(Lire disque de centre B et de rayon R ) alors
(X-R) =< AC =< (X+R). Consequence de L'inégalité de Minkowski


Suffit donc de stocker la distance par rapport au centre de l'univers et d'utiliser une structure de donnée triées selon ce critére.
Aprés suffit de faire une simple recherche dichotomique.

Il est possible aussi de trouver une formule pour les angles (en 2D c'est faisable, je sais pas si ca l'est en 3D. ). ça devrait réduire encore plus le champ de recherche


Autre Solution :

Si X est d'un ordre de grandeur connu ( style X tourne autour d'une années lumiére ), on peut diviser l'univers en carré (cube) de côté = 1al.
Chaque point aura alors les cordonnées du carré (cube) auquel il appartient ainsi que ses propre coordonées à l'intérieur du carré (cube) .

Un point B à moins d'une al d'un point A appartient forcement à l'un des carrés (cubes) voisins à celui de A, voir au même carré (cube) .