Pourquoi les flux Java sont-ils uniques?

239

Contrairement à C # IEnumerable, où un pipeline d'exécution peut être exécuté autant de fois que nous le voulons, en Java, un flux ne peut être "itéré" qu'une seule fois.

Tout appel à une opération de terminal ferme le flux, le rendant inutilisable. Cette «fonctionnalité» enlève beaucoup de puissance.

J'imagine que la raison de cela n'est pas technique. Quelles étaient les considérations de conception derrière cette étrange restriction?

Edit: afin de démontrer de quoi je parle, considérez l'implémentation suivante de Quick-Sort en C #:

IEnumerable<int> QuickSort(IEnumerable<int> ints)
{
  if (!ints.Any()) {
    return Enumerable.Empty<int>();
  }

  int pivot = ints.First();

  IEnumerable<int> lt = ints.Where(i => i < pivot);
  IEnumerable<int> gt = ints.Where(i => i > pivot);

  return QuickSort(lt).Concat(new int[] { pivot }).Concat(QuickSort(gt));
}

Maintenant, pour être sûr, je ne préconise pas que ce soit une bonne mise en œuvre de tri rapide! C'est cependant un excellent exemple de la puissance expressive de l'expression lambda combinée à un fonctionnement en flux.

Et cela ne peut pas se faire en Java! Je ne peux même pas demander à un flux s'il est vide sans le rendre inutilisable.

Vitaliy
la source
4
Pourriez-vous donner un exemple concret où la fermeture du flux "enlève le pouvoir"?
Rogério
23
Si vous souhaitez utiliser les données d'un flux plusieurs fois, vous devrez les vider dans une collection. C'est à peu près comment cela doit fonctionner: soit vous devez refaire le calcul pour générer le flux, soit vous devez stocker le résultat intermédiaire.
Louis Wasserman
5
Ok, mais refaire le même calcul sur le même flux sonne mal. Un flux est créé à partir d'une source donnée avant qu'un calcul ne soit effectué, tout comme les itérateurs sont créés pour chaque itération. J'aimerais encore voir un exemple concret concret; à la fin, je parie qu'il existe un moyen propre de résoudre chaque problème avec les flux à utilisation unique, en supposant qu'il existe un moyen correspondant avec les énumérables de C #.
Rogério
2
Au début, c'était déroutant pour moi, car je pensais que cette question IEnumerablejava.io.*
relierait les
9
Notez que l'utilisation de IEnumerable plusieurs fois en C # est un modèle fragile, donc la prémisse de la question peut être légèrement erronée. De nombreuses implémentations de IEnumerable le permettent, mais certaines ne le permettent pas! Les outils d'analyse de code ont tendance à vous déconseiller de faire une telle chose.
Sander

Réponses:

368

J'ai quelques souvenirs de la conception initiale de l'API Streams qui pourraient éclairer la justification de la conception.

En 2012, nous ajoutions des lambdas au langage et nous voulions un ensemble d'opérations orientées collections ou «données en masse», programmées à l'aide de lambdas, qui faciliteraient le parallélisme. L'idée d'enchaîner les opérations paresseusement était bien établie à ce stade. Nous ne voulions pas non plus que les opérations intermédiaires stockent les résultats.

Les principaux problèmes dont nous avions besoin pour décider étaient à quoi ressemblaient les objets de la chaîne dans l'API et comment ils se connectaient aux sources de données. Les sources étaient souvent des collections, mais nous voulions également prendre en charge des données provenant d'un fichier ou du réseau, ou des données générées à la volée, par exemple, à partir d'un générateur de nombres aléatoires.

Il y avait de nombreuses influences du travail existant sur la conception. Parmi les plus influents se trouvaient la bibliothèque Google de Guava et la bibliothèque des collections Scala. (Si quelqu'un est surpris par l'influence de la goyave, notez que Kevin Bourrillion , développeur principal de la goyave, faisait partie du groupe d'experts JSR-335 Lambda .) Sur les collections Scala, nous avons trouvé cette conférence de Martin Odersky particulièrement intéressante: Future- Vérification des collections Scala: de Mutable à Persistant à Parallèle . (Stanford EE380, 1er juin 2011)

Notre conception de prototype à l'époque était basée sur Iterable. Les opérations familières filter, mapet ainsi de suite sont des méthodes d'extension (par défaut) sur Iterable. L'appel de l'un a ajouté une opération à la chaîne et en a renvoyé une autre Iterable. Une opération terminale comme celle countqui appelle iterator()la chaîne à la source, et les opérations ont été mises en œuvre dans l'itérateur de chaque étape.

Comme ce sont des Iterables, vous pouvez appeler la iterator()méthode plusieurs fois. Que devrait-il se passer alors?

Si la source est une collection, cela fonctionne généralement très bien. Les collections sont itérables et chaque appel à iterator()produit une instance d'itérateur distincte qui est indépendante de toute autre instance active, et chacune traverse la collection indépendamment. Génial.

Maintenant, que se passe-t-il si la source est à un coup, comme la lecture de lignes d'un fichier? Peut-être que le premier itérateur devrait obtenir toutes les valeurs, mais le second et les suivants devraient être vides. Peut-être que les valeurs devraient être entrelacées entre les itérateurs. Ou peut-être que chaque itérateur devrait avoir toutes les mêmes valeurs. Alors, que se passe-t-il si vous avez deux itérateurs et que l'un est plus avancé que l'autre? Quelqu'un devra mettre en mémoire tampon les valeurs dans le deuxième itérateur jusqu'à ce qu'elles soient lues. Pire, que se passe-t-il si vous obtenez un Iterator et lisez toutes les valeurs, et seulement alors obtenez un deuxième Iterator. D'où viennent les valeurs maintenant? Y a-t-il une exigence pour que tous soient mis en mémoire tampon au cas où quelqu'un voudrait un deuxième itérateur?

De toute évidence, autoriser plusieurs itérateurs sur une source ponctuelle soulève de nombreuses questions. Nous n'avions pas de bonnes réponses pour eux. Nous voulions un comportement cohérent et prévisible pour ce qui se passe si vous appelez iterator()deux fois. Cela nous a poussés à interdire les traversées multiples, ce qui rend les pipelines à un coup.

Nous avons également vu d'autres se heurter à ces problèmes. Dans le JDK, la plupart des Iterables sont des collections ou des objets de type collection, qui permettent une traversée multiple. Il n'est spécifié nulle part, mais il semble y avoir une attente non écrite selon laquelle les Iterables autorisent une traversée multiple. Une exception notable est l' interface NIO DirectoryStream . Sa spécification inclut cet avertissement intéressant:

Bien que DirectoryStream étende Iterable, il ne s'agit pas d'un Iterable à usage général car il ne prend en charge qu'un seul Iterator; l'appel de la méthode itérateur pour obtenir un deuxième itérateur ou un itérateur suivant lève IllegalStateException.

[gras dans l'original]

Cela semblait assez inhabituel et désagréable pour que nous ne voulions pas créer tout un tas de nouveaux Iterables qui pourraient être une seule fois. Cela nous a éloignés de l'utilisation d'Iterable.

À cette époque, un article de Bruce Eckel est apparu décrivant un problème qu'il avait eu avec Scala. Il avait écrit ce code:

// Scala
val lines = fromString(data).getLines
val registrants = lines.map(Registrant)
registrants.foreach(println)
registrants.foreach(println)

C'est assez simple. Il analyse les lignes de texte en Registrantobjets et les imprime deux fois. Sauf qu'il ne les imprime qu'une seule fois. Il s'avère qu'il pensait que registrantsc'était une collection, alors qu'en fait c'est un itérateur. Le deuxième appel à foreachrencontre un itérateur vide, dont toutes les valeurs ont été épuisées, il n'imprime donc rien.

Ce type d'expérience nous a convaincus qu'il était très important d'avoir des résultats clairement prévisibles en cas de tentative de traversée multiple. Il a également souligné l'importance de distinguer les structures de type pipeline paresseux des collections réelles qui stockent des données. À son tour, cela a conduit à la séparation des opérations de pipeline paresseux dans la nouvelle interface Stream et à ne conserver que des opérations mutantes avides directement sur les collections. Brian Goetz a expliqué la raison de cela.

Qu'en est-il d'autoriser la traversée multiple pour les pipelines basés sur la collecte mais de l'interdire pour les pipelines non basés sur la collecte? C'est incohérent, mais c'est raisonnable. Si vous lisez des valeurs sur le réseau, vous ne pouvez bien sûr pas les parcourir à nouveau. Si vous souhaitez les parcourir plusieurs fois, vous devez les tirer explicitement dans une collection.

Mais explorons la possibilité de traverser plusieurs fois à partir de pipelines basés sur des collections. Disons que vous avez fait ceci:

Iterable<?> it = source.filter(...).map(...).filter(...).map(...);
it.into(dest1);
it.into(dest2);

(L' intoopération est maintenant orthographiée collect(toList()).)

Si la source est une collection, le premier into()appel créera une chaîne d'itérateurs vers la source, exécutera les opérations de pipeline et enverra les résultats à la destination. Le deuxième appel à into()créera une autre chaîne d'itérateurs et exécutera à nouveau les opérations de pipeline . Ce n'est évidemment pas faux, mais cela a pour effet d'effectuer toutes les opérations de filtrage et de mappage une deuxième fois pour chaque élément. Je pense que de nombreux programmeurs auraient été surpris par ce comportement.

Comme je l'ai mentionné ci-dessus, nous avions parlé aux développeurs de Guava. L'une des choses sympas qu'ils ont est un cimetière d'idées où ils décrivent des fonctionnalités qu'ils ont décidé de ne pas implémenter avec les raisons. L'idée de collections paresseuses semble plutôt cool, mais voici ce qu'elles en disent. Considérons une List.filter()opération qui renvoie un List:

La plus grande préoccupation ici est que trop d'opérations deviennent des propositions coûteuses en temps linéaire. Si vous souhaitez filtrer une liste et récupérer une liste, et pas seulement une collection ou un Iterable, vous pouvez utiliser ImmutableList.copyOf(Iterables.filter(list, predicate))ce qui "indique à l'avance" ce qu'il fait et son coût.

Pour prendre un exemple spécifique, quel est le coût de get(0)ou size()sur une liste? Pour les classes couramment utilisées comme ArrayList, elles sont O (1). Mais si vous appelez l'un de ces éléments sur une liste filtrée paresseusement, il doit exécuter le filtre sur la liste de sauvegarde, et tout à coup, ces opérations sont O (n). Pire, il doit parcourir la liste de sauvegarde à chaque opération.

Cela nous semblait trop de paresse. C'est une chose de mettre en place certaines opérations et de différer l'exécution jusqu'à ce que vous "Go". C'est une autre façon de configurer les choses de manière à masquer une quantité potentiellement importante de recalcul.

En proposant de interdire les flux non linéaires ou "sans réutilisation", Paul Sandoz a décrit les conséquences potentielles de leur autorisation comme donnant lieu à "des résultats inattendus ou déroutants". Il a également mentionné que l'exécution parallèle rendrait les choses encore plus difficiles. Enfin, j'ajouterais qu'une opération de pipeline avec des effets secondaires entraînerait des bogues difficiles et obscurs si l'opération était exécutée de manière inattendue plusieurs fois, ou au moins un nombre de fois différent de celui prévu par le programmeur. (Mais les programmeurs Java n'écrivent pas d'expressions lambda avec des effets secondaires, n'est-ce pas?

C'est donc la raison d'être de la conception de l'API Java 8 Streams qui permet une traversée en une seule fois et qui nécessite un pipeline strictement linéaire (sans branchement). Il fournit un comportement cohérent sur plusieurs sources de flux différentes, il sépare clairement les opérations paresseuses des opérations ardues et il fournit un modèle d'exécution simple.


En ce qui concerne IEnumerable, je suis loin d'être un expert en C # et .NET, donc j'apprécierais d'être corrigé (doucement) si je tire des conclusions incorrectes. Il semble cependant que IEnumerableles traversées multiples se comportent différemment avec différentes sources; et il permet une structure de branchement des IEnumerableopérations imbriquées , ce qui peut entraîner un recalcul important. Bien que j'apprécie que différents systèmes fassent des compromis différents, ce sont deux caractéristiques que nous avons cherché à éviter dans la conception de l'API Java 8 Streams.

L'exemple de tri rapide donné par l'OP est intéressant, déroutant, et je suis désolé de le dire, quelque peu horrible. L'appel QuickSortprend un IEnumerableet retourne un IEnumerable, donc aucun tri n'est fait jusqu'à ce que la finale IEnumerablesoit traversée. Cependant, ce que l'appel semble faire, c'est construire une structure arborescente IEnumerablesqui reflète le partitionnement que le tri rapide ferait, sans le faire réellement. (C'est du calcul paresseux, après tout.) Si la source a N éléments, l'arborescence sera N éléments large à son plus large, et ce sera lg (N) niveaux profonds.

Il me semble - et encore une fois, je ne suis pas un expert C # ou .NET - que cela rendra certains appels d'apparence anodine, tels que la sélection de pivot via ints.First(), plus chers qu'ils ne le paraissent. Au premier niveau, bien sûr, c'est O (1). Mais considérons une partition profondément dans l'arborescence, sur le bord droit. Pour calculer le premier élément de cette partition, toute la source doit être traversée, une opération O (N). Mais comme les partitions ci-dessus sont paresseuses, elles doivent être recalculées, nécessitant des comparaisons O (lg N). La sélection du pivot serait donc une opération O (N lg N), qui est aussi coûteuse qu'un tri entier.

Mais nous ne trions pas réellement jusqu'à ce que nous traversions le retour IEnumerable. Dans l'algorithme de tri rapide standard, chaque niveau de partitionnement double le nombre de partitions. Chaque partition ne fait que la moitié de la taille, donc chaque niveau reste à la complexité O (N). L'arbre des partitions est O (lg N) élevé, donc le travail total est O (N lg N).

Avec l'arborescence des IEnumerables paresseux, au bas de l'arborescence il y a N partitions. Le calcul de chaque partition nécessite une traversée de N éléments, chacun nécessitant des comparaisons lg (N) dans l'arborescence. Pour calculer toutes les partitions au bas de l'arborescence, il faut alors des comparaisons O (N ^ 2 lg N).

(Est-ce vrai? Je peux à peine y croire. Quelqu'un, veuillez vérifier cela pour moi.)

En tout cas, c'est en effet cool que l' IEnumerableon puisse utiliser de cette façon pour construire des structures de calcul compliquées. Mais si cela augmente la complexité de calcul autant que je le pense, il semblerait que la programmation de cette façon soit quelque chose qui devrait être évitée à moins d'être extrêmement prudent.

Stuart Marks
la source
35
Tout d'abord, merci pour la réponse excellente et non condescendante! C'est de loin l'explication la plus précise et la plus précise que j'ai eue. En ce qui concerne l'exemple QuickSort, il semble que vous ayez raison en ce qui concerne les pouces. Premièrement, ballonnements à mesure que le niveau de récursivité augmente. Je crois que cela peut être facilement corrigé en calculant 'gt' et 'lt' avec impatience (en collectant les résultats avec ToArray). Cela étant dit, cela confirme certainement votre point de vue selon lequel ce style de programmation peut entraîner des prix de performance inattendus. (Continuer dans le deuxième commentaire)
Vitaliy
18
D'un autre côté, d'après mon expérience avec C # (plus de 5 ans), je peux dire que l'élimination des calculs `` redondants '' n'est pas si difficile une fois que vous avez rencontré un problème de performance (ou obtenu une interdiction, si quelqu'un a rendu l'impensable et a introduit un côté y affecter). Il m'a simplement semblé que trop de compromis avaient été faits pour garantir la pureté de l'API, au détriment des possibilités de type C #. Vous m'avez certainement aidé à ajuster mon point de vue.
Vitaliy
7
@Vitaliy Merci pour cet échange d'idées équitable. J'ai appris un peu sur C # et .NET en étudiant et en écrivant cette réponse.
Stuart marque le
10
Petit commentaire: ReSharper est une extension Visual Studio qui aide avec C #. Avec le code QuickSort ci-dessus, ReSharper ajoute un avertissement pour chaque utilisationints : "Énumération multiple possible de IEnumerable". Les utiliser IEenumerableplusieurs fois est suspect et doit être évité. Je voudrais également souligner cette question (à laquelle j'ai répondu), qui montre certaines des mises en garde avec l'approche .Net (en plus des performances médiocres): Liste <T> et différence IEnumerable
Kobi
4
@Kobi Très intéressant qu'il y ait un tel avertissement dans ReSharper. Merci pour le pointeur vers votre réponse. Je ne connais pas C # /. NET donc je vais devoir le parcourir attentivement, mais il semble présenter des problèmes similaires aux problèmes de conception que j'ai mentionnés ci-dessus.
Stuart marque
122

Contexte

Bien que la question semble simple, la réponse réelle nécessite quelques informations pour avoir un sens. Si vous voulez passer à la conclusion, faites défiler vers le bas ...

Choisissez votre point de comparaison - Fonctionnalité de base

En utilisant des concepts de base, le concept de C # IEnumerableest plus étroitement lié à JavaIterable , qui est capable de créer autant d' itérateurs que vous le souhaitez. IEnumerablescréer IEnumerators. Java de IterablecréerIterators

L'histoire de chaque concept est similaire, dans la mesure où les deux IEnumerableet Iterableont une motivation de base pour permettre une boucle de style «pour chacun» sur les membres des collections de données. C'est une simplification excessive car ils permettent tous les deux plus que cela, et ils sont également arrivés à ce stade via différentes progressions, mais c'est une caractéristique commune importante malgré tout.

Comparons cette fonctionnalité: dans les deux langages, si une classe implémente le IEnumerable/ Iterable, alors cette classe doit implémenter au moins une seule méthode (pour C #, c'est GetEnumeratoret pour Java c'est iterator()). Dans chaque cas, l'instance renvoyée à partir de ce ( IEnumerator/ Iterator) vous permet d'accéder aux membres actuels et suivants des données. Cette fonctionnalité est utilisée dans la syntaxe de langue pour chaque.

Choisissez votre point de comparaison - Fonctionnalité améliorée

IEnumerableen C # a été étendu pour permettre un certain nombre d'autres fonctionnalités de langage ( principalement liées à Linq ). Les fonctionnalités ajoutées incluent des sélections, des projections, des agrégations, etc.

Java 8 a également ajouté des fonctionnalités pour permettre un certain degré de programmation fonctionnelle à l'aide de Streams et Lambdas. Notez que les flux Java 8 ne sont pas principalement motivés par la théorie des ensembles, mais par la programmation fonctionnelle. Quoi qu'il en soit, il existe de nombreux parallèles.

Donc, c'est le deuxième point. Les améliorations apportées à C # ont été implémentées comme une amélioration du IEnumerableconcept. En Java, cependant, les améliorations apportées ont été mises en œuvre en créant de nouveaux concepts de base de Lambdas et Streams, puis en créant également un moyen relativement trivial de convertir depuis Iteratorset Iterablesvers Streams, et vice-versa.

Donc, comparer IEnumerable au concept Stream de Java est incomplet. Vous devez le comparer aux API combinées Streams et Collections en Java.

En Java, les flux ne sont pas identiques aux Iterables ou aux itérateurs

Les flux ne sont pas conçus pour résoudre les problèmes de la même manière que les itérateurs:

  • Les itérateurs sont un moyen de décrire la séquence de données.
  • Les flux sont un moyen de décrire une séquence de transformations de données.

Avec un Iterator, vous obtenez une valeur de données, la traitez, puis obtenez une autre valeur de données.

Avec Streams, vous enchaînez une séquence de fonctions ensemble, puis vous introduisez une valeur d'entrée dans le flux et obtenez la valeur de sortie de la séquence combinée. Notez qu'en termes Java, chaque fonction est encapsulée dans une seule Streaminstance. L'API Streams vous permet de lier une séquence d' Streaminstances de manière à enchaîner une séquence d'expressions de transformation.

Pour compléter le Streamconcept, vous avez besoin d'une source de données pour alimenter le flux et d'une fonction de terminal qui consomme le flux.

La façon dont vous introduisez des valeurs dans le flux peut en fait provenir d'un Iterable, mais la Streamséquence elle-même n'est pas un Iterable, c'est une fonction composée.

A Streamest également destiné à être paresseux, en ce sens qu'il ne fonctionne que lorsque vous lui demandez une valeur.

Notez ces hypothèses et caractéristiques importantes de Streams:

  • Un StreamJava est un moteur de transformation, il transforme un élément de données dans un état, en étant dans un autre état.
  • les flux n'ont aucune notion de l'ordre ou de la position des données, ils transforment simplement tout ce qui leur est demandé.
  • les flux peuvent être fournis avec des données provenant de nombreuses sources, y compris d'autres flux, les itérateurs, les itérables, les collections,
  • vous ne pouvez pas "réinitialiser" un flux, ce serait comme "reprogrammer la transformation". La réinitialisation de la source de données est probablement ce que vous voulez.
  • il n'y a logiquement qu'un seul élément de données «en vol» dans le flux à tout moment (sauf si le flux est un flux parallèle, auquel cas, il y a 1 élément par thread). Cela est indépendant de la source de données qui peut avoir plus que les éléments actuels «prêts» à être fournis au flux, ou du collecteur de flux qui peut avoir besoin d'agréger et de réduire plusieurs valeurs.
  • Les flux peuvent être non liés (infinis), limités uniquement par la source de données ou le collecteur (qui peut également être infini).
  • Les flux sont «chaînables», la sortie du filtrage d'un flux est un autre flux. Les valeurs entrées et transformées par un flux peuvent à leur tour être fournies à un autre flux qui effectue une transformation différente. Les données, dans leur état transformé, circulent d'un flux à l'autre. Vous n'avez pas besoin d'intervenir et d'extraire les données d'un flux et de les connecter au suivant.

Comparaison C #

Lorsque vous considérez qu'un flux Java n'est qu'une partie d'un système d'approvisionnement, de flux et de collecte, et que les flux et les itérateurs sont souvent utilisés avec des collections, il n'est pas étonnant qu'il soit difficile de se rapporter aux mêmes concepts qui sont presque tous intégrés dans un seul IEnumerableconcept en C #.

Des parties de IEnumerable (et des concepts proches) sont visibles dans tous les concepts Java Iterator, Iterable, Lambda et Stream.

Il y a de petites choses que les concepts Java peuvent faire qui sont plus difficiles dans IEnumerable, et vice-versa.


Conclusion

  • Il n'y a pas de problème de conception ici, juste un problème de correspondance des concepts entre les langues.
  • Les flux résolvent les problèmes d'une manière différente
  • Les flux ajoutent des fonctionnalités à Java (ils ajoutent une manière différente de faire les choses, ils n'enlèvent rien à la fonctionnalité)

L'ajout de Streams vous donne plus de choix lors de la résolution de problèmes, ce qui est juste à classer comme «augmenter le pouvoir», pas «le réduire», le «retirer» ou le «restreindre».

Pourquoi les flux Java sont-ils uniques?

Cette question est erronée, car les flux sont des séquences de fonctions, pas des données. Selon la source de données qui alimente le flux, vous pouvez réinitialiser la source de données et alimenter le même flux ou un flux différent.

Contrairement à IEnumerable de C #, où un pipeline d'exécution peut être exécuté autant de fois que nous le voulons, en Java, un flux ne peut être "itéré" qu'une seule fois.

Comparer un IEnumerableà un Streamest erroné. Le contexte que vous utilisez pour dire IEnumerablepeut être exécuté autant de fois que vous le souhaitez, mieux que Java Iterables, qui peut être répété autant de fois que vous le souhaitez. Un Java Streamreprésente un sous-ensemble du IEnumerableconcept, et non le sous-ensemble qui fournit des données, et ne peut donc pas être «réexécuté».

Tout appel à une opération de terminal ferme le flux, le rendant inutilisable. Cette «fonctionnalité» enlève beaucoup de puissance.

La première affirmation est vraie, dans un sens. La déclaration «emporte le pouvoir» ne l'est pas. Vous comparez toujours Streams it IEnumerables. L'opération de terminal dans le flux est comme une clause de «rupture» dans une boucle for. Vous êtes toujours libre d'avoir un autre flux, si vous le souhaitez, et si vous pouvez fournir à nouveau les données dont vous avez besoin. Encore une fois, si vous considérez que IEnumerablecela ressemble plus à un Iterable, pour cette déclaration, Java le fait très bien.

J'imagine que la raison de cela n'est pas technique. Quelles étaient les considérations de conception derrière cette étrange restriction?

La raison est technique, et pour la simple raison qu'un Stream est un sous-ensemble de ce qu'il pense. Le sous-ensemble de flux ne contrôle pas la fourniture de données, vous devez donc réinitialiser la fourniture, pas le flux. Dans ce contexte, ce n'est pas si étrange.

Exemple QuickSort

Votre exemple de tri rapide a la signature:

IEnumerable<int> QuickSort(IEnumerable<int> ints)

Vous traitez l'entrée IEnumerablecomme une source de données:

IEnumerable<int> lt = ints.Where(i => i < pivot);

De plus, la valeur de retour est IEnumerableégalement, qui est une fourniture de données, et puisqu'il s'agit d'une opération de tri, l'ordre de cette fourniture est important. Si vous considérez que la Iterableclasse Java est la correspondance appropriée pour cela, en particulier la Listspécialisation de Iterable, puisque List est une fourniture de données qui a un ordre ou une itération garantis, alors le code Java équivalent à votre code serait:

Stream<Integer> quickSort(List<Integer> ints) {
    // Using a stream to access the data, instead of the simpler ints.isEmpty()
    if (!ints.stream().findAny().isPresent()) {
        return Stream.of();
    }

    // treating the ints as a data collection, just like the C#
    final Integer pivot = ints.get(0);

    // Using streams to get the two partitions
    List<Integer> lt = ints.stream().filter(i -> i < pivot).collect(Collectors.toList());
    List<Integer> gt = ints.stream().filter(i -> i > pivot).collect(Collectors.toList());

    return Stream.concat(Stream.concat(quickSort(lt), Stream.of(pivot)),quickSort(gt));
}    

Notez qu'il y a un bug (que j'ai reproduit), dans la mesure où le tri ne gère pas les valeurs en double avec élégance, il s'agit d'un tri de «valeur unique».

Notez également comment le code Java utilise la source de données ( List) et les concepts de flux à différents points, et qu'en C # ces deux «personnalités» peuvent être exprimées en juste IEnumerable. De plus, bien que j'aie utilisé Listcomme type de base, j'aurais pu utiliser le plus général Collection, et avec une petite conversion d'itérateur en flux, j'aurais pu utiliser le plus généralIterable

rolfl
la source
9
Si vous songez à «itérer» un flux, vous le faites mal. Un flux représente l'état des données à un moment donné dans une chaîne de transformations. Les données pénètrent dans le système dans une source de flux, puis circulent d'un flux au suivant, changeant d'état au fur et à mesure, jusqu'à ce qu'elles soient collectées, réduites ou vidées, à la fin. A Streamest un concept ponctuel, pas une «opération en boucle» .... (suite)
rolfl
7
Avec un flux, vous avez des données entrant dans le flux ressemblant à X et sortant du flux ressemblant à Y. Il existe une fonction que le flux fait qui effectue cette transformation.Le f(x)flux encapsule la fonction, il n'encapsule pas les données qui transitent
rolfl
4
IEnumerablepeut également fournir des valeurs aléatoires, être non lié et devenir actif avant que les données existent.
Arturo Torres Sánchez
6
@Vitaliy: De nombreuses méthodes qui reçoivent un IEnumerable<T>s'attendent à ce qu'il représente une collection finie qui peut être répétée plusieurs fois. Certaines choses qui sont itérables mais ne remplissent pas ces conditions sont mises en œuvre IEnumerable<T>car aucune autre interface standard ne correspond à la loi, mais les méthodes qui attendent des collections finies qui peuvent être itérées plusieurs fois sont sujettes à planter si on leur donne des choses itérables qui ne respectent pas ces conditions .
supercat
5
Votre quickSortexemple pourrait être beaucoup plus simple s'il renvoyait un Stream; cela économiserait deux .stream()appels et un .collect(Collectors.toList())appel. Si vous remplacez ensuite Collections.singleton(pivot).stream()avec Stream.of(pivot)le code devient presque lisible…
Holger
22

Streamles s sont construits autour de Spliterators qui sont des objets mutables avec état. Ils n'ont pas d'action de «réinitialisation» et en fait, exiger de soutenir une telle action de rembobinage «enlèverait beaucoup de pouvoir». Comment serait Random.ints()censé traiter une telle demande?

En revanche, pour les Streams qui ont une origine rétractable, il est facile de construire un équivalent Streamà réutiliser. Mettez simplement les étapes faites pour construire le Streamdans une méthode réutilisable. Gardez à l'esprit que la répétition de ces étapes n'est pas une opération coûteuse car toutes ces étapes sont des opérations paresseuses; le travail réel commence par l'opération de terminal et, en fonction de l'opération de terminal réelle, un code entièrement différent peut être exécuté.

Il appartiendrait à vous, l'auteur d'une telle méthode, de spécifier ce qu'impliquer l'appel de la méthode deux fois: reproduit-il exactement la même séquence, comme le font les flux créés pour un tableau ou une collection non modifié, ou produit-il un flux avec un sémantique similaire mais éléments différents comme un flux d'entrées aléatoires ou un flux de lignes d'entrée de console, etc.


Soit dit en passant, pour éviter toute confusion, une opération de terminal consomme ce Streamqui est distinct de la fermeture de ce Streamque fait l'appel close()sur le flux (ce qui est requis pour les flux ayant des ressources associées comme, par exemple, produites par Files.lines()).


Il semble que beaucoup de confusion découle d'une comparaison erronée de IEnumerableavec Stream. Un IEnumerablereprésente la capacité de fournir un réel IEnumerator, donc c'est comme un IterableJava. En revanche, a Streamest une sorte d'itérateur et comparable à un IEnumerator, il est donc faux de prétendre que ce type de type de données peut être utilisé plusieurs fois dans .NET, la prise en charge de IEnumerator.Resetest facultative. Les exemples discutés ici utilisent plutôt le fait que an IEnumerablepeut être utilisé pour récupérer de nouveaux IEnumerator s et qui fonctionne également avec les Collections de Java ; vous pouvez en obtenir un nouveau Stream. Si les développeurs Java décidaient d'ajouter directement les Streamopérations Iterable, les opérations intermédiaires renvoyant une autreIterable, c'était vraiment comparable et cela pouvait fonctionner de la même manière.

Cependant, les développeurs se sont prononcés contre et la décision est discutée dans cette question . Le plus gros point est la confusion concernant les opérations de collecte enthousiastes et les opérations de flux paresseux. En regardant l'API .NET, je (oui, personnellement) la trouve justifiée. Bien qu'il semble raisonnable de regarder IEnumerableseul, une collection particulière aura beaucoup de méthodes manipulant directement la collection et beaucoup de méthodes renvoyant un paresseux IEnumerable, tandis que la nature particulière d'une méthode n'est pas toujours intuitivement reconnaissable. Le pire exemple que j'ai trouvé (dans les quelques minutes où je l'ai regardé) est List.Reverse()dont le nom correspond exactement au nom de l'héritage (est-ce le bon terminus pour les méthodes d'extension?) Enumerable.Reverse()Tout en ayant un comportement entièrement contradictoire.


Bien sûr, ce sont deux décisions distinctes. Le premier à faire Streamun type distinct de Iterable/ Collectionet le second à faire Streamune sorte d'itérateur ponctuel plutôt qu'un autre type d'itérable. Mais ces décisions ont été prises ensemble et il se pourrait que la séparation de ces deux décisions n'ait jamais été envisagée. Il n'a pas été créé en étant comparable à celui de .NET.

La décision de conception de l'API a été d'ajouter un type d'itérateur amélioré, le Spliterator. SpliteratorLes s peuvent être fournis par les anciens Iterables (ce qui est la façon dont ils ont été mis à niveau) ou des implémentations entièrement nouvelles. Ensuite, a Streamété ajouté en tant que frontal de haut niveau au niveau plutôt bas Spliterator. C'est tout. Vous pouvez discuter de savoir si une conception différente serait meilleure, mais ce n'est pas productif, cela ne changera pas, compte tenu de la façon dont ils sont conçus maintenant.

Il y a un autre aspect de mise en œuvre que vous devez considérer. Streams ne sont pas des structures de données immuables. Chaque opération intermédiaire peut renvoyer une nouvelle Streaminstance encapsulant l'ancienne mais elle peut également manipuler sa propre instance à la place et se retourner (cela n'empêche pas de faire même les deux pour la même opération). Des exemples connus sont des opérations comme parallelou unorderedqui n'ajoutent pas une autre étape mais manipulent l'ensemble du pipeline). Avoir une telle structure de données mutable et tenter de réutiliser (ou pire encore, l'utiliser plusieurs fois en même temps) ne fonctionne pas bien…


Pour être complet, voici votre exemple de tri rapide traduit dans l' StreamAPI Java . Cela montre que cela «n'enlève pas vraiment beaucoup de pouvoir».

static Stream<Integer> quickSort(Supplier<Stream<Integer>> ints) {

  final Optional<Integer> optPivot = ints.get().findAny();
  if(!optPivot.isPresent()) return Stream.empty();

  final int pivot = optPivot.get();

  Supplier<Stream<Integer>> lt = ()->ints.get().filter(i -> i < pivot);
  Supplier<Stream<Integer>> gt = ()->ints.get().filter(i -> i > pivot);

  return Stream.of(quickSort(lt), Stream.of(pivot), quickSort(gt)).flatMap(s->s);
}

Il peut être utilisé comme

List<Integer> l=new Random().ints(100, 0, 1000).boxed().collect(Collectors.toList());
System.out.println(l);
System.out.println(quickSort(l::stream)
    .map(Object::toString).collect(Collectors.joining(", ")));

Vous pouvez l'écrire encore plus compact comme

static Stream<Integer> quickSort(Supplier<Stream<Integer>> ints) {
    return ints.get().findAny().map(pivot ->
         Stream.of(
                   quickSort(()->ints.get().filter(i -> i < pivot)),
                   Stream.of(pivot),
                   quickSort(()->ints.get().filter(i -> i > pivot)))
        .flatMap(s->s)).orElse(Stream.empty());
}
Holger
la source
1
Eh bien, consomme ou non, essayer de le consommer à nouveau jette une exception que le flux était déjà fermé , non consommé. Quant au problème de réinitialisation d'un flux d'entiers aléatoires, comme vous l'avez dit, c'est au rédacteur de la bibliothèque de définir le contrat exact d'une opération de réinitialisation.
Vitaliy
2
Non, le message est «le flux a déjà été opéré ou fermé» et nous ne parlions pas d'une opération de «réinitialisation» mais d'appeler deux opérations de terminal ou plus, Streamalors que la réinitialisation des sources Spliteratorserait implicite. Et je suis sûr que si c'était possible, il y avait une question sur SO comme "Pourquoi est-ce que le fait d'appeler count()deux fois sur un Streamdonne des résultats différents à chaque fois", etc…
Holger
1
Il est absolument valable pour count () de donner des résultats différents. count () est une requête sur un flux, et si le flux est mutable (ou pour être plus exact, le flux représente le résultat d'une requête sur une collection mutable), alors il est attendu. Jetez un œil à l'API de C #. Ils traitent gracieusement toutes ces questions.
Vitaliy
4
Ce que vous appelez «absolument valable» est un comportement contre-intuitif. Après tout, c'est la principale motivation pour demander à utiliser un flux plusieurs fois pour traiter le résultat, qui devrait être le même, de différentes manières. Chaque question sur SO à propos de la nature non réutilisable de Streams jusqu'à présent provient d'une tentative de résoudre un problème en appelant plusieurs fois les opérations du terminal (évidemment, sinon vous ne le remarquez pas), ce qui a conduit à une solution silencieuse si l' StreamAPI le permettait. avec des résultats différents à chaque évaluation. Voici un bel exemple .
Holger
3
En fait, votre exemple montre parfaitement ce qui se passe si un programmeur ne comprend pas les implications de l'application de plusieurs opérations de terminal. Pensez simplement à ce qui se passe lorsque chacune de ces opérations sera appliquée à un ensemble d'éléments entièrement différent. Cela ne fonctionne que si la source du flux a renvoyé les mêmes éléments à chaque requête, mais c'est exactement la mauvaise hypothèse dont nous parlions.
Holger
8

Je pense qu'il y a très peu de différences entre les deux quand on regarde de près.

À première vue, un IEnumerablesemble être une construction réutilisable:

IEnumerable<int> numbers = new int[] { 1, 2, 3, 4, 5 };

foreach (var n in numbers) {
    Console.WriteLine(n);
}

Cependant, le compilateur fait actuellement un peu de travail pour nous aider; il génère le code suivant:

IEnumerable<int> numbers = new int[] { 1, 2, 3, 4, 5 };

IEnumerator<int> enumerator = numbers.GetEnumerator();
while (enumerator.MoveNext()) {
    Console.WriteLine(enumerator.Current);
}

Chaque fois que vous effectuez une itération sur l'énumérable, le compilateur crée un énumérateur. L'énumérateur n'est pas réutilisable; d'autres appels à MoveNextretourneront simplement faux, et il n'y a aucun moyen de le réinitialiser au début. Si vous souhaitez réitérer les nombres, vous devrez créer une autre instance d'énumérateur.


Pour mieux illustrer que l'IEnumerable a (peut avoir) la même «fonctionnalité» qu'un Java Stream, considérons un énumérable dont la source des nombres n'est pas une collection statique. Par exemple, nous pouvons créer un objet énumérable qui génère une séquence de 5 nombres aléatoires:

class Generator : IEnumerator<int> {
    Random _r;
    int _current;
    int _count = 0;

    public Generator(Random r) {
        _r = r;
    }

    public bool MoveNext() {
        _current= _r.Next();
        _count++;
        return _count <= 5;
    }

    public int Current {
        get { return _current; }
    }
 }

class RandomNumberStream : IEnumerable<int> {
    Random _r = new Random();
    public IEnumerator<int> GetEnumerator() {
        return new Generator(_r);
    }
    public IEnumerator IEnumerable.GetEnumerator() {
        return this.GetEnumerator();
    }
}

Maintenant, nous avons un code très similaire à l'énumérable précédent basé sur un tableau, mais avec une deuxième itération sur numbers:

IEnumerable<int> numbers = new RandomNumberStream();

foreach (var n in numbers) {
    Console.WriteLine(n);
}
foreach (var n in numbers) {
    Console.WriteLine(n);
}

La deuxième fois que nous répétons, numbersnous obtiendrons une séquence de nombres différente, qui n'est pas réutilisable dans le même sens. Ou, nous aurions pu écrire le RandomNumberStreampour lever une exception si vous essayez de l'itérer plusieurs fois, rendant l'énumérable réellement inutilisable (comme un Java Stream).

En outre, que signifie votre tri rapide basé sur les énumérations lorsqu'il est appliqué à un RandomNumberStream?


Conclusion

Ainsi, la plus grande différence est que .NET vous permet de réutiliser un IEnumerableen créant implicitement un nouveau IEnumeratoren arrière-plan chaque fois qu'il aura besoin d'accéder aux éléments de la séquence.

Ce comportement implicite est souvent utile (et «puissant» comme vous le dites), car nous pouvons répéter de manière répétée une collection.

Mais parfois, ce comportement implicite peut en fait causer des problèmes. Si votre source de données n'est pas statique ou si son accès est coûteux (comme une base de données ou un site Web), alors beaucoup d'hypothèses IEnumerabledoivent être rejetées; la réutilisation n'est pas si simple

Andrew Vermie
la source
2

Il est possible de contourner certaines des protections «à exécution unique» dans l'API Stream; par exemple, nous pouvons éviter les java.lang.IllegalStateExceptionexceptions (avec le message "le flux a déjà été opéré ou fermé") en référençant et en réutilisant le Spliterator(plutôt que Streamdirectement).

Par exemple, ce code s'exécutera sans lever d'exception:

    Spliterator<String> split = Stream.of("hello","world")
                                      .map(s->"prefix-"+s)
                                      .spliterator();

    Stream<String> replayable1 = StreamSupport.stream(split,false);
    Stream<String> replayable2 = StreamSupport.stream(split,false);


    replayable1.forEach(System.out::println);
    replayable2.forEach(System.out::println);

Cependant, la sortie sera limitée à

prefix-hello
prefix-world

plutôt que de répéter la sortie deux fois. Cela est dû au fait ArraySpliteratorque la Streamsource utilisée est avec état et stocke sa position actuelle. Lorsque nous rejouons cela, Streamnous recommençons à la fin.

Nous avons plusieurs options pour résoudre ce défi:

  1. Nous pourrions utiliser une Streamméthode de création sans état telle que Stream#generate(). Il faudrait gérer l'état en externe dans notre propre code et réinitialiser entre les Stream"replays":

    Spliterator<String> split = Stream.generate(this::nextValue)
                                      .map(s->"prefix-"+s)
                                      .spliterator();
    
    Stream<String> replayable1 = StreamSupport.stream(split,false);
    Stream<String> replayable2 = StreamSupport.stream(split,false);
    
    
    replayable1.forEach(System.out::println);
    this.resetCounter();
    replayable2.forEach(System.out::println);
  2. Une autre solution (légèrement meilleure mais pas parfaite) est d'écrire notre propre ArraySpliterator(ou une Streamsource similaire ) qui inclut une certaine capacité pour réinitialiser le compteur actuel. Si nous devions l'utiliser pour générer le, Streamnous pourrions potentiellement les rejouer avec succès.

    MyArraySpliterator<String> arraySplit = new MyArraySpliterator("hello","world");
    Spliterator<String> split = StreamSupport.stream(arraySplit,false)
                                            .map(s->"prefix-"+s)
                                            .spliterator();
    
    Stream<String> replayable1 = StreamSupport.stream(split,false);
    Stream<String> replayable2 = StreamSupport.stream(split,false);
    
    
    replayable1.forEach(System.out::println);
    arraySplit.reset();
    replayable2.forEach(System.out::println);
  3. La meilleure solution à ce problème (à mon avis) est de faire une nouvelle copie de tous les états Spliteratorutilisés dans le Streampipeline lorsque de nouveaux opérateurs sont appelés sur le Stream. C'est plus complexe et plus compliqué à implémenter, mais si cela ne vous dérange pas d'utiliser des bibliothèques tierces, cyclops-react a une Streamimplémentation qui fait exactement cela. (Divulgation: je suis le développeur principal de ce projet.)

    Stream<String> replayableStream = ReactiveSeq.of("hello","world")
                                                 .map(s->"prefix-"+s);
    
    
    
    
    replayableStream.forEach(System.out::println);
    replayableStream.forEach(System.out::println);

Cela imprimera

prefix-hello
prefix-world
prefix-hello
prefix-world

comme prévu.

John McClean
la source