(Parzialmente) Ordinamento di una raccolta con valutazione lazy

4

Quindi sto cercando di implementare un tipo di dati di valutazione lazy (in PHP, anche se questo non dovrebbe importare) in cui è possibile mettere in coda le azioni da intraprendere su un set di dati. Questi dati possono venire (teoricamente) da qualsiasi oggetto traversabile: matrici, generatori e altri oggetti iterabili.

Quindi, ad esempio, dato un oggetto $collection contenente un array non ordinato di numeri interi, puoi chiamare metodi su quell'oggetto come map($callback) o filter($callback) e restituirà una nuova istanza Collection con la coda azione dell'originale collezione aggiunta con il metodo chiamato. Nessuna azione in coda viene eseguita fino all'ultimo momento possibile, ad es. quando i dati verranno effettivamente utilizzati per l'output, la riduzione a un valore semplice e persino i metodi come some / every / find eseguiranno solo iterazione quanto necessario. Questa restrizione è resa più facile da implementare dalla raccolta (al momento) che non espone alcun tipo di interfaccia di accesso all'indice.

L'implementazione sottostante, una volta che l'esecuzione è stata avviata, tenterà di eseguire iterazioni sul set di dati sottostante il più volte possibile raggruppando logicamente le operazioni in coda laddove possibile per evitare di creare il più possibile rappresentazioni intermedie dei dati. Quindi, se hai impostato più% di operazioni dimap(), le comporrà. Le operazioni di filtro possono essere raggruppate in questo singolo ciclo di esecuzione, tutto ciò significa che quando la funzione di test di filtro / rifiuto non riesce, l'esecuzione termina per quell'elemento di iterazione.

E tutto funziona, fino a un caso limite: l'ordinamento. L'ordinamento (a meno che non ci sia un'idea migliore mi manca qui) richiede un ciclo di iterazione separato per iniziare in modo che l'array possa iniziare. Che non mi dispiace fare, tranne in alcuni casi come dove voglio solo, diciamo, esclusivamente i primi n elementi della raccolta ordinata. A quel punto, mi sembra che non ci sia modo di sapere quali sono quei valori senza ordinare l'intera collezione. C'è un modo per evitarlo? Altrimenti sarà uno spreco di (la maggior parte) dei vantaggi della valutazione pigra, e vorrei evitare che ...

    
posta moberemk 25.06.2015 - 01:52
fonte

2 risposte

5

In breve, no , non c'è modo di eseguire l'ordinamento su una raccolta incompleta a meno che non si ritarderà l'ordinamento fino alla fine quando la raccolta è già presente.

Versione più lunga: L'ordinamento per definizione implica la valutazione dell'intero insieme di elementi e la loro organizzazione nell'ordine corretto. Dubito che tu possa fare l'ordinamento sulla raccolta senza che l'intera raccolta sia stata istanziata.

Se la tua raccolta consiste in oggetti complessi piuttosto grandi, considera di avere i metadati oggetto richiesti per l'ordinamento disponibili al momento dell'ordinamento e carica il resto dei dati dell'oggetto come richiesto in seguito nel ciclo di esecuzione.

    
risposta data 25.06.2015 - 01:59
fonte
3

Prendendo spunti da LINQ, un modo tipico per ovviare a questa fondamentale impossibilità è implementare una funzione Take , che prende i primi N valori dalla raccolta lenta (o dall'enumeratore) e quindi elabora solo quei valori N.

Per usarlo, l'utente deve specificare quanti valori "prendere" ogni volta.

Le raccolte che sono già ordinate o istogrammate (abbinate in un ordine ordinato) possono eseguire lazy take, perché l'ordinamento è già stato fatto.

In alcuni casi d'uso limitati, si potrebbe fare qualcosa di simile a:

  • Supponiamo che i valori siano numeri interi compresi tra 0 e 99, inclusi.
  • Per recuperare tutti gli elementi nell'intervallo 0 - 9, fai un Filter tra 0 e 9 inclusi, il cui risultato viene quindi ordinato.
  • Per recuperare tutti gli elementi nell'intervallo successivo di 10 - 19, fai un altro Filter tra 10 e 19 inclusi, quindi ordina quello.

Ciò richiede una conoscenza preliminare della distribuzione numerica dei dati, ma non richiede un ordinamento completo (classifica) di tutti i dati.

In particolare, questo approccio di filtraggio dell'intervallo non sarà in grado di produrre risultati corretti a meno che non sia noto un limite inferiore sui dati numerici. (Qualsiasi limite inferiore funzionerà.)

    
risposta data 25.06.2015 - 02:04
fonte

Leggi altre domande sui tag