从没有二次时间复杂度的列表中获取所有重复记录？

Question

下面是我的列表，其中包含列名称：国家/地区、性别和年龄。

scala> funList
res1: List[(String, String, String)] = List((india,M,15), (usa,F,25), (australia,M,35), (kenya,M,55), (russia,M,75), (china,T,95), (england,F,65), (germany,F,25), (finland,M,45), (australia,F,35))

我的目标是找到具有（国家、年龄）组合的重复记录。请注意，我只想获取所有重复记录并忽略其他记录。并且列表还应包含具有重复记录的其他列值。

输出应该是这样的：

australia,M,35
australia,F,35

如果你没有 groupBy 操作并且没有 n*square 复杂性，那就太好了。 GroupBy 很好，除非它弄乱了我的输出。

Answer 1

没有groupBy()。不确定复杂性。

val keys = funList.map{case (a,b,c) => (a,c)}  //isolate elements of interest
val dups = keys diff keys.distinct             //find the duplicates
funList.filter{case (a,b,c) => dups.contains((a,c))}
//res0: List[(String, String, String)] = List((australia,M,35), (australia,F,35))

Answer 2

不确定您所说的 groupBy 可能会扰乱输出是什么意思。您可以按如下方式使用它，您将得到您要查找的重复项列表：

// input
val items = List(("india","M",15), ("usa","F",25), ("australia","M",35), ("kenya","M",55), ("russia","M",75), ("china","T",95), ("england","F",65), ("germany","F",25), ("finland","M",45), ("australia","F",35))

items.
  groupBy { case (nation, _, age) => nation -> age }. // group by relevant items
  filter(_._2.length > 1).                            // keep only duplicates
  flatMap(_._2)                                       // get them and flatten the result

或者您可能有兴趣使用 groupBy 作为您自己的函数的基础，该函数通过键对值进行存储并通过某些谓词过滤结果，例如以下：

implicit class FilterGroups[A, CC[X] <: Iterable[X]](self: CC[A]) {
  import scala.collection.mutable
  import scala.collection.mutable.Builder
  import scala.collection.generic.CanBuildFrom
  def filterGroups[K, That](f: A => K)(p: CC[A] => Boolean)(implicit bfs: CanBuildFrom[CC[A], A, CC[A]], bf: CanBuildFrom[CC[A], A, That]): That = {
    val m = mutable.Map.empty[K, Builder[A, CC[A]]]
    for (elem <- self) {
      val key = f(elem)
      val bldr = m.getOrElseUpdate(key, bfs())
      bldr += elem
    }
    val b = bf()
    for {
      (_, v) <- m
      group = v.result if p(group)
      elem <- group
    } b += elem
    b.result
  }
}

然后您将按如下方式调用它：

// bucket by the first function, filter by the second one
items.filterGroups(tuple => (tuple._1, tuple._3))(_.length > 1)

并且，就像上面一样，取回所需的项目列表：

List((australia,M,35), (australia,F,35))

替代解决方案的唯一主要优点是输出类型与输入相同，而使用 groupBy 会强制您的结果类型为 Iterable[(String, String, Int)]。不确定你的意思是不是 弄乱了输出 .

无论哪种方式，我想说时间复杂度实际上是线性的（我们必须一次传递给桶，一次传递给过滤器，但我们仍然可以摆脱 big-O 表示法中的常量）。这当然意味着 space 复杂性也与集合大小有关（因为我们对原始结果进行了存储）。

最后一点：您可能不想在测量尺寸时使用列表，因为它的复杂性是线性的。我的解决方案和使用 groupBy 的解决方案都使用与原始集合相同类型的构建器，因此您可能希望使用 Vector 或其他带有 O(1)[ 的集合=43=] 用于计算 length.

但是 正确的答案可能是只使用 groupBy，这对任何其他 Scala 开发人员来说更简单明了（尽管您可能还想使用惰性通过迭代查看以防止不必要的双重传递数据）。

从没有二次时间复杂度的列表中获取所有重复记录？

Fetch all the duplicate records from a list without quadratic time complexity?

scala

performance

time-complexity

user-defined-functions

scala-collections