Scala:删除对象列表中的重复项

Question

我有一个对象列表,这些对象List[Object]都是从同一个类中实例化的.该类有一个必须唯一的字段Object.property.迭代对象列表并删除具有相同属性的所有对象(但第一个)的最简洁方法是什么？

Answer 1

list.groupBy(_.property).map(_._2.head)

Explanation:groupBy方法接受将元素转换为键以进行分组的函数._.property只是简写elem: Object => elem.property(编译器生成一个唯一的名称,类似x$1).所以现在我们有了一张地图Map[Property, List[Object]].A Map[K,V]延伸Traversable[(K,V)].所以它可以像列表一样遍历,但元素是一个元组.这与Java类似Map#entrySet().map方法通过迭代每个元素并向其应用函数来创建新集合.在这种情况下,函数_._2.head是简写的elem: (Property, List[Object]) => elem._2.head._2只是一个返回第二个元素的元组方法.第二个元素是List [Object]并head返回第一个元素

要使结果成为您想要的类型:

import collection.breakOut
val l2: List[Object] = list.groupBy(_.property).map(_._2.head)(breakOut)

简要说明一下,map实际上需要两个参数,一个函数和一个用于构造结果的对象.在第一个代码片段中,您没有看到第二个值,因为它被标记为隐式,因此由编译器从范围中的预定义值列表中提供.结果通常从映射容器中获取.这通常是件好事.List上的map将返回List,Array上的map将返回Array等.但是,在这种情况下,我们想要表示我们想要的容器作为结果.这是使用breakOut方法的地方.它只通过查看所需的结果类型来构造构建器(构建结果的东西).它是一个通用方法,编译器推断它的泛型类型,因为我们明确地将l2键入为List[Object]或保持顺序(假设Object#property是类型)Property):

list.foldRight((List[Object](), Set[Property]())) {
  case (o, cum@(objects, props)) => 
    if (props(o.property)) cum else (o :: objects, props + o.property))
}._1

foldRight是一个接受初始结果的方法和接受元素并返回更新结果的函数.该方法迭代每个元素,根据将函数应用于每个元素并返回最终结果来更新结果.我们从右到左(而不是从左到右foldLeft)因为我们在前面objects- 这是O(1),但是附加是O(N).同时在这里观察好的样式,我们使用模式匹配来提取元素.

在这种情况下,初始结果是空列表和集合的对(元组).列表是我们感兴趣的结果,该集用于跟踪我们已经遇到的属性.在每次迭代中,我们检查组props已经包含属性(Scala中,obj(x)被翻译成obj.apply(x)在Set,该方法apply被def apply(a: A): Boolean也就是说,接受一个元素,如果它存在与否返回真/假).如果属性存在(已经遇到),则结果按原样返回.否则,结果将更新为包含object(o :: objects)并记录属性(props + o.property)

更新:@andreypopp想要一个通用的方法:

import scala.collection.IterableLike
import scala.collection.generic.CanBuildFrom

class RichCollection[A, Repr](xs: IterableLike[A, Repr]){
  def distinctBy[B, That](f: A => B)(implicit cbf: CanBuildFrom[Repr, A, That]) = {
    val builder = cbf(xs.repr)
    val i = xs.iterator
    var set = Set[B]()
    while (i.hasNext) {
      val o = i.next
      val b = f(o)
      if (!set(b)) {
        set += b
        builder += o
      }
    }
    builder.result
  }
}

implicit def toRich[A, Repr](xs: IterableLike[A, Repr]) = new RichCollection(xs)

使用:

scala> list.distinctBy(_.property)
res7: List[Obj] = List(Obj(1), Obj(2), Obj(3))

另请注意,这非常有效,因为我们正在使用构建器.如果您有非常大的列表,则可能需要使用可变HashSet而不是常规集并对性能进行基准测试.

Answer 2

这是一个有点偷偷摸摸但快速的解决方案,保留顺序:

list.filterNot{ var set = Set[Property]()
    obj => val b = set(obj.property); set += obj.property; b}

虽然它在内部使用var,但我认为它比foldLeft-solution更容易理解和阅读.

Answer 3

开始时Scala 2.13,大多数集合现在都提供了一个distinctBy方法,该方法在应用给定的转换函数后返回序列的所有元素,忽略重复项:

list.distinctBy(_.property)

例如:

List(("a", 2), ("b", 2), ("a", 5)).distinctBy(_._1) // List((a,2), (b,2))
List(("a", 2.7), ("b", 2.1), ("a", 5.4)).distinctBy(_._2.floor) // List((a,2.7), (a,5.4))

Answer 4

上面有很多很好的答案。然而，distinctBy已经在 Scala 中，只是在一个不那么明显的地方。也许你可以像这样使用它

def distinctBy[A, B](xs: List[A])(f: A => B): List[A] =
  scala.reflect.internal.util.Collections.distinctBy(xs)(f)

Answer 5

还有一个解决方案

@tailrec
def collectUnique(l: List[Object], s: Set[Property], u: List[Object]): List[Object] = l match {
  case Nil => u.reverse
  case (h :: t) => 
    if (s(h.property)) collectUnique(t, s, u) else collectUnique(t, s + h.prop, h :: u)
}

Answer 6

保留顺序：

def distinctBy[L, E](list: List[L])(f: L => E): List[L] =
  list.foldLeft((Vector.empty[L], Set.empty[E])) {
    case ((acc, set), item) =>
      val key = f(item)
      if (set.contains(key)) (acc, set)
      else (acc :+ item, set + key)
  }._1.toList

distinctBy(list)(_.property)