Mam kilka wspomnień z wczesnego projektu interfejsu API Streams, które mogą rzucić nieco światła na uzasadnienie projektu.
W 2012 r. Dodawaliśmy lambdy do tego języka i chcieliśmy zbioru operacji opartych na kolekcjach lub „zbiorczych danych”, zaprogramowanych przy użyciu lambd, które ułatwiłyby równoległość. Pomysł leniwego łączenia operacji został w tym miejscu dobrze przyjęty. Nie chcieliśmy też, aby operacje pośrednie zapisywały wyniki.
Głównymi problemami, które musieliśmy podjąć, były: jak wyglądały obiekty w łańcuchu w interfejsie API i jak podłączyły się do źródeł danych. Źródłami były często kolekcje, ale chcieliśmy również obsługiwać dane pochodzące z pliku lub sieci lub dane generowane w locie, np. Z generatora liczb losowych.
Prace nad projektem miały wiele wpływów. Bardziej wpływowe były między innymi biblioteka Google Guava i biblioteka kolekcji Scala. (Jeśli ktoś jest zaskoczony wpływem Guavy , zauważ, że Kevin Bourrillion , główny programista Guava, był w grupie ekspertów JSR-335 Lambda .) W kolekcjach Scali stwierdziliśmy, że ta rozmowa Martina Oderskiego jest szczególnie interesująca: Future- Sprawdzanie kolekcji Scala: od Zmiennych przez Trwałe do Równoległych . (Stanford EE380, 1 czerwca 2011 r.)
Nasz ówczesny projekt prototypu opierał się wokół Iterable. Znajome operacje filter, mapi tak dalej były przedłużające (domyślnie) na metody Iterable. Wywołanie jednego dodało operację do łańcucha i zwróciło inną Iterable. Operacja terminalowa, jak countwywołałaby iterator()łańcuch do źródła, a operacje zostały zaimplementowane w Iteratorze każdego etapu.
Ponieważ są to Iterables, możesz wywołać tę iterator()metodę więcej niż jeden raz. Co zatem powinno się stać?
Jeśli źródłem jest kolekcja, działa to głównie dobrze. Kolekcje są Iterowalne, a każde wywołanie iterator()tworzy odrębną instancję Iteratora, która jest niezależna od wszelkich innych aktywnych instancji, i każda z nich niezależnie przechodzi przez kolekcję. Wspaniały.
Co teraz, jeśli źródłem jest jedno ujęcie, na przykład czytanie linii z pliku? Może pierwszy iterator powinien otrzymać wszystkie wartości, ale drugi i kolejne powinny być puste. Może wartości powinny być przeplatane między iteratorami. A może każdy Iterator powinien otrzymać te same wartości. A co, jeśli masz dwa iteratory, a jeden z nich wyprzedza drugi? Ktoś będzie musiał buforować wartości w drugim Iteratorze, dopóki nie zostaną odczytane. Gorzej, co jeśli zdobędziesz jeden Iterator i przeczytasz wszystkie wartości, a dopiero potem dostaniesz drugi Iterator. Skąd pochodzą te wartości? Czy istnieje wymóg buforowania ich wszystkich na wypadek, gdyby ktoś chciał mieć drugi iterator?
Oczywiste jest, że dopuszczenie wielu iteratorów w jednym źródle budzi wiele pytań. Nie mieliśmy dla nich dobrych odpowiedzi. Chcieliśmy spójnego, przewidywalnego zachowania w przypadku tego, co nastąpi, jeśli zadzwonisz iterator()dwukrotnie. To popchnęło nas w kierunku niedopuszczenia do wielokrotnych przejść, co sprawiło, że rurociągi były jednym strzałem.
Zauważyliśmy również, że inni wpadali na te problemy. W JDK większość Iterabeli to kolekcje lub obiekty podobne do kolekcji, które umożliwiają wielokrotne przechodzenie. Nigdzie nie jest to określone, ale wydawało się, że istnieje niepisane oczekiwanie, że Iterables zezwoli na wielokrotne przechodzenie. Godnym uwagi wyjątkiem jest interfejs NIO DirectoryStream . Jego specyfikacja zawiera to interesujące ostrzeżenie:
Chociaż DirectoryStream rozszerza Iterable, nie jest to Iterable ogólnego przeznaczenia, ponieważ obsługuje tylko jeden Iterator; wywołanie metody iteratora w celu uzyskania drugiego lub kolejnego iteratora zgłasza IllegalStateException.
[pogrubiony w oryginale]
Wydawało się to dość niezwykłe i nieprzyjemne, że nie chcieliśmy tworzyć całej gamy nowych Iterabeli, które mogą być jednorazowe. To odepchnęło nas od korzystania z Iterable.
Mniej więcej w tym czasie ukazał się artykuł Bruce'a Eckela, który opisał problem z Scalą. Napisał ten kod:
// Scala
val lines = fromString(data).getLines
val registrants = lines.map(Registrant)
registrants.foreach(println)
registrants.foreach(println)
To całkiem proste. Analizuje wiersze tekstu na Registrantobiekty i drukuje je dwukrotnie. Tyle że drukuje je tylko raz. Okazuje się, że myślał, że registrantsto zbiór, podczas gdy w rzeczywistości jest to iterator. Drugie wywołanie foreachnapotyka pusty iterator, z którego wszystkie wartości zostały wyczerpane, więc nic nie drukuje.
Tego rodzaju doświadczenie przekonało nas, że bardzo ważne jest, aby uzyskać wyraźnie przewidywalne wyniki, jeśli podjęto próbę wielokrotnego przejścia. Podkreślono także znaczenie odróżnienia leniwych struktur przypominających potoki od rzeczywistych kolekcji przechowujących dane. To z kolei doprowadziło do rozdzielenia leniwych operacji potokowych na nowy interfejs Stream i utrzymywanie tylko chętnych, mutatywnych operacji bezpośrednio na kolekcjach. Brian Goetz wyjaśnił uzasadnienie tego.
Co powiesz na zezwolenie na wielokrotne przechodzenie dla rurociągów opartych na kolekcji, ale nie zezwalanie na rurociągi nie oparte na kolekcji? To niespójne, ale rozsądne. Jeśli czytasz wartości z sieci, oczywiście nie możesz przejść ponownie. Jeśli chcesz przemierzać je wiele razy, musisz jawnie wciągnąć je do kolekcji.
Ale zbadajmy, pozwalając na wielokrotne przechodzenie z rurociągów opartych na kolekcjach. Powiedzmy, że to zrobiłeś:
Iterable<?> it = source.filter(...).map(...).filter(...).map(...);
it.into(dest1);
it.into(dest2);
( intoOperacja jest teraz pisana collect(toList()).)
Jeśli źródło jest kolekcją, pierwsze into()wywołanie utworzy łańcuch Iteratorów z powrotem do źródła, wykona operacje potokowe i wyśle wyniki do miejsca docelowego. Drugie wywołanie into()spowoduje utworzenie kolejnego łańcucha Iteratorów i ponowne wykonanie operacji potoku . Nie jest to oczywiście złe, ale powoduje, że wszystkie operacje filtrowania i mapowania wykonywane są po raz drugi dla każdego elementu. Myślę, że wielu programistów byłoby zaskoczonych takim zachowaniem.
Jak wspomniałem powyżej, rozmawialiśmy z programistami Guava. Jedną z fajnych rzeczy, jakie mają, jest Cmentarz pomysłów, w którym opisują funkcje, których nie zdecydowali się wdrożyć wraz z uzasadnieniem. Pomysł na leniwe kolekcje brzmi całkiem fajnie, ale oto, co mają do powiedzenia na ten temat. Rozważ List.filter()operację, która zwraca List:
Największym problemem jest tutaj to, że zbyt wiele operacji staje się kosztownymi propozycjami w czasie liniowym. Jeśli chcesz przefiltrować listę i odzyskać listę, a nie tylko kolekcję lub Iterable, możesz użyć ImmutableList.copyOf(Iterables.filter(list, predicate)), który „z góry określa”, co robi i jak jest drogi.
Aby podać konkretny przykład, jaki jest koszt get(0)lub size()na liście? Dla często używanych klas, takich jak ArrayList, są O (1). Ale jeśli wywołasz jedną z nich na leniwie odfiltrowanej liście, musi ona uruchomić filtr nad listą kopii zapasowych i nagle te operacje są O (n). Co gorsza, musi on przechodzić przez listę kopii zapasowych przy każdej operacji.
Wydawało nam się to zbyt dużym lenistwem. Jedną rzeczą jest skonfigurowanie niektórych operacji i odłożenie rzeczywistego wykonania, dopóki nie „przejdziesz”. Kolejnym jest ustawienie rzeczy w taki sposób, aby ukryć potencjalnie dużą liczbę ponownych obliczeń.
Proponując niedopuszczenie do strumieni nieliniowych lub strumieni „bez ponownego użycia”, Paul Sandoz opisał potencjalne konsekwencje dopuszczenia ich jako powodujące „nieoczekiwane lub mylące wyniki”. Wspomniał również, że równoległe wykonywanie sprawi, że będzie to jeszcze trudniejsze. Na koniec dodam, że operacja potokowa z efektami ubocznymi prowadziłaby do trudnych i niejasnych błędów, gdyby operacja była nieoczekiwanie wykonywana wiele razy lub przynajmniej inną liczbę razy, niż oczekiwał programista. (Ale programiści Java nie piszą wyrażeń lambda z efektami ubocznymi, prawda?
Jest to więc podstawowe uzasadnienie dla zaprojektowania interfejsu API Java 8 Streams, który umożliwia jednorazowe przejście i który wymaga ściśle liniowego (bez rozgałęzienia) potoku. Zapewnia spójne zachowanie dla wielu różnych źródeł strumienia, wyraźnie oddziela leniwe od chętnych operacji i zapewnia prosty model wykonania.
Jeśli chodzi o IEnumerable, jestem daleki od eksperta w C # i .NET, więc byłbym wdzięczny za poprawienie (delikatnie), jeśli wyciągnę niepoprawne wnioski. Wydaje się jednak, że IEnumerablepozwala wielokrotnemu przechodzeniu zachowywać się inaczej z różnymi źródłami; i pozwala na rozgałęzioną strukturę IEnumerableoperacji zagnieżdżonych , co może spowodować pewne znaczące ponowne obliczenia. Chociaż doceniam fakt, że różne systemy powodują różne kompromisy, są to dwie cechy, których staraliśmy się unikać w projekcie interfejsu API Java 8 Streams.
Przykład Quicksort podany przez OP jest interesujący, zagadkowy i przykro mi to powiedzieć, nieco przerażający. Wywołanie QuickSortwymaga IEnumerablei zwraca an IEnumerable, więc sortowanie nie jest wykonywane, dopóki finał nie IEnumerablezostanie przemierzony. Wydaje się jednak, że wywołanie polega na utworzeniu struktury drzewa IEnumerablesodzwierciedlającej partycjonowanie, które wykonałby quicksort, bez faktycznego wykonania tego. (W końcu to leniwe obliczenie.) Jeśli źródło ma N elementów, drzewo będzie miało N elementów w najszerszym miejscu i będzie miało głębokość poziomów lg (N).
Wydaje mi się - i po raz kolejny nie jestem ekspertem w C # ani .NET - że spowoduje to, że niektóre niewinnie wyglądające połączenia, takie jak wybór przestawny ints.First(), będą droższe niż się wydaje. Na pierwszym poziomie jest oczywiście O (1). Ale rozważ partycję głęboko w drzewie, po prawej stronie. Aby obliczyć pierwszy element tej partycji, należy przejść całe źródło, operacja O (N). Ale ponieważ powyższe partycje są leniwe, należy je ponownie obliczyć, wymagając porównań O (lg N). Zatem wybranie osi przestawnej byłoby operacją O (N lg N), która jest tak samo droga jak cały rodzaj.
Ale tak naprawdę nie sortujemy, dopóki nie przejdziemy zwróconych IEnumerable. W standardowym algorytmie szybkiego sortowania każdy poziom partycjonowania podwaja liczbę partycji. Każda partycja ma tylko połowę wielkości, więc każdy poziom ma złożoność O (N). Drzewo partycji ma wysokość O (lg N), więc całkowita praca to O (N lg N).
Z drzewem leniwych IEnumerables na dole drzewa znajduje się N partycji. Obliczenie każdej partycji wymaga przejścia N elementów, z których każdy wymaga porównania lg (N) w górę drzewa. Aby obliczyć wszystkie partycje w dolnej części drzewa, wymaga porównań O (N ^ 2 lg N).
(Czy to prawda? Nie mogę w to uwierzyć. Ktoś, proszę, sprawdź to dla mnie.)
W każdym razie naprawdę fajnie IEnumerablejest wykorzystać tę metodę do tworzenia skomplikowanych struktur obliczeniowych. Ale jeśli zwiększy to złożoność obliczeniową tak bardzo, jak mi się wydaje, wydaje się, że programowania w ten sposób należy unikać, chyba że ktoś jest bardzo ostrożny.