Entfernen redundante Einträge, scala Weg

Question

Bearbeiten: Die Tatsache hinzugefügt, dass die Liste sortiert ist, und Realisierung von "duplizieren" ist irreführend, ersetzt das mit "redundant" im Titel.

Ich habe eine sortierte Liste von Einträgen, die einen Produktionswert in einem bestimmten Intervall angeben. Einträge, die zu einem späteren Zeitpunkt den exakt gleichen Wert angeben, fügen keine Informationen hinzu und können sicher weggelassen werden.

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)) 

Experimentieren mit den scala 2.8 Sammelfunktionen, so weit ich habe diese Arbeit Umsetzung:

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)) 

Fragen oder Anregungen? Verpasse ich etwas Scala-Magie?

Answer 1

Wenn Sie die aufeinander folgenden Einträge in einer Liste vergleichen, beginnen Sie mit zip - ping die Liste mit ihrem Schwanz, um eine Liste von Paaren aufeinander folgender Elemente zu erhalten.

Unten, ich nehme den ersten Eintrag aus der Liste, und collect verwenden, um gleichzeitig Paare zu filtern, bei denen die Produktion unverändert ist, und für die verbleibenden Paare, Karte e2. (collect ist neu in Scala 2.8, und für eine Weile wurde partialMap genannt)

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 Der Einfachheit halber dies setzt voraus, dass Einträge nicht leer ist.

Answer 2

Anstatt nach Duplikaten für jedes Element zu suchen, welches O (n^2) ist, oder zippen, was n^2 im Speicher ist, verwenden Sie map [Double, Int]. Dann fügen Sie einfach die Elemente mit der 'Produktion' als Schlüssel und der 'Minute' als Wert hinzu. Die Karte stellt eindeutige Werte für die Produktion sicher. Sie können die Karte natürlich an anderer Stelle in Ihrem Code laden, aber selbst wenn Sie mit der Liste wie oben beginnen müssen, ist das Laden der Karte in der Liste linear und nur O (n log (n)) auf der Karte.

Die Karte wird ersetzt, wenn Sie "mymap + = production -> minute" hinzufügen. Um den ersten Wert beizubehalten, kehren Sie die Liste um, bevor Sie einen 'contains (key)' Guard einfügen oder verwenden. Die Überprüfungen werden O (log (n)) sein, so dass der Algorithmus insgesamt O (n log (n)) ist.

BTW, Sie könnten eine Karte [Double, Entry] verwenden, um Produktionswerte direkt auf Ihre Entry-Strukturen abzubilden. Dann können Sie bei Bedarf eine Liste heraussuchen, indem Sie die Werte der Karte direkt aus der Karte ziehen und bei Bedarf jedes Element des Eintrags sortieren.

Answer 3

Es gibt eine neue zipped Methode mit Tuple2, die effizienter ist (und fauler) als zip auf Listen für einige Operationen. Sie könnten versuchen, diese auf Ihre Benchmark - ich weiß nicht, ob es tatsächlich schneller ist, aber es ist sicherlich könnte sein (und es ist auf jeden Fall viel kürzer):

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

Anstatt die Liste paarweise alle zippen Englisch: www.doc-o-matic.com/webhelp/AH_Edit...ng.html & L = 1 Durch den Weg hindurch erstellt er eine Ansicht der Liste, in der die Teile zusammen manipuliert werden können und gibt dann die manipulierten Listen zurück Beachten Sie die Verwendung von Take und Drop, um mit dem leeren Fall umzugehen.

Es ist nicht super effizient, da es zwei Listen erstellt, wenn Sie wirklich nur eine benötigen, aber es ist eine Klasse von Lösung, die noch nicht aufgetaucht ist.