Améliorer la performance d'une recherche de point dans des vecteursRésolu

Question

bonsoir,

voila je vous explique ce que je suis entrain de faire. Je dessine une zone sur une image et pour chaque point selectionné je recherche dans tous les vecteurs si il est déja présent. Mais en utilisant cette fonction ci dessous, quand jaffiche tous les points de la zone ca prend une éternité. Je voulais donc savoir comment je pourrais améliorer cet algorithme. (si je l'enleve les points sont la instantanément)

public boolean PointExist(Point p)
 {
  boolean b=false;
  int p1;
  int p2;
  
  if(!this.contenu_label.isEmpty())
  {
   for(int i=0;i<this.contenu_label.size() && !b;i++)
   {
    //on extrait le Vector<Vector> de i
    Vectorvext=(Vector)(this.contenu_label.get(i)).get(3);
    
    if(!vext.isEmpty())
    {
     for(int j=0;j<vext.size() && !b;j++)
     {
      p1=((Point)vext.get(j)).x;
      p2=((Point)vext.get(j)).y;
      
      if((p1==p.x) && (p2==p.y))
      {
       b=true;
      }
     }
    }


   }
  }
  
  return b;
 }

merci de votre aide

Francks11 · Accepted Answer

ca marche, ct lié à une erreur indice... donc avant ca devait déja marcher...
merci en tout cas

Twinuts · Answer

Salut, pourquoi ne pas faire simplement Vector vecGlobal = new Vector(); //remplissage //........ public boolean exist(Point p){ if(vecGlobal.isEmpty()) return false; for(Vector vext : vecGlobal) if(vext.contains(p)) return true; return false; } ------------------------------------ "On n'est pas au resto : ici on ne fait pas dans les plats tout cuits ..." WORA

cs_DARKSIDIOUS · Answer

Il vaut mieux utiliser un HashTable pour ce genre d'opération si on veut des performances optimales !

Francks11 · Answer

ouai je vais tester car ma fonction prend trop de temps quand je verifie chaque point avec defois plus de 60 000 points...

pr la hash table je peux pas car sinon faut que je change toute la structure de l'appli

si vous avez d'autres idées, je suis preneur

merci

cs_DARKSIDIOUS · Answer

Toute la structure, pas forcément : un Vector n'est qu'une collection d'object, tout comme le HashTable (de façon plus hiérarchique, je te l'accorde).

Sinon, essaye d'utiliser des List plutôt qui sont plus optimisée que le Vector (la LinkedList par exemple).

Francks11 · Answer

j'ai testé la deuxieme fonction, c pas assez performant...
Je sais vraiment pas comment faire... peut être qu'il faudrait que je classe l'abscise en ordre croissant ou je sais pas trop...

Twinuts · Answer

Salut,

le Vector est bien mais toutes ses méthodes sont synchronizé donc cela emplifie sont temps d'acces... appres faudrait voir ce que tu fais dans ton code pour aider à l'optimisation de celui-ci...

------------------------------------
"On n'est pas au resto : ici on ne fait pas dans les plats tout cuits ..."

WORA

kaloway · Answer

bonsoir voici quelque petit truc.

dnans ta boucle for(int i=0;i<this.contenu_label.size() && !b;i++) sort le "this.contenu_label.size()" et remplaces le par une variable. le !b devrait être testé avant la boucle for.
après ces modificaction la boucle for devient for(inti=0;i<variable;i++).
encore une dernière optimisation for(int i=variable;i=0;i++) au lieu de for(int i=0;i<variable;i++). le test du égale à zero est plus rapide que égale  à une valeur.

est ce que tu peux récupèrer tes points sous forme de point2d. car la classe point2d a la méthode equals pour comparer 2 points. les méthodes de l'api sont souvent plus rapide que nos propres méthodes que nous créons.

Francks11 · Answer

sinon vous me proposerez quoi? faire une fonction récursive ou utiliser hash table? ou faire je sais pas quoi. Mais faudrait qui sache dans la seconde si tous les points existent ou pas...

voila

cs_DARKSIDIOUS · Answer

lol, une fonction récursive !!! Tu peux dire adieux aux performances là !

Pour traîter plus de 60 000 points en moins d'une seconde, tourne toi vers le HashTable !!! Ou ordonne tes points et stocke-les dans un tableau, avec un bon algorithme de recherche, tu peux arriver à trouver ton points en log n opérations (soit environ 11 opérations !, là seule chose, c'est d'avoir aussi un bon algo de tri (tri par insertion ou tri shell fortement déconseillé, utilise plutôt un tri de Dijkstra, ou un tri rapide). Mais ca va te faire une grosse algorithmique assez dure à utiliser (car avec un tableau tu perd tout les avantages de l'ajout d'un object dans un collection !).

Non franchement, passe par un HashTable, tu obtiendra les performances d'un tableau sans trop de prise de tête. Eclipse est fait pour faire du refactoring de code rapidement, profite en... ;)

Francks11 · Answer

j'ai essayé une hash table mais ca pas l'impression de marcher:

hashtable ht=new hashtable();

j'ai ajouté chaque point comme ca:

ht.put(p,p);//P est un point
--------------------
-------------------
-------------------

et apres quand je test si un point existe, j'ai fais ceci:

if(ht.contains(p))
{

b=true;

}

mais ca a pas l'air de marché vu que ct tj faux...

si vous pouviez m'aider...

merci

cs_DARKSIDIOUS · Answer

Une Hashtable est une collection hiérarchique composée de clés et de valeur. A une clé est associé une ou plusieurs valeurs.
L'utilisation la plus commune est d'utiliser une chaîne de caractère comme clé (pour un dictionnaire par exemple).

Ce que je te conseille de faire, c'est de mettre les coordonnées de ton point (+ d'autres propriétés si plusieurs points peuvent être aux mêmes coordonnées) en tant que chaîne de caractère pour la clé, et ton point en tant que valeur.

Pourquoi ? Je pense que le test d'égalité de la fonction contains se base sur l'adresse physique du point (méthode de comparaison classique de Java) et non sur le contenu de l'objet. Donc là si tu teste un point avec la coordonnée "1, 1" avec un point avec la même coordonnée, mais qui est un objet différent, la fonction contains te renverra false !

cs_DARKSIDIOUS · Answer

Autre petite chose : utilise plutôt la fonction containsKey à la place de la fonction contains, elle est plus rapide car elle ne teste que les clés de ta table !

Francks11 · Answer

ok mais comment tester si le point p que je mets en paramètre a la meme clé que une clé d'une meme point dans la hashtable... 

je dois faire un clé avec p et verifier qu'elle est identique à celle du point recherché, c'est bien ca??

merci en tout cas, je vais tester...

Francks11 · Answer

en faite ca marche tj pas, je fais un ht.containsKey(clévoulut) mais tj false

la clé est construite comme ca vp.get(i).x+"-"+vp.get(i).y;

et chaque fois je recherche ce type de clé p.x+"-"+p.y

Améliorer la performance d'une recherche de point dans des vecteurs

15 réponses

Votre réponse

Discussions similaires