Поиск наиболее часто встречающегося элемента в коллекции?

Каков наилучший способ поиска наиболее часто встречающегося элемента в коллекции? Например:

list = List(1, 3, 4, 4, 2)
list.mostCommon   // => 4        !! This is what I want !!

Хм.. Что можно сделать, это сначала сделать groupBy, а затем map их на length, а затем выбрать самый большой. Итак, вы получите:

Map(1 -> List(1), 4 -> List(4, 4), 3 -> List(3), 2 -> List(2))
(...)
Map(1 -> 1, 4 -> 2, 3 -> 1, 2 -> 1)  // mapped by length. 4 -> 2  since there two 4s

И затем, в конце, выберите ключ (4), который отображает наибольшее число (2). (вложенный вопрос: что это лучший способ сделать это?). Но это похоже на большую работу для такой простой операции.?

Есть ли лучший/более идиоматический способ сделать это?

Ответ 1

Я должен сказать, что:

list.groupBy(identity).mapValues(_.size).maxBy(_._2)._1

Или просто:

list.groupBy(identity).maxBy(_._2.size)._1

На самом деле это не так много работает.

Если вы беспокоитесь о накладных расходах на сбор списков для каждого значения, когда вам нужны только счеты, вы можете сделать следующее:

list.foldLeft(Map.empty[Int, Int].withDefaultValue(0)) {
  case (m, v) => m.updated(v, m(v) + 1)
}.maxBy(_._2)._1

Или даже следить за максимумом, когда вы идете, чтобы избежать дополнительного обхода в конце:

list.foldLeft(
  Map.empty[Int, Int].withDefaultValue(0), -1 -> Double.NegativeInfinity
) {
  case ((m, (maxV, maxCount)), v) =>
    val count = m(v) + 1
    if (count > maxCount) (m.updated(v, count), v -> count)
    else (m.updated(v, count), maxV -> maxCount)
}._2._1

Это, очевидно, гораздо менее удобочитаемо, чем однострочные выше, хотя я бы рекомендовал придерживаться их, если вы не можете показать (например, с бенчмаркингом, а не спекуляцией), что они являются узким местом в вашем приложении.

Ответ 2

Я не думаю, что это действительно лучше, но вы можете сделать это:

List(1, 3, 4, 4, 2).groupBy(identity).maxBy(_._2.size)._1

Не самое приятное решение. То, что вы хотите, это способ использования maxBy в списке, а затем ссылаться на список следующим образом:

val someList = List(1, 3, 4, 4, 2)
someList.maxBy(x => list.count(_ == x))

Ответ 3

Нет, я думаю, что это лучший способ. Но это не так много работы...

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

дает вам

Map(2 -> 1, 4 -> 2, 1 -> 2, 3 -> 1)

то, например, вы можете взять его .maxBy(_._2) (EDITED: thanks @Travis Brown!) и получить кортеж (4,2) (число, которое происходит чаще всего и сколько раз оно происходит)

Если вы поклонник однострочного интерфейса:

scala> List(1, 3, 4, 1, 4, 2).groupBy(identity).mapValues(_.size).maxBy(_._2)
res0: (Int, Int) = (4,2)

Ответ 4

другой вариант:

val x = List(1, 3, 4, 1, 4, 2, 5, 5, 5)
 x.distinct.foldLeft((0,0))((a, b) => {
     val cnt = x.count(_ == b);
   if (cnt > a._1) (cnt, b) else a
 })._2

Ответ 5

Начиная с Scala 2.13, мы можем использовать:

K)(f:A=>B)(reduce:(B,B)=>B):scala.collection.immutable.Map[K,B]):scala.collection.immutable.Map[K,B] rel="nofollow noreferrer"> List::groupMapReduce который (как следует из его названия) является эквивалентом groupBy за которым следует mapValues и шаг сокращения.
B):Option[(K,V)] rel="nofollow noreferrer"> Map::maxByOption вместо простого maxBy для обработки пустых списков:

List(1, 3, 4, 4, 2, 3).groupMapReduce(identity)(_ => 1)(_+_).maxByOption(_._2).map(_._1)
// Option[Int] = Some(4)

Это:

group элементы (групповая часть группы MapReduce)
map каждое вхождение сгруппированного значения в 1 (часть карты группы Map Reduce)
reduce значения в группе значений (_ + _), суммируя их (уменьшить часть groupMap Reduce).
наконец получает необязательный максимум по nbr вхождений и отображает его, чтобы получить соответствующий элемент.

Если вы знаете, что ваш список не пуст, то также работает простой maxBy:

List(1, 3, 4, 4, 2, 3).groupMapReduce(identity)(_ => 1)(_+_).maxBy(_._2)._1
// 4

Часть groupMapReduce является эквивалентной версией, выполненной за один проход в последовательности:

List(1, 3, 4, 4, 2, 3).groupBy(identity).mapValues(_.map(_ => 1).reduce(_+_))