BattleDev 14 : leçons en vue de la prochaine édition

J’aurais bien aimé utiliser le langage Go mais il n’était pas proposé dans la liste. Je me suis donc rabattu sur Java qui est le langage que j’ai le plus pratiqué. Après cette nouvelle participation j’ai remarqué deux ou trois choses qui reviennent souvent.

Le toString() tu implémenteras

Assez rapidement il est nécessaire d’utiliser des classes de type DTO/Entity si l’on ne veut se retrouver avec un code illisible. Afin de faciliter le débogage il est primordiale d’implémenter la méthode toString(). 
Sans toString() :

[Stick@1eef9aef, Stick@11389053, Stick@5db99216, Stick@3ec11999]

Avec toString() :

[Stick{length=12, owner='Yann'}, Stick{length=56, owner='Enora'}, Stick{length=8, owner='Katell'}, Stick{length=21, owner='Erwann'}]

La différence saute aux yeux et quand on essaie de comprendre pourquoi notre solution ne fonctionne pas cela permet de gagner un temps précieux !

Le tri tu maîtriseras

L’autre avantage d’utiliser des classes DTO va être de faciliter le tri des listes. Pour résoudre les 4 premiers exercices il était nécessaire d’utiliser un algorithme de tri. Ce n’est pas vraiment une surprise, les algorithmes de tri sont parmis les plus utilisés. Deux approches possibles.

Le tri à bulle tu banniras

Une approche naïve serait de se préparer sous le coude un bout de code permettant de trier facilement une liste. 
Prenons l’exemple du premier exercice. Pour rappel il s’agit de tirer à la courte paille, les pailles étant remplacées ici par des bouts de bois.

On imagine une classe DTO de type:

public class Stick {

  private int length;  
  private String owner;  
  
  public Stick(int length, String owner) {  
    this.length = length;  
    this.owner = owner;  
  }  
  
  public int getLength() {  
    return length;  
  }  
  
  public String getOwner() {  
    return owner;  
  }  
  
  @Override
  public String toString() {
    return "Stick{" +
            "length=" + length +
            ", owner='" + owner + '\'' +
            '}';
  }
}

La méthode de tri ressemblerait probablement à :

// Tri à bulles  
public static void Sort(List<Stick> items) {  
  int n = items.size();  
  for (int i = 0; i < n - 1; i++)  
    for (int j = 0; j < n - i - 1; j++)  
      if (items.get(j).length > items.get(j + 1).length) {  
        Stick temp = items.get(j);  
        items.set(j, items.get(j + 1));  
        items.set(j + 1, temp);  
      }  
}

Cela fonctionne correctement et c’est peut-être suffisant pour passer à l’exercice suivant. Mais personnellement il y a deux choses qui me chagrinent :

• D’une part on se retrouve à écrire beaucoup de code
• D’autre part le tri à bulles a une complexité de o(n²)

La complexité algorithmique ne posera pas de problèmes si l’on manipule des ensembles de données relativement petits, mais dès que ces ensembles grossiront le temps d’exécution deviendra trop long.

Le tri fusion tu béniras

L’autre solution qui me semble à la fois plus élégante et plus performante est d’utiliser le tri fusion (merge sort) fournis par le JDK. 
Concrètement il faut d’une part modifier notre DTO pour implémenter l’interface Comparable:

public class Stick implements Comparable<Stick> {

  private int length;  
  private String owner;  
  
  public Stick(int length, String owner) {  
    this.length = length;  
    this.owner = owner;  
  }  
  
  public int getLength() {  
    return length;  
  }  
  
  public String getOwner() {  
    return owner;  
  }  
  
  @Override  
  public String toString() {  
    return "Stick{" +  
            "length=" + length +  
            ", owner='" + owner + '\'' +  
            '}';  
  }  
  
  @Override  
  public int compareTo(Stick other) {  
    return Integer.compare(this.length, other.length);  
  }  
}

Enfin il suffit simplement d’appeler la méthode de tri :

List<Stick> sticks = new ArrayList<>();  
sticks.add(new Stick(12, "Yann"));  
sticks.add(new Stick(56, "Enora"));  
sticks.add(new Stick(8, "Katell"));  
sticks.add(new Stick(21, "Erwann"));  
  
Collections.sort(sticks); // utilisation du merge sort

Je trouve le code plus concis et en terme de performance on est sur du o(nlog(n)) grosso modo. Si vous voulez plus de détails je vous invite à consulter la javadoc de java.util.List :

This implementation is a stable, adaptive, iterative mergesort that  
requires far fewer than n lg(n) comparisons when the input array is  
partially sorted, while offering the performance of a traditional  
mergesort when the input array is randomly ordered.

Au final j’ai terminé à la 457ème place, en ayant buté sur l’exercice 4 en particulier. Mais j’ai adoré l’événement et j’ai hâte à la prochaine édition !
N’hésitez pas à me faire part de vos commentaires ou questions en bas de cet article ou en m’envoyant un message sur LinkedIn :
http://www.linkedin.com/in/jbleduigou/en.
Cet article a initialement été publié sur Medium.