Rimuovi voci ridondanti, scala

Question

Modifica: aggiunto il fatto che la lista è ordinata e la realizzazione di "duplicati" è fuorviante, sostituita con "ridondante" nel titolo.

Ho un elenco ordinato di voci che indica un valore di produzione in un dato intervallo. Le voci che indicano lo stesso identico valore in un secondo momento non aggiungono informazioni e possono essere tralasciate in modo sicuro.

case class Entry(minute:Int, production:Double) 
val entries = List(Entry(0, 100.0), Entry(5, 100.0), Entry(10, 100.0), Entry(20, 120.0), Entry(30, 100.0), Entry(180, 0.0)) 

Sperimentare con le funzioni di raccolta Scala 2.8, fino ad ora ho questa implementazione di lavoro:

entries.foldRight(List[Entry]()) { 
    (entry, list) => list match { 
    case head :: tail if (entry.production == head.production) => entry :: tail 
    case head :: tail => entry :: list 
    case List() => entry :: List() 
    } 
} 
res0: List[Entry] = List(Entry(0,100.0), Entry(20,120.0), Entry(30,100.0), Entry(180,0.0)) 

Eventuali commenti? Mi sto perdendo un po 'di scala magica?

Answer 1

Quando si confrontano le voci consecutive in un elenco, iniziare con zip -ping l'elenco con la coda per ottenere un elenco di coppie di elementi consecutivi.

Di seguito, prendo la prima voce dall'elenco e utilizzo collect per filtrare simultaneamente le coppie in cui la produzione è invariata e per le coppie rimanenti, mappa e2. (collect è nuovo in Scala 2.8, e per un tempo è stato chiamato partialMap)

scala> entries.head :: ((entries zip entries.tail).collect { 
      case (Entry(_, p1), e2@Entry(_, p2)) if p1 != p2 => e2 
     }) 
res13: List[Entry] = List(Entry(0,100.0), Entry(20,120.0), Entry(30,100.0), Entry(180,0.0)) 

UPDATE Per semplicità, si assume che le voci non è vuoto.

Answer 2

Invece di cercare duplicati per ciascun elemento, che è O (n^2), o zipping, che è n^2 in memoria, utilizzare map [Double, Int]. Quindi aggiungi gli articoli con la "produzione" come chiave e il "minuto" come valore. La mappa garantirà valori unici per la "produzione". Potresti essere in grado di caricare la mappa in modo naturale altrove nel tuo codice, ma anche se devi iniziare con la lista come sopra, il caricamento della mappa è lineare sulla lista e solo O (n log (n)) sulla mappa.

La mappa verrà sostituita quando si aggiunge "mymap + = produzione -> minuto" in modo da mantenere il primo valore, invertire l'elenco prima di inserire o utilizzare una protezione "contiene (chiave)". I controlli saranno O (log (n)) quindi l'algoritmo complessivo sarà O (n log (n)).

BTW, è possibile utilizzare una mappa [Double, Entry] per mappare dai valori di produzione direttamente alle strutture Entry. Quindi è possibile ottenere facilmente una lista, se necessario, estraendo i valori della mappa direttamente dalla mappa e ordinando su entrambi gli elementi della voce (se necessario).

Answer 3

C'è un nuovo metodo zipped con Tuple2 che è più efficiente (e più pigro) di zip in elenchi per alcune operazioni. Si potrebbe provare questo fuori sul vostro punto di riferimento - non so se è effettivamente più veloce, ma certamente potrebbe essere (ed è sicuramente molto più breve):

entries.take(1) ::: 
(entries,entries.drop(1)).zipped.filter(_.production != _.production)._2 

Invece di zippare lista a coppie tutti la via attraverso, crea una vista della lista in cui i pezzi possono essere manipolati insieme, e quindi restituisce le liste manipolate. Nota l'uso di prendere e rilasciare per gestire il caso vuoto.

Non è super efficiente poiché crea due elenchi quando ne hai solo bisogno uno, ma è una classe di soluzione che non è ancora disponibile.