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

Question

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

Answer 1

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

说明： groupBy 方法接受将元素转换为用于分组的键的函数。 _.property 只是 elem: Object => 的简写elem.property （编译器生成一个唯一的名称，例如 x$1）。现在我们有了一个地图 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 的类型为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 而不是常规集合并对性能进行基准测试。

Answer 2

从 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 3

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

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

虽然它在内部使用 var，但我认为它比 FoldLeft 解决方案更容易理解和阅读。

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

保留订单：

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)

Answer 6

另一种解决方案

@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 7

我找到了一种让它与 groupBy 一起使用的方法，只需一个中间步骤：

def distinctBy[T, P, From[X] <: TraversableLike[X, From[X]]](collection: From[T])(property: T => P): From[T] = {
  val uniqueValues: Set[T] = collection.groupBy(property).map(_._2.head)(breakOut)
  collection.filter(uniqueValues)
}

像这样使用它：

scala> distinctBy(List(redVolvo, bluePrius, redLeon))(_.color)
res0: List[Car] = List(redVolvo, bluePrius)

与 IttayD 的第一个解决方案类似，但它根据唯一值集过滤原始集合。如果我的期望是正确的，这将执行三次遍历：一次用于 groupBy，一次用于 map，一次用于 filter。它保持原始集合的顺序，但不一定采用每个属性的第一个值。例如，它可能会返回 List(bluePrius, redLeon)。

当然，IttayD 的解决方案仍然更快，因为它只进行一次遍历。

我的解决方案还有一个缺点，如果集合中有实际上相同的 Car，则两者都将出现在输出列表中。可以通过删除 filter 并直接返回 uniqueValues（类型为 From[T]）来解决此问题。但是，似乎 CanBuildFrom[Map[P, From[T]], T, From[T]] 不存在...欢迎建议！

Answer 8

通过集合和从记录到键的函数，可以生成按键区分的记录列表。目前尚不清楚 groupBy 是否会保留原始集合中的顺序。它甚至可能取决于集合的类型。我猜测 head 或 last 将始终产生最早的元素。

collection.groupBy(keyFunction).values.map(_.head)

Scala 什么时候会获得 nubBy ？它已经在 Haskell 中存在了几十年了。

Answer 9

如果您想删除重复项并保留列表的顺序，您可以尝试以下两个行：

val tmpUniqueList = scala.collection.mutable.Set[String]()
val myUniqueObjects = for(o <- myObjects if tmpUniqueList.add(o.property)) yield o

Answer 10

这完全是 @IttayD 答案的翻版，但不幸的是我没有足够的声誉来发表评论。
您可以简单地创建一个隐式类，而不是创建一个隐式函数来转换迭代器：

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

implicit 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
  }
}