scala найти элементы top-k для последовательности ключей - PullRequest
Новая
       39

scala найти элементы top-k для последовательности ключей

0 голосов
/ 22 февраля 2020

Для последовательности вещей, где первый элемент составляет ключ: 

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

Я хочу посчитать, как часто встречается ключ, а затем сохранить только элементы top-k.

В pandas или базе данных я бы:

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

edit

Мне нужно решение, которое работает для 2.11.x.

Ответы [ 2 ]

1 голос
/ 23 февраля 2020

Этот подход сначала группирует по ключам, чтобы получить карту ключей к оригинальным элементам.

Вы также можете использовать 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 - но это работает в Scala 2.11.

0 голосов
/ 22 февраля 2020

Похоже: 

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

вычисляет нужные выходные данные

...