Strumień.pomiń zachowanie z nieuporządkowaną operacją terminala

Przeczytałem już to i to pytania, ale nadal wątpimy, czy obserwowane zachowanie Stream.skip było zamierzone przez autorów JDK.

Niech będzie proste wprowadzenie liczb 1..20:

List<Integer> input = IntStream.rangeClosed(1, 20).boxed().collect(Collectors.toList());

Teraz stwórzmy równoległy strumień, połączmy unordered() z skip() na różne sposoby i zbierzmy wynik:

System.out.println("skip-skip-unordered-toList: "
        + input.parallelStream().filter(x -> x > 0)
            .skip(1)
            .skip(1)
            .unordered()
            .collect(Collectors.toList()));
System.out.println("skip-unordered-skip-toList: "
        + input.parallelStream().filter(x -> x > 0)
            .skip(1)
            .unordered()
            .skip(1)
            .collect(Collectors.toList()));
System.out.println("unordered-skip-skip-toList: "
        + input.parallelStream().filter(x -> x > 0)
            .unordered()
            .skip(1)
            .skip(1)
            .collect(Collectors.toList()));

Filtrowanie krok zasadniczo nic tutaj, ale dodaje więcej trudności dla stream engine: teraz nie zna dokładnej wielkości wyjście, dlatego niektóre optymalizacje są wyłączone. Mam następujące wyniki:

skip-skip-unordered-toList: [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
// absent values: 1, 2
skip-unordered-skip-toList: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20]
// absent values: 1, 15
unordered-skip-skip-toList: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20]
// absent values: 7, 18

Wyniki są całkowicie w porządku, wszystko działa zgodnie z oczekiwaniami. W pierwszym przypadku poprosiłem o pominięcie pierwszych dwóch elementów, a następnie zebrać do listy w żadnej konkretnej kolejności. W drugim przypadku poprosiłem o pominięcie pierwszego elementu, a następnie przejście na unordered i pominięcie jeszcze jednego elementu (nie obchodzi mnie który). W trzecim przypadku najpierw przełączyłem się w tryb nieuporządkowany, a następnie pominąłem dwa dowolne elementy.

Let ' s pomiń jeden element i zbierz do kolekcji niestandardowej w trybie nieuporządkowanym. Nasza kolekcja będzie HashSet:

System.out.println("skip-toCollection: "
        + input.parallelStream().filter(x -> x > 0)
        .skip(1)
        .unordered()
        .collect(Collectors.toCollection(HashSet::new)));

Wynik jest zadowalający:

skip-toCollection: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
// 1 is skipped

Więc generalnie spodziewam się, że dopóki stream jest uporządkowany, skip() pomija pierwsze elementy, w przeciwnym razie pomija dowolne.

Jednak użyjmy równoważnej, nieuporządkowanej operacji terminala collect(Collectors.toSet()):

System.out.println("skip-toSet: "
        + input.parallelStream().filter(x -> x > 0)
            .skip(1)
            .unordered()
            .collect(Collectors.toSet()));

Teraz wyjście to:

skip-toSet: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20]
// 13 is skipped

Ten sam wynik można osiągnąć z każdym innym nieuporządkowane działanie terminala (jak forEach, findAny, anyMatch, itd.). Usunięcie unordered() kroku w tym przypadku nic nie zmienia. Wygląda na to, że podczas gdy unordered() step poprawnie powoduje, że strumień nie jest uporządkowany od bieżącej operacji, operacja terminala nie jest uporządkowana od samego początku, mimo że może to wpłynąć na wynik, jeśli skip() została użyta. Wydaje mi się to całkowicie mylące: spodziewam się, że użycie nieuporządkowanego kolektora jest tym samym, co Zamiana strumienia w tryb nieuporządkowany tuż przed operacją terminala i używając równoważnego uporządkowanego kolektora.

Więc moje pytania to:

  1. czy to zachowanie jest zamierzone, czy to błąd?
  2. jeśli tak, czy jest to gdzieś udokumentowane? Przeczytałem Stream.skip () dokumentacja: nie mówi nic o nieuporządkowanych operacjach terminala. Również Cechy.UNORDERED dokumentacja nie jest zbyt zrozumiała i nie mówi, że zamówienie zostanie utracone dla całego strumień. Na koniec sekcja uporządkowanie w podsumowaniu pakietu również nie obejmuje tego przypadku. Pewnie coś przeoczyłem?
  3. jeśli jest to zamierzone, że niezaordowana operacja terminala sprawia, że cały strumień jest niezaordowany, dlaczego unordered() krok sprawia, że jest niezaordowany dopiero od tego momentu? Czy mogę polegać na takim zachowaniu? Czy po prostu miałem szczęście, że moje pierwsze testy działają dobrze?
Author: Community, 2015-06-15

2 answers

Przypomnijmy, że celem FLAG strumieniowych (uporządkowanych, posortowanych, wielkości, odrębnych) jest umożliwienie operacjom unikania niepotrzebnej pracy. Przykłady optymalizacji, które obejmują flagi strumienia są:

  • jeśli wiemy, że strumień jest już posortowany, to sorted() jest no-op;
  • jeśli znamy rozmiar strumienia, możemy wstępnie przydzielić tablicę o prawidłowym rozmiarze w toArray(), unikając kopii;
  • jeśli wiemy, że dane wejściowe nie mają znaczącej kolejności spotkań, nie musimy podejmować dodatkowych kroków, aby zachowaj porządek spotkania.

Każdy etap rurociągu ma zestaw znaczników strumienia. Operacje pośrednie mogą wstrzykiwać, zachowywać lub usuwać flagi strumienia. Na przykład filtrowanie zachowuje sortowanie-ness / distinct-Ness, ale nie ma rozmiaru-Ness; mapowanie zachowuje sortowanie-Ness, ale nie ma sortowania-Ness lub distinct-Ness. Sortowanie wstrzykuje sortowanie-ness. Traktowanie FLAG dla operacji pośrednich jest dość proste, ponieważ wszystkie decyzje są lokalne.

Traktowanie FLAG dla operacje terminala są bardziej subtelne. Zamówiony jest najbardziej odpowiednią flagą dla operacji terminalowych. A jeśli operacja terminala jest nieuporządkowana, to robimy back-propagate unordered-ness.

Dlaczego to robimy? Cóż, rozważ ten rurociąg:
set.stream()
   .sorted()
   .forEach(System.out::println);

Ponieważ forEach nie jest ograniczona do działania w porządku, praca sortowania listy jest całkowicie zmarnowana. Więc cofamy tę informację (dopóki nie dojdzie do operacji zwarcia, takiej jak limit), aby nie stracić tej optymalizacji okazja. Podobnie, możemy użyć zoptymalizowanej implementacji distinct na nieuporządkowanych strumieniach.

Czy to zachowanie jest zamierzone, czy to błąd?

Tak:) propagacja wsteczna jest zamierzona, ponieważ jest to użyteczna optymalizacja, która nie powinna dawać błędnych wyników. Jednak część błędu polega na tym, że propagujemy poprzedni skip, czego nie powinniśmy. więc propagacja wsteczna nieuporządkowanej flagi jest zbyt agresywna i to jest błąd. Zamieścimy bug.

Jeśli tak, czy jest to gdzieś udokumentowane?

Powinien to być tylko szczegół implementacji; gdyby był poprawnie zaimplementowany, nie zauważyłbyś (poza tym, że Twoje strumienie są szybsze.)

 21
Author: Brian Goetz,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-06-18 12:58:44
@Ruben, pewnie nie rozumiesz mojego pytania. Z grubsza problem is: why unordered ().collect(toCollection (HashSet:: new)) inaczej niż collect (toSet ()). Oczywiście wiem, że toSet () jest nieuporządkowane.
Prawdopodobnie, ale w każdym razie spróbuję jeszcze raz.

Patrząc na Javadocs kolektorów toSet i toCollection widzimy, że tocollection dostarcza nieuporządkowanego kolektora

To jest {@link Collector.Charakterystyka # UNORDERED unordered} Kolekcjoner.

Tj. CollectorImpl z nieuporządkowanym charakterystycznym. Przeglądając Javadoc kolekcjonera.Charakterystyka # UNORDERED możemy przeczytać:

Wskazuje, że operacja zbierania nie zobowiązuje do zachowania kolejność elementów wejściowych

W Javadocach Collector możemy również zobaczyć:

Dla kolektorów równoległych, an wdrożenie jest bezpłatne (ale nie wymagane do równoczesnego wdrożenia redukcji. Jednoczesna redukcja jest taki, w którym funkcja akumulatora nazywana jest równocześnie z wiele wątków, używając tego samego wyniku, który można jednocześnie modyfikować kontenera, zamiast trzymać wynik odizolowany podczas akumulacja. Równoczesne zmniejszenie powinno być stosowane tylko wtedy, gdy kolektor ma cechy {@link # UNORDERED} lub jeżeli dane wyjściowe są unordered

Oznacza to dla mnie, że jeśli ustawimy charakterystykę UNORDERED, w ogóle nie dbamy o kolejność, w jakiej elementy strumienia przechodzą do akumulatora, a zatem elementy mogą być wydobywane z rurociągu w dowolnej kolejności.

Btw, otrzymujesz to samo zachowanie jeśli pominiesz unordered () w twoim przykładzie:

    System.out.println("skip-toSet: "
            + input.parallelStream().filter(x -> x > 0)
                .skip(1)
                .collect(Collectors.toSet()));

Ponadto metoda skip () w Stream daje nam podpowiedź:

While {@code skip ()} is generalnie tania operacja na sekwencyjnym rurociągów strumieniowych, to może być dość drogie na zamówione równolegle rurociągi

I

Użycie nieuporządkowanego źródła strumienia (np. {@link #generate(Supplier)}) lub usunięcie ograniczenia zamówienia za pomocą {@link #unordered ()} może wyniki w znaczących przyspieszeniach

Podczas stosowania

Collectors.toCollection(HashSet::new)

Tworzysz normalny" uporządkowany " kolektor (taki bez cech nieuporządkowanych), co dla mnie znaczy, że robisz dbaj o kolejność, a zatem elementy są wyodrębniane w kolejności i otrzymujesz oczekiwane zachowanie.

 0
Author: Ruben,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-06-17 05:49:28