Отфильтруйте общие записи из двух последовательностей, возвращая два списка с уникальными записями из оригиналов

Я хочу отфильтровать общие элементы из двух списков и получить два списка, содержащих остатки.

У меня есть две последовательности в scala: 

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

И то, что я хочу сделать, это отфильтровать все общие элементы, что означало бы, что я в конечном итоге получу: 

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

Итак, есть простой способ добраться сюда в скале: 

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

Но! Это означает, что я должен пробежать весь первый список и совпадения, и весь второй список и совпадения, что занимает много времени. время, когда списки велики, а записи сложнее целых чисел!

Я бы предпочел только один раз пройтись по всему циклу, но единственный способ, который я могу придумать, - это иметь изменяемые списки и удалять значение из обоих, когда мы находим совпадение. Хотя это кажется немного неприятным. Я уверен, что должен быть тривиальный ответ на этот вопрос, который я упускаю.

Спасибо за любые предложения!

1 2
scala sequences

1 ответ:

Этот пример предполагает, что каждый из списков не содержит дубликатов, если это не так, то логика внутри сгиба должна будет немного измениться.

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)

Вывод: 

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