Фильтрация коллекции Scala по нескольким элементам

У меня есть следующая рекурсивная функция для удаления элементов из списка (zooResidents: List[(String, Int)]), содержащихся в другом списке (pets: List[String]. >). Он работает, но очень медленно. Как это сделать в Scala?

val pets = List("cat", "dog")

val zooResidents = List(("cat", 4), ("lion", 2), ("tiger", 3), ("dog", 2) 

def removePets(zooResidents: List[(String, Int)], pets: List[String]): List[(String, Int)] =  {
  if (pets.isEmpty) zooResidents
  else removePets(zooResidents.filterNot(_._1.contains(pets.head)), pets.tail)
}

removePets(zooResidents, pets)      //> res2: List[(String, Int)] = List((lion,2), (tiger,3))

recursion scala functional-programming scala-collections tail-recursion
person Saqib Ali    schedule 01.06.2016    source источник

Ответы (3)


arrow_upward
5
arrow_downward

Обратите внимание, что List#contains является линейным, так как он должен сканировать весь список, я бы рекомендовал вам использовать структуру данных с постоянным поиском, например Set

val petSet = pets.toSet
val filter = zooResidents.filterNot(element => petSet.contains(element._1))
person Sleiman Jneidi    schedule 01.06.2016
comment
Слейман. Спасибо, это работает! Я новичок в Scala, не могли бы вы помочь мне понять, как это работает? - person Saqib Ali; 01.06.2016
comment
Это просто неверно, возвращает cat и dog, вам нужно отменить условие. - person Łukasz; 01.06.2016
comment
Lukasz, ага, поменял на filterNot. Затем он делает то, что мне нужно. - person Saqib Ali; 01.06.2016
comment
Извините ребята, это опечатка - person Sleiman Jneidi; 01.06.2016
comment
@SaqibAli Мы просто фильтруем элементы в списке, для каждого элемента, если набор содержит текущий элемент, мы не добавляем его в список результатов. - person Sleiman Jneidi; 01.06.2016

arrow_upward
2
arrow_downward

Это то, что я бы назвал способом Scala

@ zooResidents filterNot { case (resident, _) => pets contains resident } 
res6: List[(String, Int)] = List(("lion", 2), ("tiger", 3))

Для лучшей производительности pets должен быть Set.

filterNot принимает только те элементы, которые не удовлетворяют предикату, т.е. те, для которых данная функция возвращает false. Итак, мы хотим взять все те элементы, для которых pets не содержит первого элемента кортежа.

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

{ case (resident, _) => pets contains resident }

это эквивалентно

(residentTuple => pets.contains(residentTuple._1))
person Łukasz    schedule 01.06.2016

arrow_upward
1
arrow_downward 

val zooResidents = List(("cat", 4), ("lion", 2), ("tiger", 3), ("dog", 2)
val pets = List("cat", "dog")

Попробуйте однострочник:

zooResidents.filter(x=>pets.toSet.contains(x._1)==false)

scala> zooResidents.filter(x=>pets.toSet.contains(x._1)==false)
res167: List[(String, Int)] = List((lion,2), (tiger,3))

домашние животные изменены на набор для повышения производительности.

Это берет список zooResidents и проверяет наличие каждой строки в pets также и возвращает только те элементы zooResidents, которых нет в pets, ==false сделает это.

person RAGHHURAAMM    schedule 15.07.2018
comment
Пожалуйста, добавьте объяснение. - person petezurich; 15.07.2018