Как выбрать элементы коллекции на основе другого типа?

Question

Я знаю, что могу это сделать:

scala> val a = List(1,2,3) 
a: List[Int] = List(1, 2, 3) 

scala> val b = List(2,4) 
b: List[Int] = List(2, 4) 

scala> a.filterNot(b.toSet) 
res0: List[Int] = List(1, 3) 

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

case class N (p: Int , q: Int) 
val x = List(N(1,100), N(2,200), N(3,300)) 
val y = List(2,4) 
val z = .... ? 
Z // want Z to be ((N1,100), (N3,300)) after removing the items of type N with 'p' 
    // matching any item in list y. 

Я знаю, что один из способов это что-то вроде следующего, что делает вышеперечисленный неработающий код работы:

val z = x.filterNot(e => y.contains(e.p)) 

но это кажется очень неэффективным. Есть ли способ лучше?

Answer 1

Проблема contains в том, что поиск будет линейный поиск, и вы смотрите на O(N^2) раствор (который по-прежнему хорошо, если набор данных не большой)

В любом случае, это простое решение может быть использование Двоичный поиск, чтобы получить решение O(NlnN). Вы можете легко преобразовать val y в Array из списка, а затем использовать метод двоичного поиска java.

scala> case class N(p: Int, q: Int) 
defined class N 

scala> val x = List(N(1, 100), N(2, 200), N(3, 300)) 
x: List[N] = List(N(1,100), N(2,200), N(3,300)) 

scala> val y = Array(2, 4) // Using Array directly. 
y: Array[Int] = Array(2, 4) 

scala> val z = x.filterNot(e => java.util.Arrays.binarySearch(y, e.p) >= 0) 
z: List[N] = List(N(1,100), N(3,300)) 

Answer 2

Вобще

val z = y.toSet 
x.filterNot {z.contains(_.p)} 

Это линейная.