scala - 如何在Scala中实现具有多个最大值的maxBy

Question

我需要一个 maxBy 在相等的情况下返回所有最大值。

这是签名和第一个实现:

def maxBy[A, B](as: Seq[A])(f: A => B)(implicit cmp: Ordering[B]) : Seq[A] = 
  as.groupBy(f).toList.maxBy(_._1)._2

例子 :

maxBy(Seq(("a", "a1"),("a", "a2"),("b", "b1"),("b", "b2")))(_._1)
res6: Seq[(String, String)] = List(("b", "b1"), ("b", "b2"))

更新了@thearchetypepaul 评论

  def maxBy[A, B](l: Seq[A])(f: A => B)(implicit cmp: Ordering[B]) : Seq[A] = {
    l.foldLeft(Seq.empty[A])((b, a) =>
      b.headOption match {
        case None => Seq(a)
        case Some(v) => cmp.compare(f(a), f(v)) match {
          case -1 => b
          case 0 => b.+:(a)
          case 1 => Seq(a)
        }
      }
    )
  }

有没有更好的办法 ？

Answer 1

(1) Ordering#compare promise 用负数、正数或零数来表示三个可能的结果，而不一定是 -1、1 或 0。

(2) Option#fold是 generally (虽然不是普遍的)被认为比模式匹配更惯用。

(3) 您调用f每个元素可能多次。 TraversableOnce#maxBy在它是 fixed 之前曾经这样做过在 2.11 中。

(4) 您只接受Seq . Scala 库努力使用 CanBuildFrom概括算法；你可能也想要。

(5) 可以使用语法糖B : Ordering如果你愿意。

(6) 您在 Seq 前面加上.这比追加要快，因为 List 的追加是 O(1)并且附加是O(n)。但是你以相反的顺序结束了结果。 foldRight将纠正这一点。 (或者您可以调用 reverse 了解最终结果。)

如果要允许使用 CanBuildFrom ,

def maxBy[A, Repr, That, B : Ordering](elements: TraversableLike[A, Repr])(f: A => B)(implicit bf: CanBuildFrom[Repr, A, That]): That = {
  val b = bf()
  elements.foldLeft(Option.empty[B]) { (best, element) =>
    val current = f(element)
    val result = best.fold(0)(implicitly[Ordering[B]].compare(current, _))
    if (result > 0) {
      b.clear()
    }
    if (result >= 0) {
      b += element
      Some(current)
    } else {
      best
    }
  }
  b.result
}

如果您想使用 TraversableOnce ,

def maxBy[A, B : Ordering](elements: TraversableOnce[A])(f: A => B): Seq[A] = {
  elements.foldRight((Option.empty[B], List.empty[A])) { case (element, (best, elements)) =>
    val current = f(element)
    val result = best.fold(0)(implicitly[Ordering[B]].compare(current, _))
    if (result > 0) {
      (Some(current), List(element))
    } else {
      (best, if (result == 0) element +: elements else elements)
    }
  }._2
}