diff options
author | yllan <yllan@me.com> | 2013-06-27 16:13:01 +0800 |
---|---|---|
committer | yllan <yllan@me.com> | 2013-07-06 11:23:44 +0800 |
commit | ece18346582ffccb6d05b48b647ba5439aa2cca3 (patch) | |
tree | 8577d1c374d13d111ebc7d4b58ece60258b44b17 /src/library | |
parent | b5f70c844c77ac974118d07a9d53e3fd98a69e5f (diff) | |
download | scala-ece18346582ffccb6d05b48b647ba5439aa2cca3.tar.gz scala-ece18346582ffccb6d05b48b647ba5439aa2cca3.tar.bz2 scala-ece18346582ffccb6d05b48b647ba5439aa2cca3.zip |
SI-7614 Minimize the times of evaluation f in TraversableOnce.maxBy/minBy.
In the previous implementation, maxBy/minBy will evaluate most of its elements
with f twice to get the ordering. That results (2n - 2) evaluations of f.
I save both the element and result of evaluation to a tuple so that it doesn't
need to re-evaluate f on next comparison. Thus only n evaluations of f, that is
the optimal.
Note that the original implementation always returns the first matched if more
than one element evaluated to same largest/smallest value of f. I document
this behavior explicitly in this commit as well.
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/GenTraversableOnce.scala | 26 | ||||
-rw-r--r-- | src/library/scala/collection/TraversableOnce.scala | 28 |
2 files changed, 52 insertions, 2 deletions
diff --git a/src/library/scala/collection/GenTraversableOnce.scala b/src/library/scala/collection/GenTraversableOnce.scala index d966c7324b..3d1b2c4278 100644 --- a/src/library/scala/collection/GenTraversableOnce.scala +++ b/src/library/scala/collection/GenTraversableOnce.scala @@ -363,8 +363,34 @@ trait GenTraversableOnce[+A] extends Any { */ def max[A1 >: A](implicit ord: Ordering[A1]): A + /** Finds the first element which yields the largest value measured by function f. + * + * @param cmp An ordering to be used for comparing elements. + * @tparam B The result type of the function f. + * @param f The measuring function. + * @return the first element of this $coll with the largest value measured by function f + * with respect to the ordering `cmp`. + * + * @usecase def maxBy[B](f: A => B): A + * @inheritdoc + * + * @return the first element of this $coll with the largest value measured by function f. + */ def maxBy[B](f: A => B)(implicit cmp: Ordering[B]): A + /** Finds the first element which yields the smallest value measured by function f. + * + * @param cmp An ordering to be used for comparing elements. + * @tparam B The result type of the function f. + * @param f The measuring function. + * @return the first element of this $coll with the smallest value measured by function f + * with respect to the ordering `cmp`. + * + * @usecase def minBy[B](f: A => B): A + * @inheritdoc + * + * @return the first element of this $coll with the smallest value measured by function f. + */ def minBy[B](f: A => B)(implicit cmp: Ordering[B]): A def forall(pred: A => Boolean): Boolean diff --git a/src/library/scala/collection/TraversableOnce.scala b/src/library/scala/collection/TraversableOnce.scala index 526c36dda7..634807b29f 100644 --- a/src/library/scala/collection/TraversableOnce.scala +++ b/src/library/scala/collection/TraversableOnce.scala @@ -221,13 +221,37 @@ trait TraversableOnce[+A] extends Any with GenTraversableOnce[A] { if (isEmpty) throw new UnsupportedOperationException("empty.maxBy") - reduceLeft((x, y) => if (cmp.gteq(f(x), f(y))) x else y) + var maxF: B = null.asInstanceOf[B] + var maxElem: A = null.asInstanceOf[A] + var first = true + + for (elem <- self) { + val fx = f(elem) + if (first || cmp.gt(fx, maxF)) { + maxElem = elem + maxF = fx + first = false + } + } + maxElem } def minBy[B](f: A => B)(implicit cmp: Ordering[B]): A = { if (isEmpty) throw new UnsupportedOperationException("empty.minBy") - reduceLeft((x, y) => if (cmp.lteq(f(x), f(y))) x else y) + var minF: B = null.asInstanceOf[B] + var minElem: A = null.asInstanceOf[A] + var first = true + + for (elem <- self) { + val fx = f(elem) + if (first || cmp.lt(fx, minF)) { + minElem = elem + minF = fx + first = false + } + } + minElem } /** Copies all elements of this $coll to a buffer. |