删除列表中指定相等功能的重复项

问题描述 投票:15回答:6

我有一个List[A],给定一个相等的函数(a:A, b:A) => Boolean,如何删除重复的惯用方法?我一般不能覆盖equalsfor A

我现在想的方式是创建一个包装class AExt与被覆盖的equals,然后

list.map(新的AExt(_))。distinct

但我想知道是否有更清洁的方式。

scala
6个回答
4
投票

我必须说我想我会通过一个Set的中间集合,如果你期望你的Lists可能很长,因为在exists上测试存在(通过findSeq)当然是O(n):

而不是写自定义等于;决定元素相等的属性。所以代替:

def myCustomEqual(a1: A, a2: A) = a1.foo == a2.foo && a1.bar == a2.bar

做一把钥匙。像这样:

type Key = (Foo, Bar)
def key(a: A) = (a.foo, a.bar)

然后你可以将密钥添加到Set,看看你之前是否遇到过它们。

var keys = Set.empty[Key]
((List.empty[A] /: as) { (l, a) => 
  val k = key(a)
  if (keys(k)) l else { keys += k; a +: l  }
}).reverse

当然,在非常短的列表的情况下,这种解决方案具有更差的空间复杂性和可能更差的性能(因为您正在创建额外的对象 - 密钥)。如果你不喜欢折叠中的var,你可能想看看如何使用StateTraverse来自scalaz 7


19
投票

有一种简单(简单)的方法可以做到这一点:

list.groupBy(_.key).mapValues(_.head)

如果您愿意,可以通过功能块替换_.head,立即使用生成的地图,如:

sameElements => { val observedItem = sameElements.head
                  new A (var1 = observedItem.firstAttr,
                         var2 = "SomethingElse") }

为每个不同的元素返回一个新的A

只有一个小问题。上面的代码(list.groupBy(_.key).mapValues(_.head))没有很好地解释删除重复的意图。因此,拥有像distinctIn[A](attr: A => B)distinctBy[A](eq: (A, A) -> Boolean)这样的函数会很棒。


7
投票

使用来自misingFaktor答案的FoocustomEquals

  case class Foo(a: Int, b: Int)
  val (a, b, c, d) = (Foo(3, 4), Foo(3, 1), Foo(2, 5), Foo(2, 5))
  def customEquals(x: Foo, y: Foo) = x.a == y.a

  (Seq(a, b, c, d).foldLeft(Seq[Foo]()) {
    (unique, curr) => {
      if (!unique.exists(customEquals(curr, _)))
        curr +: unique
      else
        unique
    }
  }).reverse

如果结果排序很重要但要删除的副本不重要,则foldRight更可取

  Seq(a, b, c, d).foldRight(Seq[Foo]()) {
    (curr, unique) => {
      if (!unique.exists(customEquals(curr, _)))
        curr +: unique
      else
        unique
    }
  }

3
投票
scala> case class Foo(a: Int, b: Int)
defined class Foo

scala> val (a, b, c, d) = (Foo(3, 4), Foo(3, 1), Foo(2, 5), Foo(2, 5))
a: Foo = Foo(3,4)
b: Foo = Foo(3,1)
c: Foo = Foo(2,5)
d: Foo = Foo(2,5)

scala> def customEquals(x: Foo, y: Foo) = x.a == y.a
customEquals: (x: Foo, y: Foo)Boolean

scala> Seq(a, b, c, d) filter {
     |   var seq = Seq.empty[Foo]
     |   x => {
     |    if(seq.exists(customEquals(x, _))) {
     |      false 
     |    } else { 
     |      seq :+= x
     |      true 
     |    }
     | }
res13: Seq[Foo] = List(Foo(3,4), Foo(2,5))

0
投票
case class Foo (a: Int, b: Int)

val x = List(Foo(3,4), Foo(3,1), Foo(2,5), Foo(2,5))
def customEquals(x : Foo, y: Foo) = (x.a == y.a && x.b == y.b)

x.foldLeft(Nil : List[Foo]) {(list, item) => 
   val exists = list.find(x => customEquals(item, x))
   if (exists.isEmpty) item :: list
   else list
 }.reverse

res0:List [Foo] = List(Foo(3,4),Foo(3,1),Foo(2,5))


0
投票

启动Scala 2.13,我们可以使用新的distinctBy方法,它返回一个序列的元素,忽略==在应用转换函数f后确定的重复项:

def distinctBy [B](f:(A)=> B):列表[A]

例如:

// case class A(a: Int, b: String, c: Double)
// val list = List(A(1, "hello", 3.14), A(2, "world", 3.14), A(1, "hello", 12.3))
list.distinctBy(x => (x.a, x.b)) // List(A(1, "hello", 3.14), A(2, "world", 3.14))
list.distinctBy(_.c)             // List(A(1, "hello", 3.14), A(1, "hello", 12.3))
© www.soinside.com 2019 - 2024. All rights reserved.