(Grosse) lenteur d'algorithme de détection de pixels contigus

Bonjour à tous,

Je développe actuellement -à titre personnel- un algorithme de détection des pixels contigus dans une image. Voici son fonctionnement simplifié, pour l'exploration d'une zone de l'image:

On créée un objet "cellule" défini par un attribut (String), ses coordonnées (int), les coordonnées de son père (int).
On appelle sa méthode 'Rayonne', qui créée de nouveaux objets "cellule" dans une direction donnée de l'espace (Up Down Right Left) si la case connexe correspondante répond à certaines conditions.
Si aucune de ces conditions n'est remplie, cette case met à jour le tableau (boolean) de suivi de son père.
Lorsque le tableau est complet, le père met à jour le tableau de son propre père, et ainsi de suite jusqu'à la case d'attribut "Main" qui n'a pas de père.
Lorsque le tableau de suivi de "Main" est complet, c'est que toute la zone a été explorée.

Les coordonnées des cellules sont stockées dans un ArrayList<String>. (int x+","+int y)

Cet algorithme fonctionne parfaitement sur des zones restreintes (2500 px ça va encore), mais dès que l'on augmente la taille de la zone à explorer, l'appli rame un maximum et finit par se bloquer (Ctrl Alt Suppr nécessaire).

Ma question:
Est-ce parce que j'ai utilisé des ArrayList ?
Est-ce parce qu'il y a trop d'objets créés ?
Est-ce à cause d'une autre raison ?

Merci!

> Uncle Bobo

Tu n'aurais pas un problème de mémoire? pas sur car tu n'as pas d'ereur outOfmemory, mais bon...

Par contre si j'ai bien compris ton explication, ton algo fait que tu traites toutes tes cellules 3 fois au moins, avec la méthode rayonne. As-tu du cache sur les valeurs de tes cellules ou pas?

Non elles ne sont pas traitées 3 fois, car je vérifie avant de créer une nouvelle cellule que la case à explorer n'a pas déjà été explorée auparavant (je créée un tableau 2D de "cellule" qui se remplit à chaque nouvelle création d'objet).

"As-tu du cache sur les valeurs de tes cellules ou pas?"
=> Du quoi ? :oops:

Citation:

---

Envoyé par uncle bobo

"As-tu du cache sur les valeurs de tes cellules ou pas?"
=> Du quoi ? :oops:

---

Je te demandé si tu stockais quelque part tes objets cellules (un tableau par ex ;)) pour les retrouver les valeurs facilement sans recalculer et multiplier le nombre d'objet.

as-tu essayer de supprimer les cellules inutile de ton tableau?
A la 3e ligne la 1ere ne sert plus à rien passé ses objets à null donnerait de la place pour le GC.

Le problème, c'est que l'appel de l'objet parent se fait justement par l'intermédiaire de ce tableau de "cellule".
Si je supprime mes objets du tableau au fur et à mesure, je ne pourrais plus actualiser leurs tableaux de suivi par la suite.

Je ne me suis pas penche en details sur la description sur probleme, mais a priori pour le stockage j'utiliserai plutot une Map<Integer, List<Point>> ou la cle est le numero de la zone et la List<Point> est en fait une LinkedList<Point> du moins pendant le travail de recherche (car on ne sait pas combien de points on va trouver). Libre a toi de la transformer en ArrayList<Point> tout a la fin de la recherche quand on a tout trouve.

On peut aussi utiliser une Map<Integer, Map<Point, Point>> (note : cle et valeurs sont alors identiques) ce qui permet de plus rapidement detecter (temps de la methode containsKey()) si on repasse sur une point deja traite, mais c'est un poil initule car si l'algorithme d'innondation est correctement fait, il traite ca deja de lui-meme et donc ne necessite pas d'appeler containsKey() ou contains()..