Co oznacza cecha UNORDERED kolekcjonera Java 8?

Question

W oficjalnej dokumentacji można przeczytać, że:

UNORDERED wskazuje, że operacja kolekcja nie zobowiązuje do zachowując kolejność spotkanie elementów wejściowych.

To nie jest zbyt pomocne bez żadnych przykładów.

Moje pytanie brzmi, co dokładnie oznacza charakterystyczna cecha UNORDERED? Czy powinienem używać go z redukcją kolektorów, takich jak min lub suma, czy też dotyczy to tylko kolektorów?

W OpenJDK wygląda jak operacje zmniejszające (min, sum, avg) mają puste charakterystyki. Spodziewałem się znaleźć tam co najmniej CONCURRENT i UNORDERED.

Answer 1

UNORDERED zasadniczo oznacza, że ​​kolektor jest zarówno asocjacyjny (wymagany przez specyfikację), jak i przemienny (niewymagany).

Skojarzenie umożliwia dzielenie obliczeń na podelementy, a następnie łączenie ich w pełny wynik, ale wymaga ścisłego uporządkowania etapu łączenia. Zbadać ten fragment z 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 

w ostatnim etapie, combiner.apply(a2, a3) argumenty muszą pojawiać się w dokładnie tej kolejności, co oznacza, że ​​cała obliczenie rurociąg musi śledzić kolejność i szanować go w końcu.

Innym sposobem powiedzenia tego jest to, że drzewo, które otrzymujemy z podziału rekursywnego, musi zostać uporządkowane.

Z drugiej strony, jeśli operacja łączenia jest przemienna, możemy łączyć dowolne inne części w dowolnej kolejności i zawsze uzyskiwać taki sam wynik. Oczywiście prowadzi to do wielu możliwości optymalizacji zarówno w wymiarze przestrzennym, jak i czasowym.

Należy zauważyć, że w JDK znajdują się kolektory UNORDERED, które nie gwarantują przemienności. Główną kategorią są kolektory "wyższego rzędu", które składają się z innych kolektorów niższego rzędu, ale nie wymuszają na nich właściwości UNORDERED.

Answer 2

Sama klasa wewnętrzna Collector.Characteristics jest dość lakoniczny w jego opisie, ale jeśli spędzić kilka sekund zbadanie kontekstu, można zauważyć, że zawierający Collector interfejs zapewnia dodatkowe informacje

Dla kolekcjonerów, które nie mają Charakterystyka UNORDERED, dwa skumulowane wyniki a1 i a2 są równoważne, jeśli finisher.apply (a1) .equals (finisher.apply (a2)). W przypadku kolektorów nieuporządkowanych równoważność zostaje złagodzona, aby umożliwić nierówność związaną z różnicami w porządku. (Na przykład, nieuporządkowana kolektor, który zgromadził elementy do listy byłoby rozważyć dwie listy równoważne, jeżeli zawierają one te same elementy, kolejność ignorując.)

---

W OpenJDK wygląda zmniejszenie operacji (min, suma , śr.) mają pustą charakterystykę, spodziewałem się znaleźć tam co najmniej KONKURENCYJNY i NIEOGRANICZONY.

Przynajmniej dla podwójnego sumowania i średnich są zdecydowanie uporządkowane, a nie współbieżne, ponieważ logika sumowania wykorzystuje łączenie podporządkowane, a nie bezpiecznik wątkowy.

Answer 3

W przypadku braku specjalnego pisma proces operacji strumieniowych musi zachowywać się tak, jakby elementy były przetwarzane w kolejności spotkań źródła. W przypadku niektórych operacji - takich jak redukcja z operacją asocjacyjną - można przestrzegać tego ograniczenia i nadal uzyskać wydajne wykonanie równoległe. Dla innych ograniczenie to jest bardzo ograniczone. W przypadku niektórych problemów to ograniczenie nie ma znaczenia dla użytkownika. Rozważmy następujący Stream:

people.stream() 
     .collect(groupingBy(Person::getLastName, 
          mapping(Person::getFirstName)); 

ważne jest, że lista imion związanych z „Smith” pojawi się na mapie w kolejności, w jakiej pojawiła się w początkowym strumieniu? Dla niektórych problemów, tak, dla niektórych nie - nie chcemy, aby biblioteka strumieniowa zgadywała dla nas. Zamówiony kolektor mówi, że w porządku jest wstawianie pierwszych imion do listy w porządku niezgodnym z kolejnością, w jakiej Smith-owniacy ludzie pojawiają się w źródle wejściowym. Rozluźniając to ograniczenie, czasami (nie zawsze) biblioteka strumieniowa może dać bardziej wydajne wykonanie.

Na przykład, jeśli nie dbają o zachowanie tej kolejności, można ją wykonać jako:

people.parallelStream() 
     .collect(groupingByConcurrent(Person::getLastName, 
            mapping(Person::getFirstName)); 

Jednoczesne kolektor jest nieuporządkowana, które pozwala na optymalizację dzielenie stanowiącego podstawę ConcurrentMap, zamiast O(log n) kroki scalania map. Rozluźnienie ograniczenia zamawiania zapewnia realną przewagę algorytmiczną - ale nie możemy zakładać, że ograniczenie nie ma znaczenia, potrzebujemy, aby użytkownik nas o tym poinformował. Używanie kolektora UNORDERED jest jednym ze sposobów poinformowania biblioteki strumieniowej, że te optymalizacje są uczciwą grą.