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

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

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

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

为了使结果成为你想要的types:

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

简单地说, map实际上需要两个参数,一个函数和一个用于构造结果的对象。 在第一个代码片段中,您看不到第二个值,因为它被标记为隐式的,并且由编译器从范围中的预定义值列表中提供。 结果通常从映射的容器中获得。 这通常是一件好事。 在List上的映射将返回List,Array上的映射将返回Array等。然而,在这种情况下,我们想要表示我们想要的容器作为结果。 这是使用breakOut方法的地方。 它只通过查看所需的结果types来构build一个构build器(构build结果的东西)。 这是一个通用的方法,编译器推断它的genericstypes,因为我们明确地键入l2为List[Object]或者为了保持顺序(假定Object#property的types为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)。 同时观察这里的好样式,我们使用模式匹配来提取元素。

在这种情况下,初始结果是一个空列表和一个集合的一个对(元组)。 该列表是我们感兴趣的结果,并且该集合用于跟踪我们已经遇到的属性。 在每一次迭代中,我们检查set props已经包含属性(在Scala中, obj(x)被转换为obj.apply(x) ,在Set apply方法是def apply(a: A): Boolean 。 ,接受一个元素,如果它存在或不存在则返回true / false)。 如果该属性存在(已经遇到),结果将按原样返回。 否则,结果被更新为包含对象( o :: objects )并且logging属性( 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而不是一个常规集合,并且对性能进行基准testing。

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

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

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

多一个解决scheme

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

保存顺序:

 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) 

我find了一种方法,使它与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的第一个解决scheme类似,但它基于一组唯一值过滤原始集合。 如果我的期望是正确的,这会做三个遍历:一个是groupBy ,一个是map ,一个是filter 。 它维护原始集合的顺序,但不一定为每个属性取第一个值。 例如,它可能已经返回List(bluePrius, redLeon)

当然,IttayD的解决scheme还是更快,因为它只有一个遍历。

我的解决scheme还有一个缺点,如果集合中的Car实际上是相同的,则两者都将在输出列表中。 这可以通过删除filter并直接返回uniqueValues来解决,typesFrom[T] 。 然而,看起来像CanBuildFrom[Map[P, From[T]], T, From[T]]不存在…build议欢迎!

我不知道你正在使用哪个版本的Scala,但2.8.2肯定有

 list.distinct