Java 8 funkcjonalny styl iterować z indeksami

Question

Ćwiczę java 8 strumieni i styl funkcjonalny na chwilę. Czasami próbuję rozwiązać niektóre zagadki programistyczne za pomocą strumieni. W tym czasie znalazłem klasę zadań, których nie potrafię rozwiązać za pomocą strumieni, tylko z klasycznym podejściem.

Jednym z przykładów tego rodzaju zadań jest: Biorąc pod uwagę tablicę liczb znajdź indeks elementu, który zsumuje lewą część tablicy poniżej zera. np. na tablicy [1, 2, 3, -1, 3, -10, 9] odpowiedź będzie 5

Moim pierwszym pomysłem było wykorzystanie IntStream.generate(0, arr.length)... ale nie wiem, jak gromadzić wartości i świadomość indeksu samym czasie.

więc pytania:

• Czy to możliwe, aby w jakiś sposób gromadzić wartość nad strumieniem, a następnie dokonać warunkowego wyjścia?
• Co to jest z równoległym wykonaniem? nie pasuje to do znalezienia indeksów, w których musimy być świadomi kolejności elementów.

Answer 1

Wątpię, aby Twoje zadanie dobrze pasowało do strumieni. To, czego szukasz, to typowa operacja skanowania, która z natury jest sekwencyjną operacją.

Na przykład wyobraź sobie następujące elementy w przygotowaniu: [1, 2, -4, 5]. Równoległe wykonanie może podzielić go na dwie części: [1, 2] i [-4, 5]. Więc co byś z nimi zrobił? Nie możesz ich podsumować niezależnie, ponieważ przyniesie to [3] i [1], a następnie straciłeś fakt, że 1 + 2 - 4 < 0 był przestrzegany.

Więc nawet jeśli napiszesz kolekcjoner, który śledzi indeks, i sumę, nie będzie on w stanie wykonywać dobrze równolegle (wątpię, czy możesz z niego skorzystać), ale możesz sobie wyobrazić takiego kolekcjonera dla sekwencyjnego użytku:

public static Collector<Integer, ?, Integer> indexSumLeft(int limit) { 
     return Collector.of(
       () -> new int[]{-1, 0, 0}, 
       (arr, elem) -> { 
        if(arr[2] == 0) { 
         arr[1] += elem; 
         arr[0]++; 
        } 
        if(arr[1] < limit) { 
         arr[2] = 1; 
        } 

       }, 
       (arr1, arr2) -> {throw new UnsupportedOperationException("Cannot run in parallel");}, 
       arr -> arr[0] 

     ); 
    } 

i prostego użytkowania:

int index = IntStream.of(arr).boxed().collect(indexSumLeft(0)); 

ten będzie nadal przechodzić wszystkie elementy rurociągu, więc nie bardzo wydajne.

Możesz również rozważyć użycie Arrays.parallelPrefix, jeśli źródłem danych jest tablica. Wystarczy obliczyć częściowe sumy, a następnie użyć strumienia, aby znaleźć pierwszy indeks, w którym suma jest poniżej limitu.

Arrays.parallelPrefix(arr, Integer::sum); 
int index = IntStream.range(0, arr.length) 
        .filter(i -> arr[i] < limit) 
        .findFirst() 
        .orElse(-1); 

Tutaj również obliczane są wszystkie sumy cząstkowe (ale równolegle).

Krótko mówiąc, użyłbym prostej pętli for.

Answer 2

mogę zaproponować rozwiązanie używając mojego StreamEx biblioteki (który zapewnia dodatkowe funkcje API Stream), ale nie byłby zadowolony z takiego rozwiązania:

int[] input = {1, 2, 3, -1, 3, -10, 9}; 
System.out.println(IntStreamEx.of(
    IntStreamEx.of(input).scanLeft(Integer::sum)).indexOf(x -> x < 0)); 
// prints OptionalLong[5] 

Wykorzystuje IntStreamEx.scanLeft operację obliczyć tablica sum prefiksów, a następnie przeszukuje tę tablicę za pomocą operacji IntStreamEx.indexOf. Podczas gdy indexOf jest zwarciem, operacja scanLeft przetworzy całe wejście i utworzy pośrednią tablicę o tej samej długości, co wejście, co jest zupełnie niepotrzebne, gdy rozwiązuje ten sam problem w trybie rozkazującym.

Answer 3

Dzięki nowej metodzie headTail w mojej bibliotece StreamEx możliwe jest stworzenie leniwego rozwiązania, które działa dobrze dla bardzo długich lub nieskończonych strumieni. Po pierwsze, można określić nowy pośredni scanLeft operacji:

public static <T> StreamEx<T> scanLeft(StreamEx<T> input, BinaryOperator<T> operator) { 
    return input.headTail((head, tail) -> 
       scanLeft(tail.mapFirst(cur -> operator.apply(head, cur)), operator) 
        .prepend(head)); 
} 

Definiuje lazy scanLeft pomocą headTail: dotyczy daną funkcję w head i pierwszy element strumienia tail, następnie Poprzedza head. Teraz można korzystać z tego scanLeft:

scanLeft(StreamEx.of(1, 2, 3, -1, 3, -10, 9), Integer::sum).indexOf(x -> x < 0); 

To samo można zastosować do nieskończonego strumienia (np strumienia liczb losowych):

StreamEx<Integer> ints = IntStreamEx.of(new Random(), -100, 100) 
            .peek(System.out::println).boxed(); 
int idx = scanLeft(ints, Integer::sum).indexOf(x -> x < 0); 

ten potrwa do skumulowanej sumy staje się ujemne i zwraca indeks odpowiedniego elementu.