diff options
author | michelou <michelou@epfl.ch> | 2007-10-31 15:10:33 +0000 |
---|---|---|
committer | michelou <michelou@epfl.ch> | 2007-10-31 15:10:33 +0000 |
commit | 85f19da7d2d82f6987fd9bbbc3438568e4255cd3 (patch) | |
tree | 0b1704aedd9ace30c6ab19360f1189c2e85c854e | |
parent | 3124ea56589f809bf64c43e9924fb82df21ad765 (diff) | |
download | scala-85f19da7d2d82f6987fd9bbbc3438568e4255cd3.tar.gz scala-85f19da7d2d82f6987fd9bbbc3438568e4255cd3.tar.bz2 scala-85f19da7d2d82f6987fd9bbbc3438568e4255cd3.zip |
reverted refactoring for efficiency
-rw-r--r-- | src/library/scala/util/Sorting.scala | 229 |
1 files changed, 206 insertions, 23 deletions
diff --git a/src/library/scala/util/Sorting.scala b/src/library/scala/util/Sorting.scala index 61a29ea767..9766a1aa77 100644 --- a/src/library/scala/util/Sorting.scala +++ b/src/library/scala/util/Sorting.scala @@ -6,7 +6,7 @@ ** |/ ** \* */ -// $Id: $ +// $Id$ package scala.util @@ -190,7 +190,7 @@ object Sorting { sort2(off, len) } - private def sort1[T <: AnyVal](x: Array[T], off: Int, len: Int, compare: (T, T) => Int) { + private def sort1(x: Array[Int], off: Int, len: Int) { def swap(a: Int, b: Int) { val t = x(a) x(a) = x(b) @@ -208,13 +208,10 @@ object Sorting { } } def med3(a: Int, b: Int, c: Int) = { - val ab = compare(x(a), x(b)) - val bc = compare(x(b), x(c)) - val ac = compare(x(a), x(c)) - if (ab < 0) { - if (bc < 0) b else if (ac < 0) c else a + if (x(a) < x(b)) { + if (x(b) < x(c)) b else if (x(a) < x(c)) c else a } else { - if (bc > 0) b else if (ac > 0) c else a + if (x(b) > x(c)) b else if (x(a) > x(c)) c else a } } def sort2(off: Int, len: Int) { @@ -223,7 +220,7 @@ object Sorting { var i = off while (i < len + off) { var j = i - while (j>off && compare(x(j-1), x(j)) > 0) { + while (j>off && x(j-1) > x(j)) { swap(j, j-1) j -= 1 } @@ -252,23 +249,19 @@ object Sorting { var d = c var done = false while (!done) { - var xv = compare(x(b), v) - while (b <= c && xv <= 0) { - if (xv == 0) { + while (b <= c && x(b) <= v) { + if (x(b) == v) { swap(a, b) a += 1 } b += 1 - if (b <= c) xv = compare(x(b), v) } - xv = compare(x(c), v) - while (c >= b && xv >= 0) { - if (xv == 0) { + while (c >= b && x(c) >= v) { + if (x(c) == v) { swap(c, d) d -= 1 } c -= 1 - if (c >= b) xv = compare(x(c), v) } if (b > c) { done = true @@ -298,16 +291,206 @@ object Sorting { sort2(off, len) } - private def sort1(x: Array[Int], off: Int, len: Int) { - sort1(x, off, len, (x: Int, y: Int) => x compare y) - } - private def sort1(x: Array[Double], off: Int, len: Int) { - sort1(x, off, len, (x: Double, y: Double) => x compare y) + def swap(a: Int, b: Int) { + val t = x(a) + x(a) = x(b) + x(b) = t + } + def vecswap(_a: Int, _b: Int, n: Int) { + var a = _a + var b = _b + var i = 0 + while (i < n) { + swap(a, b) + i += 1 + a += 1 + b += 1 + } + } + def med3(a: Int, b: Int, c: Int) = { + if (x(a) < x(b)) { + if (x(b) < x(c)) b else if (x(a) < x(c)) c else a + } else { + if (x(b) > x(c)) b else if (x(a) > x(c)) c else a + } + } + def sort2(off: Int, len: Int) { + // Insertion sort on smallest arrays + if (len < 7) { + var i = off + while (i < len + off) { + var j = i + while (j>off && x(j-1) > x(j)) { + swap(j, j-1) + j -= 1 + } + i += 1 + } + } else { + // Choose a partition element, v + var m = off + (len >> 1) // Small arrays, middle element + if (len > 7) { + var l = off + var n = off + len - 1 + if (len > 40) { // Big arrays, pseudomedian of 9 + var s = len / 8 + l = med3(l, l+s, l+2*s) + m = med3(m-s, m, m+s) + n = med3(n-2*s, n-s, n) + } + m = med3(l, m, n) // Mid-size, med of 3 + } + val v = x(m) + + // Establish Invariant: v* (<v)* (>v)* v* + var a = off + var b = a + var c = off + len - 1 + var d = c + var done = false + while (!done) { + while (b <= c && x(b) <= v) { + if (x(b) == v) { + swap(a, b) + a += 1 + } + b += 1 + } + while (c >= b && x(c) >= v) { + if (x(c) == v) { + swap(c, d) + d -= 1 + } + c -= 1 + } + if (b > c) { + done = true + } else { + swap(b, c) + c -= 1 + b += 1 + } + } + + // Swap partition elements back to middle + val n = off + len + var s = Math.min(a-off, b-a) + vecswap(off, b-s, s) + s = Math.min(d-c, n-d-1) + vecswap(b, n-s, s) + + // Recursively sort non-partition-elements + s = b - a + if (s > 1) + sort2(off, s) + s = d - c + if (s > 1) + sort2(n-s, s) + } + } + sort2(off, len) } private def sort1(x: Array[Float], off: Int, len: Int) { - sort1(x, off, len, (x: Float, y: Float) => x compare y) + def swap(a: Int, b: Int) { + val t = x(a) + x(a) = x(b) + x(b) = t + } + def vecswap(_a: Int, _b: Int, n: Int) { + var a = _a + var b = _b + var i = 0 + while (i < n) { + swap(a, b) + i += 1 + a += 1 + b += 1 + } + } + def med3(a: Int, b: Int, c: Int) = { + if (x(a) < x(b)) { + if (x(b) < x(c)) b else if (x(a) < x(c)) c else a + } else { + if (x(b) > x(c)) b else if (x(a) > x(c)) c else a + } + } + def sort2(off: Int, len: Int) { + // Insertion sort on smallest arrays + if (len < 7) { + var i = off + while (i < len + off) { + var j = i + while (j>off && x(j-1) > x(j)) { + swap(j, j-1) + j -= 1 + } + i += 1 + } + } else { + // Choose a partition element, v + var m = off + (len >> 1) // Small arrays, middle element + if (len > 7) { + var l = off + var n = off + len - 1 + if (len > 40) { // Big arrays, pseudomedian of 9 + var s = len / 8 + l = med3(l, l+s, l+2*s) + m = med3(m-s, m, m+s) + n = med3(n-2*s, n-s, n) + } + m = med3(l, m, n) // Mid-size, med of 3 + } + val v = x(m) + + // Establish Invariant: v* (<v)* (>v)* v* + var a = off + var b = a + var c = off + len - 1 + var d = c + var done = false + while (!done) { + while (b <= c && x(b) <= v) { + if (x(b) == v) { + swap(a, b) + a += 1 + } + b += 1 + } + while (c >= b && x(c) >= v) { + if (x(c) == v) { + swap(c, d) + d -= 1 + } + c -= 1 + } + if (b > c) { + done = true + } else { + swap(b, c) + c -= 1 + b += 1 + } + } + + // Swap partition elements back to middle + val n = off + len + var s = Math.min(a-off, b-a) + vecswap(off, b-s, s) + s = Math.min(d-c, n-d-1) + vecswap(b, n-s, s) + + // Recursively sort non-partition-elements + s = b - a + if (s > 1) + sort2(off, s) + s = d - c + if (s > 1) + sort2(n-s, s) + } + } + sort2(off, len) } private def stableSort[K](a: Array[K], lo: Int, hi: Int, scratch: Array[K], f: (K,K) => Boolean) { |