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

Question

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

Answer 1

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

说明:groupBy 方法接受将元素转换为用于分组的键的函数。 _.property 只是 elem: Object => elem.property 的简写(编译器生成一个唯一的名称，例如 x$1)。现在我们有了一个 map Map[Property, List[Object]]。 Map[K,V] 扩展了 Traversable[(K,V)]。所以它可以像列表一样被遍历，但是元素是一个元组。这与 Java 的 Map#entrySet() 类似。 map 方法通过迭代每个元素并向其应用函数来创建新集合。在本例中，函数为 _._2.head，它是 elem: (Property, List[Object]) => elem._2.head 的简写。 _2 只是 Tuple 的一个返回第二个元素的方法。第二个元素是 List[Object]，head 返回第一个元素

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

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

简单地解释一下，map 实际上需要两个参数，一个函数和一个用于构造结果的对象。在第一个代码片段中，您看不到第二个值，因为它被标记为隐式，因此由编译器从范围内的预定义值列表中提供。结果通常是从映射的容器中获取的。这通常是一件好事。 List 上的映射将返回 List，Array 上的映射将返回 Array 等。但是在这种情况下，我们希望将我们想要的容器表示为结果。这就是使用breakOut方法的地方。它仅通过查看所需的结果类型来构造构建器(构建结果的东西)。它是一个泛型方法，编译器会推断出它的泛型类型，因为我们显式地将 l2 键入为 List[Object]，或者为了保留顺序(假设 Object#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，即接受一个元素并返回true/如果存在或不存在则为 false)。如果该属性存在(已经遇到)，则按原样返回结果。否则，结果将更新为包含对象 (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 而不是常规集合并对性能进行基准测试。