Accueil / Articles PiApplications. / La plate-forme Java / Le langage

L'opération intermédiaire de réduction d'un stream.

L'opération de réduction est une opération intermédiaire fréquemment utilisée là ou la programmation impérative serait récursive. Pour éclairer ceci, nous nous posons le problème de trouver la taille de la chaîne la plus longue d'un fichier. Ceci n'est pas très difficile en programmation fonctionnelle :

Path pth = Paths.get("lines.txt");
int iLongestLineLength = Files.lines(pth)
 .mapToInt(String::length)
 .max()
 .getAsInt();

Le problème change de nature lorsque l'on demande de trouver quelle est la ligne la plus longue. On peut également trouver une réponse immédiate via la programmation fonctionnelle :

String longest = Files.lines(input)
 .sort((sL, sR) -> sR.length() - sL.length())
 .findFirst()
 .get();

Toutefois, en présence d'un très gros fichier, cette approche n'est pas efficace. En programmation impérative il y a deux familles de solutions :

  1. la programmation itérative ;
  2. la programmation récursive.

La programmation itérative est de la forme :

String sLongest = "";
while ((String s = reader.readLine()) != null)
 if (s.length() > sLongest.length())
   sLongest = s;

Cette approche sérielle ne permet pas une programmation multithread.

La programmation récursive est de la forme :

String findLongestString(String s, int iIndex, List lst)
{
 if (iIndex >= lst.size())
   return s;
 if (iIndex == lst.size() - 1)
 {
   if (s.length() > lst.get(iIndex).length())
     return s;
   return lst.get(iIndex);
 }
 String s2 = findLongestString(lst.get(iIndex), iIndex + 1, lst);
 if (s.length() > s2.length())
   return s;
 return s2;
}

Cette méthode supprime tout objet modifiable (la variable sLongest de la version itérative). Il n'y a plus non plus de boucle. Toutefois, toutes les lignes doivent avoir été lues et stockées dans une liste ce qui, outre l'aspect récursif, peut entrainer un débordement de mémoire (OutOfMemoryException).

Lorsque nous sommes en présence ou le résultat est obtenu par traitement successif d'un résultat intermédiaire (forme récursive), l'opération Optional<T> reduce(BinaryOperator<T> bopAccumulator) peut s'appliquer.

Dans notre exemple, le problème revient à trouver l'opérateur binaire approprié. Un opérateur binaire est une fonction qui admet deux opérandes de même type et produit un résultat de ce type. L'idée est ici de comparer chaque nouvel élément du flux au contenu de l'accumulateur et de modifier ce dernier en stockant le nouvel élément si sa longueur est plus grande. Ceci se fait via le code :

String longestLine = Files.lines(input)
 .reduce((sL, sR) ->
 {
   if (sR.length() > sL.length())
     return sL;
   return sR;
 })
 .get();

Comme on le constate, c'est la variable sL qui joue le rôle d'accumulateur en stockant chaque résultat intermédiaire. Le fichier est ici lu au fil de l'eau et les lignes ne sont plus stockées en mémoire. Le flux est en quelque sorte "réduit" progressivement à la ligne la plus grande.

Notez qu'il aurait été plus simple d'utiliser une forme particulière de l'opération max :

Files.lines(input)
 .max(comparingInt(String::length))
 .get();

Ceci montre que certaines opérations comme min ou max sont en fait des "réductions" typées. La réduction est souvent utilisée dans le contexte de recherche d'une valeur de caractéristique donnée.

(c) PiApplications 2016