scala为键控序列查找top-k元素。

Question

对于第一个元素构成键的一系列事物：

val things = Seq(("key_1", ("first", 1)),("key_1", ("first_second", 11)), ("key_2", ("second", 2)))

我想要计算一个键发生的频率，然后只保留top-k元素。

在熊猫或数据库中，我会：

1. count
2. 将结果加入到原始的和过滤器的

中。

在Scala中，第一部分可以由以下方法处理：

things.groupBy(identity).mapValues(_.size)

这里的第一步是：

things.groupBy(_._1).mapValues(_.map( _._2 ))

但我不确定第二步是什么。在上面的例子中，当查看顶部-1键时，key_1发生两次，因此被选中。所期望的输出结果是top-k键元组的第二个元素：

Seq(("first", 1),("first_second", 11))

编辑

我需要一个适用于2.11.x的解决方案。

Answer 1

这种方法首先按键分组，以获得原始项的键的映射。

您也可以使用OrderedMap或PriorityQueue来进行更有效的top-N计算，但是如果元素不多，那么简单的sortBy也会工作，如图所示。

def valuesOfNMostFrequentKeys(things: Seq[(String, (String, Int))], N: Int = 1) = {
    val grouped: Map[String,Seq[(String, (String, Int))]] = things.groupBy(_._1)

    // "map" array of counts per keys to KV Tuples 
    val countToTuples:Array[(Int, Seq[(String, (String, Int))])]  = grouped.map((kv: (String, Seq[(String, (String, Int))])) => (kv._2.size, kv._2)).toArray
    // sort by count (first item in tuple) descending and take top N
    val sortByCount:Array[(Int, Seq[(String, (String, Int))])] = countToTuples.sortBy(-_._1)
    val topN:Array[(Int, Seq[(String, (String, Int))])] = sortByCount.take(N)

    // extract inner (String, Int) item from list of keys and values, and flatten
    topN.flatMap((kvList: (Int, Seq[(String, (String, Int))])) => kvList._2.map(_._2))
}

valuesOfNMostFrequentKeys(things)

产出：

valuesOfNMostFrequentKeys: (things: Seq[(String, (String, Int))], N: Int)Array[(String, Int)]
res44: Array[(String, Int)] = Array((first,1), (first_second,11))

上面的注释是一个数组，您可能想要执行toSeq --但是这在Scala2.11中是有效的。

Answer 2

看上去：

things.groupBy(_._1)
  .mapValues(e => (e.map(_._2).size, e.map(_._2))).toSeq.map(_._2)
  .sortBy(_._1).reverse.take(2).flatMap(_._2)

计算所需输出。