prestazioni di Stream.sorted(). Limit()

Question

Java Streames sono entrambi metodi sorted e limit, che restituiscono rispettivamente una versione ordinata di uno stream e restituiscono uno stream restituendo solo un numero specificato di elementi di uno stream. Quando queste operazioni vengono applicati in successione, come ad esempio in:

stream.sorted().limit(qty).collect(Collectors.toList()) 

è l'ordinamento viene eseguito in un modo che ordina qty oggetti o è l'intera lista ordinata? In altre parole, se qty è stato risolto, questa operazione è O(n)? La documentazione non specifica le prestazioni di questi metodi da soli o in combinazione tra loro.

La ragione per cui chiedo è che l'ovvia implementazione imperativa di queste operazioni sarebbe quella di ordinare e quindi limitare, prendendo tempo Θ(n * log(n)). Ma queste operazioni insieme possono essere eseguite in O(n * log(qty)) e un framework di streaming intelligente potrebbe visualizzare l'intero stream prima di eseguirlo per ottimizzare questo caso speciale.

Answer 1

Vorrei iniziare facendo notare che le specifiche del linguaggio Java impongono poche restrizioni sul modo in cui gli stream vengono implementati. Quindi non è davvero troppo significativo chiedere informazioni sulle prestazioni dei flussi Java: varierà in modo significativo tra le implementazioni.

Si noti inoltre che Stream è un'interfaccia. Puoi creare la tua classe che implementa Stream per avere prestazioni o comportamenti speciali su sorted che desideri. Quindi chiedere davvero delle prestazioni di Stream non ha senso nemmeno nel contesto di un'implementazione. L'implementazione di OpenJDK ha molte classi che implementano l'interfaccia Stream.

Detto questo, se guardiamo l'attuazione OpenJDK, di smistamento dei flussi finisce in SortedOps classe (vedi fonte here) troverete che i metodi di ordinamento finiscono estensioni di operazioni stateful ritorno. Ad esempio:

private static final class OfInt extends IntPipeline.StatefulOp<Integer> 

Questi metodi controllano se l'upstream è già stato ordinato nel qual caso lo passano semplicemente a valle. Hanno anche eccezioni speciali per i flussi di dimensioni (vale a dire upstream) che prealloca gli array che finiscono per l'ordinamento che migliorerà l'efficienza (su un SpinedBuffer che usano per flussi di dimensioni sconosciute). Ma ogni volta che l'upstream non è già ordinato, accettano tutti gli elementi, quindi li ordinano e quindi inviano al metodo accept dell'istanza downstream.

Quindi la conclusione da ciò è che l'implementazione OpenJDK sorted raccoglie tutti gli elementi, quindi ordina, quindi invia downstream. In alcuni casi questo sprecherà risorse quando il downstream eliminerà alcuni elementi. Sei libero di implementare la tua operazione di ordinamento specializzata che è più efficiente di questa per casi speciali.Probabilmente il modo più semplice è quello di implementare un Collector che mantiene un elenco degli n elementi più grandi o più piccoli nel flusso. L'operazione potrebbe quindi essere simile:

.collect(new CollectNthLargest(4)).stream() 

Per sostituire

.sorted().limit(4) 

Answer 2

Questo dipende dall'implementazione e potrebbe dipendere anche dal fatto che la pipeline dello stream possa "vedere attraverso" potenziali operazioni tra lo sorted() e lo limit().

Anche se si dovesse chiedere dell'implementazione di OpenJDK, è soggetto a modifiche poiché i javadocs non forniscono alcuna garanzia sul comportamento di runtime. Ma no, al momento non implementa un algoritmo di selezione k-min.

È inoltre necessario tenere presente che sorted() non funziona su flussi infiniti a meno che non abbiano già la caratteristica SORTED.

Answer 3

C'è un collezionista speciale nella mia libreria StreamEx che svolge questa operazione: MoreCollectors.least(qty):

List<?> result = stream.collect(MoreCollectors.least(qty)); 

E uses CodaConPriorita all'interno e in realtà funziona molto più velocemente con una piccola quantità su input non ordinati. Nota comunque se l'input è in gran parte ordinato, quindi sorted().limit(qty) potrebbe funzionare più velocemente dato che TimSort è incredibilmente veloce per i dati presunti.