Algorithmes en Java

images/orangebelt.png

Certains objets sont des structures de données : des objets construits explicitement pour "stocker" d’autres objets. On a par exemple des tableaux, des ArrayList, etc… Ces structures sont dotés de méthodes pour ajouter un élément, en rechercher un, le retirer etc. Les modes opératoires varient: on aura ainsi des structures à accès direct (RandomAccess) dans lesquelles on va directement adresser l'élément d’index N; des files ( FIFO : "First In , First Out"), des piles ( LIFO : "Last In, First Out"), des files à double entrée (Deque) , etc.

On peut réaliser diverses opérations de recherche, rangement dans ces structures: voici par exemple une démonstration dans un ancien répertoire de demos standard de Java.

image: demo de tri

On constate dans cet exemple que les performances de opérations de tris peuvent considérablement varier selon l'algorithme choisi! (Les considérations algorithmiques ne s’appliquent pas forcément à des structures de données mais concernent les stratégies de déroulement du code en général).

[Note]

Dans des situations complexes il faut savoir rechercher dans la littérature scientifique et technique des exemples de traitement de problèmes analogues.

Par exemple : "The art of computer programming"

Les tris

Les critères de choix d’un algorithme de tri sont basés sur le nombre d'éléments à trier, l’ordre relatif (les objets sont-ils complètement dans le désordre), la "stabilité" (lorsque deux objets sont égaux et déjà rangés conserve-t’on l’ordre préexistant? - par exemple on veut trier une liste de Produits par prix croissant et ils sont déjà triés par ordre d’importance des ventes on voudrait que lorsque deux produits ont le même prix, ils soient présentés par ordre d’importance des ventes-), etc.

De manière pratique dans de nombreux cas courant on peut se contenter d’exécuter des algorithmes prédéfinis fournis avec des librairies standard:

// utilisation du package java.util

   Produit[] tabProduits = ...... ;
   Arrays.sort(tabProduits) ;
   ArrayList<Produit> liste = .... ;
   Collections.sort(liste) ;

Ici les tris se font par "ordre naturel" (c.a.d que les objets triés -ici de type Produit- doivent être Comparable) ;

On peut introduire en paramètre un code de comparaison :

   Comparator<Produit> comparateurPrix = new Comparator<Produit>() {
      public int compare(Produit p1, Produit p2) {
         return p1.getPrixTTC().compareTo(p2.getPrixTTC()) ;
      }
      //ignorer cette contrainte ici
      public boolean equals(Object o) { return super.equals(o) ;}
   } ;

   Arrays.sort(tabProduits, comparateurPrix) ;
   Collections.sort(liste, comparateurPrix) ;

Les recherches

L'évaluation des algorithmes de tri est basée sur la complexité: le nombre d’opérations qu’il faut théoriquement exécuter pour effectuer le tri et, en particulier, le nombre de comparaisons qu’il va falloir exécuter.

On retrouve un souci du nombre de comparaisons à effectuer lorsque l’on recherche un élément dans une structure.

Si on recherche un élément qui est "égal" à un autre dans une structure de petite taille on peut tout à fait se contenter d’exécuter linéairement des comparaisons (quelques dizaines de comparaisons ne coûtent presque rien en temps).

Pour de grandes tailles il faut se pencher sur les algorithmes.

Pour une liste triée (selon le critère de recherche) et qui est à accès direct on peut effectuer une recherche dichotomique (complexité logN : améliorable si on peut faire des interpolations -hypothèses sur la répartition-).

public class Produit implements Identifiable, Comparable<Identifiable> {
 //....
}

// dans un code : ArrayList<Produit> liste est déjà triée "naturellement"
   int index = Collections.binarySearch( liste ,
      new Identifiable() {
         public String getClef() { return referenceCherchée ;}
      } ) ;
   if( index >= 0 ) {
      produit = liste.get(index) ;
   }

Une autre approche est d’indexer les données par une clef et de réaliser un dictionnaire par table de hachage (hash table).

Tables de hachage

Principe des tables de hachage :

image: table de hash

On applique à l’objet qui sert de clef la méthode hashCode() qui doit rendre un entier caractéristique. On prend un index qui est l’entier obtenu modulo la taille de la table de référence on obtient une "entrée" qui permet de retrouver la paire clef/valeur correspondante. Si deux clefs on le même code de hachage on les range dans une liste chaînée.

L’enjeu est d'éviter des collisions trop importantes (qui ferait baisser les performances). La choix d’un code correct pour la méthode hashCode d’un objet est délicat. De plus les méthodes hashCode et equals d’un objet doivent être cohérentes (deux objets "égaux" utilisés comme clef doivent avoir le même hashcode -la réciproque n'étant pas vraie-).

Dans le package java.util voir les classes HashMap et HashSet (un ensemble pour lequel l’unicité des membres est contrôlée par une table de hachage sous-jacente).

Voir également les très performantes EnumMap et EnumSet (en fait les structures sous-jacentes sont des tableaux à accès direct utilisant l’index du type énuméré)

Les compromis mémoire/performance

L’exemple des tables hachage permet d’introduire la notion de compromis mémoire/performance: pour être performant certains algorithmes ont besoin de beaucoup de mémoire.

Par ailleurs au delà d’une certaine taille il devient difficile de maintenir des structures de données en mémoire. On a alors recours à des replis de données sur fichiers (ou base de données).

Il y a des algorithmes spécifiques pour gérer la mémoire et aussi des dispositifs qui permettent d'économiser de la place.

Imaginons par exemple que l’on veuille générer toutes les combinaisons possibles de P éléments parmi N. Si l’on génère en mémoire toutes ces combinaisons pour les exploiter ensuite on va rapidement dépasser les capacités d’un ordinateur (même généreux)!

Une autre solution consiste à générer uniquement une combinaison quand le code client la demande: un objet "Combineur" fournira alors un Itérateur (interface standard Iterator).

public class Combineur<X> implements Iterable<X[]> {
   ....
   public Combineur(X[] nDonnées, int nombreP) { ....
}

   // code utilisation
   Combineur<Type> combineur = new Combineur(tableauDeType, p) ;
   Iterator<Type[]> iterator = combineur.iterator() ; // par exemple
   while( iterator.hasNext() ) {
      // tableau de taille P
      Type[] combiCourante = iterator.next() ;
      System.out.println(Arrays.toString(combiCourante)) ;
   }
   // de toute manière si le nombre de combinaison est très grand
   // le temps d'exécution de la boucle devient phénoménal
   // donc cet exemple est limité en pratique!
   // remarque: il arrive parfois que le calcul théorique d'un temps d'exécution
   // donne des résultats à l'échelle du siècle !
   // Une telle exécution ne peut évidement pas être envisagée......
[Note]

Un des moyens pour détecter des anomalies algorithmiques: mesurer les temps d’exécution pour 10,100, 500, 1000 objets etc…. Si les temps d’exécution croissent de manière exponentielle on a manifestement un problème dans le code!

Autre exemple d’itérateur: soit un code qui prenne une requête SQL pour aller chercher des objets dans une base de données. Si ce code exécute une requête qui fournit un très grand nombre d’objets et s’il les stocke en mémoire avant de rendre un résultat on risque de saturer la mémoire (et/ou de faire attendre l’utilisateur!).

Une solution est de rendre un Iterator (ou mieux un Flow.Publisher)et d’aller rechercher et créer les objets au fur et à mesure de la demande. Au besoin on peut anticiper la demande en créant un cache dans lequel on stocke un nombre limité d’objets.

Cette problématique des caches est critique pour des objets consommant beaucoup de mémoire comme des images graphiques. On a des stratégies qui consistent à ne charger que quelques images en mémoire: les images les plus utilisées resteront et les autres seront évacuées (quitte à être "rechargées" plus tard).

Les références faibles (package java.lang.ref) permettent de gérer des objets non-permanents et adaptés aux exigences du glaneur de mémoire (garbage collector). Voir la leçon consacrée aux références faibles.