Gemeinsame Einträge aus zwei Sequenzen herausfiltern, zwei Listen mit eindeutigen Einträgen aus den Originalen zurückgeben

Question

Ich möchte die gemeinsamen Elemente aus zwei Listen filtern und links mit zwei Listen, die die Reste enthalten.

Ich habe zwei Sequenzen in scala:

val firstSeq = Seq(1,2,3,4) 
val secondSeq = Seq(1,3,5,7) 

Und was ich will tun, Filter alle gemeinsamen Elemente, die ich mit am Ende bedeuten würde:

filteredFirstSeq = Seq(2,4) 
filteredSecondSeq = Seq(5,7) 

So gibt es Ein einfacher Weg, um in Scala zu kommen:

val filteredFirstSeq = firstSeq.filterNot(firstEntry => secondSeq.contains(firstEntry)) 
val filteredSecondSeq = secondSeq.filterNot(secondEntry => firstSeq.contains(secondEntry)) 

Aber! Das bedeutet, dass ich die gesamte erste Liste durchlaufen muss und die gesamte zweite Liste mit und übereinstimmen muss, und Übereinstimmungen, die bei großen Listen sehr lange dauern und die Einträge komplizierter sind als ganze Zahlen!

Ich würde viel lieber nur einmal alles durchgehen müssen, aber die einzige Möglichkeit, dies zu tun, ist, veränderbare Listen zu haben und einen Wert von beiden zu entfernen, wenn wir eine Übereinstimmung finden. Das scheint ein bisschen eklig zu sein. Ich bin mir sicher, dass es eine triviale Antwort darauf geben muss, dass ich vermisse.

Vielen Dank für Anregungen!

Answer 1

In diesem Beispiel wird davon ausgegangen, dass jede der Listen keine Duplikate enthält. Wenn dies nicht der Fall ist, muss sich die Logik innerhalb der Faltung geringfügig ändern.

val firstSeq = Seq(1,2,3,4) 
val secondSeq = Seq(1,3,5,7) 

// Put everything into a list, keeping track of where things came from 
val both: Seq[(Int, Int)] = firstSeq.map(x => (x, 1)) ++ secondSeq.map(x => (x, 2)) 

// Reduce the list into a single map, where the keys are the numbers, and the value is the originating seq. Anytime we try to insert a value that already is in the map, we remove the value instead, since that will mean the value was in each sequence. 
val map: Map[Int, Int] = both.foldLeft(Map.empty[Int, Int]) { (map, tuple) => 
    val (value, seqNumber) = tuple 
    if (map.contains(value)) { 
    map - value 
    } else { 
    map + (value -> seqNumber) 
    } 
} 

// Now partition the values back into their original lists 
val (firstSeqFiltered, secondSeqFiltered) = map.partition(_._2 == 1) 
println(firstSeqFiltered.keys) 
println(secondSeqFiltered.keys) 

Ausgang:

Set(2, 4) 
Set(5, 7)