diff options
author | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2015-03-23 15:37:57 -0700 |
---|---|---|
committer | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2015-03-23 15:37:57 -0700 |
commit | 88d4c15dfe4862b6d73fe54f00da5f2ea075b3f5 (patch) | |
tree | e89446456aec22480d3f442e557584a25401bd89 | |
parent | 3c7b1e3d953703582aae81506f8b27732a603bfe (diff) | |
parent | 049e66cee8c27e1847044df43bc33c7d8421097e (diff) | |
download | scala-88d4c15dfe4862b6d73fe54f00da5f2ea075b3f5.tar.gz scala-88d4c15dfe4862b6d73fe54f00da5f2ea075b3f5.tar.bz2 scala-88d4c15dfe4862b6d73fe54f00da5f2ea075b3f5.zip |
Merge pull request #4338 from Ichoran/opt-SeqLike-2.11.x
Performance optimization - SeqLike
-rw-r--r-- | src/library/scala/collection/SeqLike.scala | 75 |
1 files changed, 50 insertions, 25 deletions
diff --git a/src/library/scala/collection/SeqLike.scala b/src/library/scala/collection/SeqLike.scala index 329273df5b..66fce0f902 100644 --- a/src/library/scala/collection/SeqLike.scala +++ b/src/library/scala/collection/SeqLike.scala @@ -447,9 +447,11 @@ trait SeqLike[+A, +Repr] extends Any with IterableLike[A, Repr] with GenSeqLike[ def diff[B >: A](that: GenSeq[B]): Repr = { val occ = occCounts(that.seq) val b = newBuilder - for (x <- this) - if (occ(x) == 0) b += x - else occ(x) -= 1 + for (x <- this) { + val ox = occ(x) // Avoid multiple map lookups + if (ox == 0) b += x + else occ(x) = ox - 1 + } b.result() } @@ -476,11 +478,13 @@ trait SeqLike[+A, +Repr] extends Any with IterableLike[A, Repr] with GenSeqLike[ def intersect[B >: A](that: GenSeq[B]): Repr = { val occ = occCounts(that.seq) val b = newBuilder - for (x <- this) - if (occ(x) > 0) { + for (x <- this) { + val ox = occ(x) // Avoid multiple map lookups + if (ox > 0) { b += x - occ(x) -= 1 + occ(x) = ox - 1 } + } b.result() } @@ -509,22 +513,35 @@ trait SeqLike[+A, +Repr] extends Any with IterableLike[A, Repr] with GenSeqLike[ def patch[B >: A, That](from: Int, patch: GenSeq[B], replaced: Int)(implicit bf: CanBuildFrom[Repr, B, That]): That = { val b = bf(repr) - val (prefix, rest) = this.splitAt(from) - b ++= toCollection(prefix) + var i = 0 + val it = this.iterator + while (i < from && it.hasNext) { + b += it.next() + i += 1 + } b ++= patch.seq - b ++= toCollection(rest).view drop replaced + i = replaced + while (i > 0 && it.hasNext) { + it.next() + i -= 1 + } + while (it.hasNext) b += it.next() b.result() } def updated[B >: A, That](index: Int, elem: B)(implicit bf: CanBuildFrom[Repr, B, That]): That = { if (index < 0) throw new IndexOutOfBoundsException(index.toString) val b = bf(repr) - val (prefix, rest) = this.splitAt(index) - val restColl = toCollection(rest) - if (restColl.isEmpty) throw new IndexOutOfBoundsException(index.toString) - b ++= toCollection(prefix) + var i = 0 + val it = this.iterator + while (i < index && it.hasNext) { + b += it.next() + i += 1 + } + if (!it.hasNext) throw new IndexOutOfBoundsException(index.toString) b += elem - b ++= restColl.view.tail + it.next() + while (it.hasNext) b += it.next() b.result() } @@ -544,8 +561,9 @@ trait SeqLike[+A, +Repr] extends Any with IterableLike[A, Repr] with GenSeqLike[ def padTo[B >: A, That](len: Int, elem: B)(implicit bf: CanBuildFrom[Repr, B, That]): That = { val b = bf(repr) - b.sizeHint(length max len) - var diff = len - length + val L = length + b.sizeHint(math.max(L, len)) + var diff = len - L b ++= thisCollection while (diff > 0) { b += elem @@ -617,16 +635,23 @@ trait SeqLike[+A, +Repr] extends Any with IterableLike[A, Repr] with GenSeqLike[ */ def sorted[B >: A](implicit ord: Ordering[B]): Repr = { val len = this.length - val arr = new ArraySeq[A](len) - var i = 0 - for (x <- this) { - arr(i) = x - i += 1 - } - java.util.Arrays.sort(arr.array, ord.asInstanceOf[Ordering[Object]]) val b = newBuilder - b.sizeHint(len) - for (x <- arr) b += x + if (len == 1) b ++= this + else if (len > 1) { + b.sizeHint(len) + val arr = new Array[AnyRef](len) // Previously used ArraySeq for more compact but slower code + var i = 0 + for (x <- this) { + arr(i) = x.asInstanceOf[AnyRef] + i += 1 + } + java.util.Arrays.sort(arr, ord.asInstanceOf[Ordering[Object]]) + i = 0 + while (i < arr.length) { + b += arr(i).asInstanceOf[A] + i += 1 + } + } b.result() } |