Quoi de plus efficace: stream sortingé ou sorting d’une liste?

Il est prudent de dire que deux types de sorting auront la même complexité … même sans regarder le code. (S’ils ne le faisaient pas, un formulaire serait gravement endommagé!)

En examinant le code source de Java 8 pour les stream (en particulier la classe interne java.util.stream.SortedOps ), la méthode sorted() ajoute un composant à un pipeline de stream qui capture tous les éléments de stream dans un tableau ou une ArrayList .

• Un tableau est utilisé si et seulement si le code d’assemblage de pipeline peut déduire le nombre d’éléments dans le stream à l’avance.

• Sinon, une liste de ArrayList est utilisée pour regrouper les éléments à sortinger.

Si une liste de ArrayList est utilisée, vous indiquez des frais généraux supplémentaires liés à la construction / augmentation de la liste.

Ensuite, nous revenons à deux versions du code:

 List sortedItems = new ArrayList<>(items); Collections.sort(sortedItems, itemComparator); 

Dans cette version, le constructeur ArrayList copie les éléments d’ items dans un tableau de taille appropriée, puis Collections.sort effectue un sorting sur place de ce tableau. (Cela se passe sous les couvertures).

 List sortedItems = items .stream() .sorted(itemComparator) .collect(Collectors.toList()); 

Dans cette version, comme nous l’avons vu ci-dessus, le code associé à sorted() construit ou sortinge un tableau (équivalent à ce qui se passe ci-dessus) ou construit ArrayList manière lente. Mais en plus de cela, il y a les frais généraux de stream des données des items et au collecteur.

En général (avec l’implémentation de Java 8 au moins), l’examen du code m’indique que la première version du code ne peut pas être plus lente que la deuxième version et, dans la plupart des cas (si ce n’est tous), elle sera plus rapide. Mais à mesure que la liste O(NlogN) sorting O(NlogN) aura tendance à dominer les frais généraux O(N) de la copie. Cela signifie que la différence relative entre les deux versions sera plus petite.

Si vous y tenez vraiment, vous devriez être capable d’écrire un sharepoint repère pour tester la différence réelle avec une implémentation spécifique de Java et un jeu de données en entrée spécifique. (Ou adaptez @ le sharepoint repère d’Eugene!)

Pour être honnête, je ne fais pas trop confiance à JMH (à moins que je ne comprenne le assembly, ce qui prend beaucoup de temps dans mon cas), d’autant plus que j’ai utilisé @Setup(Level.Invocation) , mais voici un petit exemple. test (j’ai pris la génération SsortingngInput d’un autre test que j’ai fait, mais cela ne devrait pas avoir d’importance, ce ne sont que quelques données à sortinger)

 @State(Scope.Thread) public static class SsortingngInput { private Ssortingng[] letters = { "q", "a", "z", "w", "s", "x", "e", "d", "c", "r", "f", "v", "t", "g", "b", "y", "h", "n", "u", "j", "m", "i", "k", "o", "l", "p" }; public Ssortingng s = ""; public List list; @Param(value = { "1000", "10000", "100000" }) int next; @TearDown(Level.Invocation) public void tearDown() { s = null; } @Setup(Level.Invocation) public void setUp() { list = ThreadLocalRandom.current() .ints(next, 0, letters.length) .mapToObj(x -> letters[x]) .map(x -> Character.toSsortingng((char) x.intValue())) .collect(Collectors.toList()); } } @Fork(1) @Benchmark public List testCollection(SsortingngInput si){ Collections.sort(si.list, Comparator.naturalOrder()); return si.list; } @Fork(1) @Benchmark public List testStream(SsortingngInput si){ return si.list.stream() .sorted(Comparator.naturalOrder()) .collect(Collectors.toList()); } 

Les résultats montrent que Collections.sort est plus rapide, mais pas de beaucoup:

 Benchmark (next) Mode Cnt Score Error Units streamvsLoop.StreamVsLoop.testCollection 1000 avgt 2 0.038 ms/op streamvsLoop.StreamVsLoop.testCollection 10000 avgt 2 0.599 ms/op streamvsLoop.StreamVsLoop.testCollection 100000 avgt 2 12.488 ms/op streamvsLoop.StreamVsLoop.testStream 1000 avgt 2 0.048 ms/op streamvsLoop.StreamVsLoop.testStream 10000 avgt 2 0.808 ms/op streamvsLoop.StreamVsLoop.testStream 100000 avgt 2 15.652 ms/op 

Ci-dessous mon repère (pas vraiment sûr si c’est correct):

 import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Set; import java.util.TreeSet; import java.util.concurrent.TimeUnit; import java.util.stream.Collectors; import org.openjdk.jmh.annotations.Benchmark; import org.openjdk.jmh.annotations.BenchmarkMode; import org.openjdk.jmh.annotations.Mode; import org.openjdk.jmh.annotations.OperationsPerInvocation; import org.openjdk.jmh.annotations.OutputTimeUnit; @OutputTimeUnit(TimeUnit.NANOSECONDS) @BenchmarkMode(Mode.AverageTime) @OperationsPerInvocation(MyBenchmark.N) public class MyBenchmark { public static final int N = 50; public static final int SIZE = 100000; static List sourceList = new ArrayList<>(); static { System.out.println("Generating the list"); for (int i = 0; i < SIZE; i++) { sourceList.add(i); } System.out.println("Shuffling the list."); Collections.shuffle(sourceList); } @Benchmark public List sortingList() { List sortedList = new ArrayList<>(sourceList); Collections.sort(sortedList); return sortedList; } @Benchmark public List sortedStream() { List sortedList = sourceList.stream().sorted().collect(Collectors.toList()); return sortedList; } @Benchmark public List treeSet() { Set sortedSet = new TreeSet<>(sourceList); List sortedList = new ArrayList<>(sortedSet); return sortedList; } } 

Résultats:

 Benchmark Mode Cnt Score Error Units MyBenchmark.sortedStream avgt 200 300691.436 ± 15894.717 ns/op MyBenchmark.sortingList avgt 200 262704.939 ± 5073.915 ns/op MyBenchmark.treeSet avgt 200 856577.553 ± 49296.565 ns/op 

Comme dans la référence de @ Eugene, la liste de sorting est légèrement plus rapide (environ 20%) que le stream sortingé. Ce qui me surprend un peu, c’est que treeSet est beaucoup plus lent. Je ne m’attendais pas à ça.