Efficienza di collection.stream(). Salto(). FindFirst()

Question

Supponiamo set è un HashSet con n elementi e k qualche int tra 0 (incluso) e n (esclusiva).

Qualcuno può spiegare, in termini semplici, cosa succede realmente quando lo fai?

set.stream().skip(k).findFirst(); 

In particolare, qual è la complessità temporale di questo? L'aggiunta di spliterator() all'interfaccia Collection significa che ora abbiamo un accesso più rapido agli elementi "casuali" delle raccolte di quanto sarebbe stato possibile con Java 7?

Answer 1

attuazione attuale ha O (k) complessità e piùmeno equivalente alla seguente:

Iterator<?> it = set.iterator(); 
for(int i=0; i<k && it.hasNext(); i++) it.next(); 
return it.hasNext() ? Optional.of(it.next()) : Optional.empty(); 

attuazione attuale non tiene conto ORDERED caratteristica per flussi sequenziali. Il pezzo di codice citato nella risposta @ the8472 funziona solo per i flussi paralleli. In parallelo, la complessità ammortizzata è approssimativamente O (k/n) dove n è il numero di processori.

Answer 2

nome Louis menziona salto non ha realmente senso sui flussi non ordinati, in realtà è attualmente (JDK 1.8) attuato in modo in cui il metodo seguente ottimizzare il salto di distanza in alcune circostanze:

 Spliterator<T> unorderedSkipLimitSpliterator(Spliterator<T> s, 
                long skip, long limit, long sizeIfKnown) { 
      if (skip <= sizeIfKnown) { 
       // Use just the limit if the number of elements 
       // to skip is <= the known pipeline size 
       limit = limit >= 0 ? Math.min(limit, sizeIfKnown - skip) : sizeIfKnown - skip; 
       skip = 0; 
      } 
      return new StreamSpliterators.UnorderedSliceSpliterator.OfRef<>(s, skip, limit); 
     } 

Questo è valido perché equivale a semplicemente attraversare la raccolta di origine in un ordine diverso.