Почему maxBy возвращает только один элемент?

Question

После этого вопроса Интересно , почему maxBy из Traversable[T] возвращает единственное значение T вместо последовательности T (список или аналогичный). Это выглядит как довольно распространенный случай. Например (из предыдущего вопроса):

Для списка студентов с их оценками

List(Student("Mike", "A"), Student("Pete", "B"), Student("Paul", A))"

Я хочу получить

List(Student("Mike", "A"), Student("Paul", A))

Кто-нибудь знает о какой-либо стандартной реализации maxBy, которая возвращает последовательность найденных элементов?

Answer 1

Нет единой команды.Самое короткое из известных мне - которые группируют все , а не только максимальное значение в качестве промежуточного значения - это

xs.groupBy(f).maxBy(_._1)._2

. Для большей эффективности складки являются хорошими инструментами общего назначения для поискасуммы и максимумы и различные подобные вещи.По сути, всякий раз, когда вам нужно перебрать свою коллекцию, набирая какой-то ответ, используйте фолд.В этом случае

(xs.head /: xs.tail) {
  (biggest, next) => if (f(biggest) < f(next)) next else biggest
}

выполнит maxBy(f), если вы не возражаете пересмотреть функцию дважды для каждого элемента, в то время как

((xs.head, f(xs.head)) /: xs.tail) {
  case (scored, next) =>
    val nextscore = f(next)
    if (scored._2 < nextscore) (next, nextscore)
    else scored
}._1

сделает это только с однимоценка за элемент.Если вы хотите сохранить последовательность, вы можете изменить ее на

(Seq(xs.head) /: xs.tail) {
  (bigs, next) =>
    if (f(bigs.head) > f(next)) bigs
    else if (f(bigs.head) < f(next)) Seq(next)
    else bigs :+ next
}

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

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

val result = {
  var bigs = xs.take(0).toList
  var bestSoFar = f(xs.head)
  xs.foreach{ x =>
    if (bigs.isEmpty) bigs = x :: bigs
    else {
      val fx = f(x)
      if (fx > bestSoFar) {
        bestSoFar = fx
        bigs = List(x)
      }
      else if (fx == bestSoFar) bigs = x :: bigs
    }
  }
  bigs
}

(это будет возвращаться в обратном порядке, между прочим).

Answer 2

Если у вас есть

case class Student(name: String, grade: String)
val students = List(Student("Mike", "A"), Student("Pete", "B"), Student("Paul", "A"))

, то это довольно простое O (N) решение, которое не включает создание промежуточных списков:

val bestGrade = students.minBy(_.grade).grade
students.filter(_.grade == bestGrade)    //List(Student(Mike,A), Student(Paul,A))

Мы используем minBy здесь из-за упорядочения строк.

Как метод:

def multiMinBy[A,B](xs: Traversable[A])(f: A => B)(implicit ord: Ordering[B]) = {
  val minVal = f(xs minBy f)
  xs filter (f(_) == minVal)
}

scala> multiMinBy(students)(_.grade)
res26: Traversable[Student] = List(Student(Mike,A), Student(Paul,A))

Answer 3

В стандартных библиотеках, о которых я знаю, нет функции.

maxBy' :: (a -> a -> Ordering) -> [a] -> [a]
maxBy' _ [] = undefined
maxBy' f (x:xs) = foldr step [x] xs
  where step y acc@(z:_) = case f y z of
          GT -> [y]
          EQ -> y:acc
          LT -> acc

[править] Упс, это вопрос Scala:)

Переведено в Scala, дан список xs и компаратор compare:

(List(xs.head) /: xs.tail) { (acc, y) =>
  y compare acc.head match {
    case 1  => List(y)
    case 0  => y :: acc
    case -1 => acc
  }
}

Answer 4

ученик и список учеников:

class Student (val name: String, val grade: String) {
  override def toString = grade + "::" + name
}
val students = List (new Student ("Mike", "A"), new Student ("Pete", "B"), new Student ("Paul", "A"))

Функциональное тауркурсивное решение, параметризованное по списку Т и способ сравнения 2 Т:

// ext: extreme, o: other, s:sample(student)
@tailrec
def collectExtreme [T](l: List[T], ext: ((T, T) => Int), carry: List[T]=List.empty) : List[T] =
  l match {
    case Nil => carry
    case s :: xs => carry match {
      case Nil => collectExtreme (xs, ext, List (s))
      case o :: _ => ext (s, o) match {
        case 0 => collectExtreme (xs, ext, s :: carry)
        case -1=> collectExtreme (xs, ext, l)
        case 1 => collectExtreme (xs, ext, carry)
      }
    }
  }
def cmp (s: Student, o: Student): Int = s.grade(0) - o.grade(0) 

collectExtreme (students, cmp) 

Работает только 1 раз над коллекцией тоже.