Chapitre 9 - Stockage des objets

pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Remplir un tableau

La bibliothèque standard Java Arrays propose aussi une méthode fill(), mais celle-ci est relativement triviale : elle ne fait que dupliquer une certaine valeur dans chaque cellule, ou dans le cas d'objets, copier la même référence dans chaque cellule. En utilisant Arrays2.print(), les méthodes Arrays.fill() peuvent être facilement illustrées :

//: c09:FillingArrays.java
// Utilisation de Arrays.fill()
import com.bruceeckel.util.*;
import java.util.*;

public class FillingArrays {
  public static void main(String[] args) {
    int size = 6;
    // Ou récupère la taille depuis la ligne de commande :
    if(args.length != 0)
      size = Integer.parseInt(args[0]);
    boolean[] a1 = new boolean[size];
    byte[] a2 = new byte[size];
    char[] a3 = new char[size];
    short[] a4 = new short[size];
    int[] a5 = new int[size];
    long[] a6 = new long[size];
    float[] a7 = new float[size];
    double[] a8 = new double[size];
    String[] a9 = new String[size];
    Arrays.fill(a1, true);
    Arrays2.print("a1 = ", a1);
    Arrays.fill(a2, (byte)11);
    Arrays2.print("a2 = ", a2);
    Arrays.fill(a3, 'x');
    Arrays2.print("a3 = ", a3);
    Arrays.fill(a4, (short)17);
    Arrays2.print("a4 = ", a4);
    Arrays.fill(a5, 19);
    Arrays2.print("a5 = ", a5);
    Arrays.fill(a6, 23);
    Arrays2.print("a6 = ", a6);
    Arrays.fill(a7, 29);
    Arrays2.print("a7 = ", a7);
    Arrays.fill(a8, 47);
    Arrays2.print("a8 = ", a8);
    Arrays.fill(a9, "Hello");
    Arrays2.print("a9 = ", a9);
    // Manipulation de plages d'index :
    Arrays.fill(a9, 3, 5, "World");
    Arrays2.print("a9 = ", a9);
  }
} ///:~

On peut soit remplir un tableau complètement, soit - comme le montrent les deux dernières instructions - une certaine plage d'indices. Mais comme il n'est possible de ne fournir qu'une seule valeur pour le remplissage dans Arrays.fill(), les méthodes Arrays2.fill() sont bien plus intéressantes.

Copier un tableau

La bibliothèque standard Java propose une méthode static, System.arraycopy(), qui réalise des copies de tableau bien plus rapidement qu'une boucle for. System.arraycopy() est surchargée afin de gérer tous les types. Voici un exemple qui manipule des tableaux d'int :

//: c09:CopyingArrays.java
// Utilisation de System.arraycopy()
import com.bruceeckel.util.*;
import java.util.*;

public class CopyingArrays {
  public static void main(String[] args) {
    int[] i = new int[25];
    int[] j = new int[25];
    Arrays.fill(i, 47);
    Arrays.fill(j, 99);
    Arrays2.print("i = ", i);
    Arrays2.print("j = ", j);
    System.arraycopy(i, 0, j, 0, i.length);
    Arrays2.print("j = ", j);
    int[] k = new int[10];
    Arrays.fill(k, 103);
    System.arraycopy(i, 0, k, 0, k.length);
    Arrays2.print("k = ", k);
    Arrays.fill(k, 103);
    System.arraycopy(k, 0, i, 0, k.length);
    Arrays2.print("i = ", i);
    // Objects :
    Integer[] u = new Integer[10];
    Integer[] v = new Integer[5];
    Arrays.fill(u, new Integer(47));
    Arrays.fill(v, new Integer(99));
    Arrays2.print("u = ", u);
    Arrays2.print("v = ", v);
    System.arraycopy(v, 0,
      u, u.length/2, v.length);
    Arrays2.print("u = ", u);
  }
} ///:~

arraycopy() accepte comme arguments le tableau source, le déplacement dans le tableau source à partir duquel démarrer la copie, le tableau destination, le déplacement dans le tableau destination à partir duquel démarrer la copie, et le nombre d'éléments à copier. Bien entendu, toute violation des frontières du tableau générera une exception.

L'exemple montre bien qu'on peut copier des tableaux de scalaires comme des tableaux d'objets. Cependant, dans le cas de la copie de tableaux d'objets, seules les références sont copiées - il n'y a pas duplication des objets eux-mêmes. C'est ce qu'on appelle une copie superficielle (voir l'Annexe A).

Comparer des tableaux

Arrays fournit la méthode surchargée equals() pour comparer des tableaux entiers. Encore une fois, ces méthodes sont surchargées pour chacun des types de base, ainsi que pour les Objects. Pour être égaux, les tableaux doivent avoir la même taille et chaque élément doit être équivalent (au sens de la méthode equals()) à l'élément correspondant dans l'autre tableau (pour les types scalaires, la méthode equals() de la classe d'encapsulation du type concerné est utilisé ; par exemple, Integer.equals() est utilisé pour les int). Voici un exemple :

//: c09:ComparingArrays.java
// Utilisation de Arrays.equals()
import java.util.*;

public class ComparingArrays {
  public static void main(String[] args) {
    int[] a1 = new int[10];
    int[] a2 = new int[10];
    Arrays.fill(a1, 47);
    Arrays.fill(a2, 47);
    System.out.println(Arrays.equals(a1, a2));
    a2[3] = 11;
    System.out.println(Arrays.equals(a1, a2));
    String[] s1 = new String[5];
    Arrays.fill(s1, "Hi");
    String[] s2 = {"Hi", "Hi", "Hi", "Hi", "Hi"};
    System.out.println(Arrays.equals(s1, s2));
  }
} ///:~

Au début du programme, a1 et a2 sont identiques, donc le résultat est « true » ; puis l'un des éléments est changé donc la deuxième ligne affichée est « false ». Dans le dernier cas, tous les éléments de s1 pointent sur le même objet, alors que s2 contient cinq objets différents. Cependant, l'égalité de tableaux est basée sur le contenu (via Object.equals()) et donc le résultat est « true ».

Comparaison d'éléments de tableau

L'une des fonctionnalités manquantes dans les bibliothèques Java 1.0 et 1.1 sont les opérations algorithmiques - y compris les simples tris. Ceci était relativement frustrant pour quiconque s'attendait à une bibliothèque standard conséquente. Heureusement, Java 2 a corrigé cette situation, au moins pour le problème du tri.

Le problème posé par l'écriture d'une méthode de tri générique est que le tri doit réaliser des comparaisons basées sur le type réel de l'objet. Bien sûr, l'une des approches consiste à écrire une méthode de tri différente pour chaque type, mais cela va à l'encontre du principe de réutilisabilité du code pour les nouveaux types.

L'un des buts principaux de la conception est de « séparer les choses qui changent de celles qui ne bougent pas » ; ici, le code qui reste le même est l'algorithme général de tri, alors que la manière de comparer les objets entre eux est ce qui change d'un cas d'utilisation à l'autre. Donc au lieu de coder en dur le code de comparaison dans différentes procédures de tri, on utilise ici la technique des callbacks. Avec un callback, la partie du code qui varie d'un cas à l'autre est encapsulé dans sa propre classe, et la partie du code qui ne change pas appellera ce code pour réaliser les comparaisons. De cette manière, il est possible de créer différents objets pour exprimer différentes sortes de comparaisons et de les passer au même code de tri.

Dans Java 2, il existe deux manières de fournir des fonctionnalités de comparaison. La méthode naturelle de comparaison constitue la première, elle est annoncée dans une classe en implémentant l'interface java.lang.Comparable. C'est une interface très simple ne disposant que d'une seule méthode, compareTo(). Cette méthode accepte un autre Object comme argument, et renvoie une valeur négative si l'argument est plus grand que l'objet courant, zéro si ils sont égaux, ou une valeur positive si l'argument est plus petit que l'objet courant.

Voici une classe qui implémente Comparable et illustre la comparaison en utilisant la méthode Arrays.sort() de la bibliothèque standard Java :

//: c09:CompType.java
// Implémenter Comparable dans une classe.
import com.bruceeckel.util.*;
import java.util.*;

public class CompType implements Comparable {
  int i;
  int j;
  public CompType(int n1, int n2) {
    i = n1;
    j = n2;
  }
  public String toString() {
    return "[i = " + i + ", j = " + j + "]";
  }
  public int compareTo(Object rv) {
    int rvi = ((CompType)rv).i;
    return (i < rvi ? -1 : (i == rvi ? 0 : 1));
  }
  private static Random r = new Random();
  private static int randInt() {
    return Math.abs(r.nextInt()) % 100;
  }
  public static Generator generator() {
    return new Generator() {
      public Object next() {
        return new CompType(randInt(),randInt());
      }
    };
  }
  public static void main(String[] args) {
    CompType[] a = new CompType[10];
    Arrays2.fill(a, generator());
    Arrays2.print("before sorting, a = ", a);
    Arrays.sort(a);
    Arrays2.print("after sorting, a = ", a);
  }
} ///:~

Lorsque la fonction de comparaison est définie, il vous incombe de décider du sens à donner à la comparaison entre deux objets. Ici, seules les valeurs i sont utilisées dans la comparaison, les valeurs j sont ignorées.

La méthode static randInt() produit des valeurs positives entre zéro et 100, et la méthode generator() produit un objet implémentant l'interface Generator, en créant une classe interne anonyme (cf. Chapitre 8). Celui-ci génére des objets CompType en les initialisant avec des valeurs aléatoires. Dans main(), le générateur est utilisé pour remplir un tableau de CompType, qui est alors trié. Si Comparable n'avait pas été implémentée, une erreur de compilation aurait été générée lors d'un appel à sort().

Dans le cas où une classe n'implémente pas Comparable, ou qu'elle l'implémente d'une manière qui ne vous satisfait pas (c'est à dire que vous souhaitez une autre fonction de comparaison pour ce type), il faut utiliser une autre approche pour comparer des objets. Cette approche nécessite de créer une classe séparée qui implémente l'interface Comparator, comportant les deux méthodes compare() et equals(). Cependant, sauf cas particuliers (pour des raisons de performance notamment), il n'est pas nécessaire d'implémenter equals() car chaque classe dérive implicitement de Object, qui fournit déjà cette méthode. On peut donc se contenter de la méthode Object.equals() pour satisfaire au contrat imposé par l'interface.

La classe Collections (que nous étudierons plus en détails par la suite) dispose d'un Comparator qui inverse l'ordre de tri. Ceci peut facilement être appliqué à CompType :

//: c09:Reverse.java
// Le Comparator Collecions.reverseOrder().
import com.bruceeckel.util.*;
import java.util.*;

public class Reverse {
  public static void main(String[] args) {
    CompType[] a = new CompType[10];
    Arrays2.fill(a, CompType.generator());
    Arrays2.print("before sorting, a = ", a);
    Arrays.sort(a, Collections.reverseOrder());
    Arrays2.print("after sorting, a = ", a);
  }
} ///:~

L'appel à Collections.reverseOrder() produit une référence sur le Comparator.

Voici un deuxième exemple dans lequel un Comparator compare des objets CompType en se basant cette fois sur la valeur de leur j plutôt que sur celle de i :

//: c09:ComparatorTest.java
// Implémenter un Comparator pour une classe.
import com.bruceeckel.util.*;
import java.util.*;

class CompTypeComparator implements Comparator {
  public int compare(Object o1, Object o2) {
    int j1 = ((CompType)o1).j;
    int j2 = ((CompType)o2).j;
    return (j1 < j2 ? -1 : (j1 == j2 ? 0 : 1));
  }
}

public class ComparatorTest {
  public static void main(String[] args) {
    CompType[] a = new CompType[10];
    Arrays2.fill(a, CompType.generator());
    Arrays2.print("before sorting, a = ", a);
    Arrays.sort(a, new CompTypeComparator());
    Arrays2.print("after sorting, a = ", a);
  }
} ///:~

La méthode compare() doit renvoyer un entier négatif, zéro ou un entier positif selon que le premier argument est respectivement plus petit, égal ou plus grand que le second.

Trier un tableau

Avec les méthodes de tri intégrées, il est maintenant possible de trier n'importe quel tableau de scalaires ou d'objets implémentant Comparable ou disposant d'une classe Comparator associée. Ceci comble un énorme trou dans les bibliothèques de Java - croyez-le ou non, Java 1.0 ou 1.1 ne fournissait aucun moyen de trier des Strings ! Voici un exemple qui génére des objets String aléatoirement et les trie :

//: c09:StringSorting.java
// Trier un tableau de Strings.
import com.bruceeckel.util.*;
import java.util.*;

public class StringSorting {
  public static void main(String[] args) {
    String[] sa = new String[30];
    Arrays2.fill(sa,
      new Arrays2.RandStringGenerator(5));
    Arrays2.print("Before sorting: ", sa);
    Arrays.sort(sa);
    Arrays2.print("After sorting: ", sa);
  }
} ///:~

Il est bon de noter que le tri effectué sur les Strings est lexicographique, c'est à dire que les mots commençant par des majuscules apparaissent avant ceux débutant par une minuscule (typiquement les annuaires sont triés de cette façon). Il est toutefois possible de redéfinir ce comportement et d'ignorer la casse en définissant une classe Comparator. Cette classe sera placée dans le package « util » à des fins de réutilisation :

//: com:bruceeckel:util:AlphabeticComparator.java
// Garder les lettres majuscules et minuscules ensemble.
package com.bruceeckel.util;
import java.util.*;

public class AlphabeticComparator
implements Comparator{
  public int compare(Object o1, Object o2) {
    String s1 = (String)o1;
    String s2 = (String)o2;
    return s1.toLowerCase().compareTo(
      s2.toLowerCase());
  }
} ///:~

Chaque String est convertie en minuscules avant la comparaison. La méthode compareTo() de String fournit ensuite le comparateur désiré.

Voici un exemple d'utilisation d'AlphabeticComparator :

//: c09:AlphabeticSorting.java
// Garder les lettres majuscules et minuscules ensemble.
import com.bruceeckel.util.*;
import java.util.*;

public class AlphabeticSorting {
  public static void main(String[] args) {
    String[] sa = new String[30];
    Arrays2.fill(sa,
      new Arrays2.RandStringGenerator(5));
    Arrays2.print("Before sorting: ", sa);
    Arrays.sort(sa, new AlphabeticComparator());
    Arrays2.print("After sorting: ", sa);
  }
} ///:~

L'algorithme de tri utilisé dans la bibliothèque standard de Java est conçu pour être optimal suivant le type d'objets triés : un Quicksort pour les scalaires, et un tri-fusion stable pour les objets. Vous ne devriez donc pas avoir à vous soucier des performances à moins qu'un outil de profilage ne vous démontre explicitement que le goulot d'étranglement de votre programme soit le processus de tri.

Effectuer une recherche sur un tableau trié

Une fois un tableau trié, il est possible d'effectuer une recherche rapide sur un item en utilisant Arrays.binarySearch(). Il est toutefois très important de ne pas utiliser binarySearch() sur un tableau non trié ; le résultat en serait imprévisible. L'exemple suivant utilise un RandIntGenerator pour remplir un tableau et produire des valeurs à chercher dans ce tableau :

//: c09:ArraySearching.java
// Utilisation de Arrays.binarySearch().
import com.bruceeckel.util.*;
import java.util.*;

public class ArraySearching {
  public static void main(String[] args) {
    int[] a = new int[100];
    Arrays2.RandIntGenerator gen =
      new Arrays2.RandIntGenerator(1000);
    Arrays2.fill(a, gen);
    Arrays.sort(a);
    Arrays2.print("Sorted array: ", a);
    while(true) {
      int r = gen.next();
      int location = Arrays.binarySearch(a, r);
      if(location >= 0) {
        System.out.println("Location of " + r +
          " is " + location + ", a[" +
          location + "] = " + a[location]);
        break; // Sortie de la boucle while
      }
    }
  }
} ///:~

Ce livre a été écrit par Bruce Eckel ( télécharger la version anglaise : Thinking in java )
Ce chapitre a été traduit par Jérome Quelin ( groupe de traduction )
télécharger la version francaise (PDF) | Commandez le livre en version anglaise (amazon) | télécharger la version anglaise

pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Penser en Java 2nde édition

Thinking in Java