Que signifie la caractéristique NON ORDONNÉE de Java 8 Collector?
Dans la documentation officielle, vous pouvez lire que:
UNORDEREDIndique que l'opération de collecte ne s'engage pas à préserver l'ordre de rencontre des éléments d'entrée.
Ce n'est pas trop utile, sans exemples.
Ma question est, que signifie exactement la caractéristique UNORDERED? Dois-je l'utiliser avec des collecteurs réducteurs comme min ou sum ou est-il uniquement applicable aux collecteurs de collection?
Dans OpenJDK ressemble à des opérations de réduction (min, sum, avg) ont des caractéristiques vides. Je m'attendais à y trouver au moins CONCURRENT et UNORDERED.
3 answers
UNORDERED signifie essentiellement que le collecteur est à la fois associatif (requis par la spécification) et commutatif (non requis).
L'associativité permet de diviser le calcul en sous-parties, puis de les combiner dans le résultat complet, mais nécessite que l'étape de combinaison soit strictement ordonnée. Examinez cet extrait du docs :
A a2 = supplier.get();
accumulator.accept(a2, t1);
A a3 = supplier.get();
accumulator.accept(a3, t2);
R r2 = finisher.apply(combiner.apply(a2, a3)); // result with splitting
Dans la dernière étape, combiner.apply(a2, a3) , les arguments doivent apparaître exactement dans cet ordre, ce qui signifie que tout le pipeline de calcul doit suivre l'ordre et le respecter à la fin.
Une autre façon de dire ceci est que l'arbre que nous obtenons du fractionnement récursif doit être ordonné.
En revanche, si l'opération de combinaison est commutative, on peut combiner n'importe quelle sous-partie avec n'importe quelle autre, sans ordre particulier, et obtenir toujours le même résultat. De toute évidence, cela conduit à de nombreuses opportunités d'optimisation dans les dimensions de l'espace et du temps.
Il convient de noter qu'il existe des UNORDERED collecteurs dans le JDK qui ne garantie commutativité. La catégorie principale sont les collecteurs "d'ordre supérieur" qui sont composés avec d'autres collecteurs en aval, mais ils n'appliquent pas la propriété UNORDERED sur eux.
En l'absence de plaidoirie spéciale, les opérations de flux doivent se comporter comme si les éléments étaient traités dans l'ordre de rencontre de la source. Pour certaines opérations - comme la réduction avec une opération associative-on peut obéir à cette contrainte tout en obtenant une exécution parallèle efficace. Pour d'autres, cependant, cette contrainte est très limitant. Et, pour certains problèmes, cette contrainte n'a pas de sens pour l'utilisateur. Considérons le pipeline de flux suivant:
people.stream()
.collect(groupingBy(Person::getLastName,
mapping(Person::getFirstName));
Est-il important que la liste des prénoms associés à "Smith" apparaît sur la carte dans l'ordre dans lequel ils sont apparus dans le flux initial? Pour certains problèmes, oui, pour d'autres non we nous ne voulons pas que la bibliothèque de flux devine pour nous. Un collecteur ordonné dit qu'il est correct d'insérer les prénoms dans la liste dans un ordre incompatible avec l'ordre dans lequel les personnes nommées Smith apparaissent dans la source d'entrée. En assouplissant cette contrainte, parfois (pas toujours), la bibliothèque de flux peut donner une exécution.
Par exemple, si vous ne vous souciez pas de cette conservation de l'ordre, vous pouvez l'exécuter comme:
people.parallelStream()
.collect(groupingByConcurrent(Person::getLastName,
mapping(Person::getFirstName));
Le collecteur concurrent n'est pas ordonné, ce qui permet l'optimisation du partage d'un ConcurrentMap sous-jacent, plutôt que d'avoir des étapes de fusion de mappage O(log n). Relâcher la contrainte de commande permet un réel avantage algorithmique but mais nous ne pouvons pas supposer que la contrainte n'a pas d'importance, nous avons besoin que l'utilisateur nous le dise. L'utilisation d'un collecteur UNORDERED est une façon de dire à la bibliothèque de flux que ces optimisations sont un jeu équitable.
L'intérieur Collector.Characteristics classe elle-même est assez laconique dans sa description, mais si vous passez quelques secondes à explorer le contexte, vous remarquerez que le contenant Collecteur interface fournit des informations supplémentaires
Pour les collecteurs qui n'ont pas la caractéristique NON ORDONNÉE, deux résultats cumulés a1 et a2 sont équivalents si finisseur.appliquer(a1).est égal à(l'unité de finition.appliquer(a2)). Pour les collecteurs non ordonnés, l'équivalence est assouplie pour permettre la non-égalité liée à les différences dans l'ordre. (Par exemple, un collecteur non ordonné qui a accumulé des éléments dans une liste considérerait deux listes équivalentes si elles contenaient les mêmes éléments, en ignorant l'ordre.)
Dans OpenJDK, on dirait que les opérations de réduction (min, sum, avg) ont des caractéristiques vides, je m'attendais à y trouver au moins SIMULTANÉES et NON ORDONNÉES.
Au moins pour les doubles la sommation et les moyennes sont définitivement ordonnées et non simultanées car la logique de sommation utilise fusion subresult, pas un accumulateur thread-safe.