webentwicklung-frage-antwort-db.com.de

Java Streams: Wie mache ich eine effiziente "Unterscheidung und Sortierung"?

Nehmen wir an, ich habe einen Stream<T> und möchte nur bestimmte Elemente erhalten und sortieren.

Der naive Ansatz wäre nur Folgendes zu tun:

Stream.of(...)
    .sorted()
    .distinct()

oder vielleicht andersherum:

Stream.of(...)
    .distinct()
    .sorted()

Da die Implementierung von beiden durch den Quellcode des JDK nicht wirklich zugänglich ist, habe ich mich nur über den möglichen Speicherbedarf und die Auswirkungen auf die Leistung Gedanken gemacht.

Oder wäre es noch effizienter, meinen eigenen Filter als den folgenden zu schreiben?

Stream.of(...)
    .sorted()
    .filter(noAdjacentDuplicatesFilter())

public static Predicate<Object> noAdjacentDuplicatesFilter() {
    final Object[] previousValue = {new Object()};

    return value -> {
        final boolean takeValue = !Objects.equals(previousValue[0], value);
        previousValue[0] = value;
        return takeValue;
    };
}
18

Wenn Sie eine distinct()-Operation nach sorted() verketten, verwendet die Implementierung die sortierte Natur der Daten und vermeidet die Erstellung einer internen HashSet, die durch das folgende Programm demonstriert werden kann

public class DistinctAndSort {
    static int COMPARE, EQUALS, HASHCODE;
    static class Tracker implements Comparable<Tracker> {
        static int SERIAL;
        int id;
        Tracker() {
            id=SERIAL++/2;
        }
        public int compareTo(Tracker o) {
            COMPARE++;
            return Integer.compare(id, o.id);
        }
        public int hashCode() {
            HASHCODE++;
            return id;
        }
        public boolean equals(Object obj) {
            EQUALS++;
            return super.equals(obj);
        }
    }
    public static void main(String[] args) {
        System.out.println("adjacent sorted() and distinct()");
        Stream.generate(Tracker::new).limit(100)
              .sorted().distinct()
              .forEachOrdered(o -> {});
        System.out.printf("compareTo: %d, EQUALS: %d, HASHCODE: %d%n",
                          COMPARE, EQUALS, HASHCODE);
        COMPARE=EQUALS=HASHCODE=0;
        System.out.println("now with intermediate operation");
        Stream.generate(Tracker::new).limit(100)
            .sorted().map(x -> x).distinct()
            .forEachOrdered(o -> {});
        System.out.printf("compareTo: %d, EQUALS: %d, HASHCODE: %d%n",
                          COMPARE, EQUALS, HASHCODE);
    }
}

was gedruckt wird

adjacent sorted() and distinct()
compareTo: 99, EQUALS: 99, HASHCODE: 0
now with intermediate operation
compareTo: 99, EQUALS: 100, HASHCODE: 200

Die Zwischenoperation, so einfach wie map(x -> x), kann von der Stream-Implementierung nicht erkannt werden. Daher muss davon ausgegangen werden, dass die Elemente möglicherweise nicht nach dem Ergebnis der Zuordnungsfunktion sortiert werden.

Es gibt keine Garantie dafür, dass diese Art von Optimierung stattfindet. Es ist jedoch davon auszugehen, dass die Entwickler der Stream-Implementierung diese Optimierung nicht entfernen und sogar versuchen, weitere Optimierungen hinzuzufügen. Wenn Sie also Ihre eigene Implementierung implementieren, kann Ihr Code davon nicht profitieren zukünftige Optimierungen.

Was Sie erstellt haben, ist ein "stateful Prädikat", von dem dringend abgeraten wird und das natürlich bricht, wenn es mit einem parallelen Stream verwendet wird.

Wenn Sie der Stream-API nicht vertrauen, um diese Operation effizient genug durchzuführen, können Sie diese spezielle Operation möglicherweise besser ohne die Stream-API implementieren.

18
Holger

Disclaimer: Ich weiß, dass Leistungstests hart sind und insbesondere in der JVM mit Warmups und einer kontrollierten Umgebung, in der keine anderen Prozesse ausgeführt werden.

Wenn ich es teste, bekomme ich diese Ergebnisse, so dass Ihre Implementierung die parallele Ausführung begünstigt. (Läuft auf i7 mit 4 Kernen + Hyperthreading).

".distinct().sorted()" scheint also langsamer zu sein. Wie vorhergesagt/erklärt von Holger

Round 1 (Warm up?)
3938
2449
5747
Round 2
2834
2620
3984
Round 3 Parallel
831
4343
6346
Round 4 Parallel
825
3309
6339

Code verwenden:

package test.test;

import Java.util.Collections;
import Java.util.List;
import Java.util.Objects;
import Java.util.function.Predicate;
import Java.util.stream.Collectors;
import Java.util.stream.IntStream;

public class SortDistinctTest {

    public static void main(String[] args) {
        IntStream range = IntStream.range(0, 6_000_000);
        List<Integer> collect = range.boxed().collect(Collectors.toList());
        Collections.shuffle(collect);

        long start = System.currentTimeMillis();

        System.out.println("Round 1 (Warm up?)");
        collect.stream().sorted().filter(noAdjacentDuplicatesFilter()).collect(Collectors.counting());
        long fst = System.currentTimeMillis();
        System.out.println(fst - start);

        collect.stream().sorted().distinct().collect(Collectors.counting());
        long snd = System.currentTimeMillis();
        System.out.println(snd - fst);

        collect.stream().distinct().sorted().collect(Collectors.counting());
        long end = System.currentTimeMillis();
        System.out.println(end - snd);

        System.out.println("Round 2");
        collect.stream().sorted().filter(noAdjacentDuplicatesFilter()).collect(Collectors.counting());
        fst = System.currentTimeMillis();
        System.out.println(fst - end);

        collect.stream().sorted().distinct().collect(Collectors.counting());
        snd = System.currentTimeMillis();
        System.out.println(snd - fst);

        collect.stream().distinct().sorted().collect(Collectors.counting());
        end = System.currentTimeMillis();
        System.out.println(end - snd);

        System.out.println("Round 3 Parallel");
        collect.stream().parallel().sorted().filter(noAdjacentDuplicatesFilter()).collect(Collectors.counting());
        fst = System.currentTimeMillis();
        System.out.println(fst - end);

        collect.stream().parallel().sorted().distinct().collect(Collectors.counting());
        snd = System.currentTimeMillis();
        System.out.println(snd - fst);

        collect.stream().parallel().distinct().sorted().collect(Collectors.counting());
        end = System.currentTimeMillis();
        System.out.println(end - snd);

        System.out.println("Round 4 Parallel");
        collect.stream().parallel().sorted().filter(noAdjacentDuplicatesFilter()).collect(Collectors.counting());
        fst = System.currentTimeMillis();
        System.out.println(fst - end);

        collect.stream().parallel().sorted().distinct().collect(Collectors.counting());
        snd = System.currentTimeMillis();
        System.out.println(snd - fst);

        collect.stream().parallel().distinct().sorted().collect(Collectors.counting());
        end = System.currentTimeMillis();
        System.out.println(end - snd);

    }

    public static Predicate<Object> noAdjacentDuplicatesFilter() {
        final Object[] previousValue = { new Object() };

        return value -> {
            final boolean takeValue = !Objects.equals(previousValue[0], value);
            previousValue[0] = value;
            return takeValue;
        };

    }

}
0
Viktor Mellgren