fork download
copy 
  1. import scala.{ specialized => spec }
  2. import Ord._
  3. import scala.util.Random
  4. import java.util.Arrays
  5. object Main {
  6.  
  7.   def main(args: Array[String]): Unit = {
  8.     println(SortBench.test_classes(
  9.       classOf[SimpleSort[Int]]))
  10.   }
  11.  
  12. }
  13.  
  14. object SortBench {
  15.   val warm_runs = 2000
  16.   val warm_length = 16
  17.   val runs = 20
  18.   val max_length = 200
  19.  
  20.   def warmup(s: SortImpl[Int], count: Int) {
  21.     if (count > 0) {
  22.       s.sortInPlace(Array.fill(max_length)(Random.nextInt))(Ord.ordInt)
  23.       warmup(s, count - 1)
  24.     }
  25.   }
  26.  
  27.   def test(s: SortImpl[Int])(length: Int) = {
  28.     def testRun() = {
  29.       val src = Array.fill(length)(Random.nextInt)
  30.       val src2 = Arrays.copyOf(src, src.length)
  31.       val timeStart = System.nanoTime()
  32.       s.sortInPlace(src)(Ord.ordInt)
  33.       val timeEnd = System.nanoTime()
  34.       val res2 = src2.sortBy(identity)
  35.       assert(Arrays.equals(res2, src))
  36.       timeEnd - timeStart
  37.     }
  38.     var res = 0L
  39.     var count = runs
  40.     while (count > 0) {
  41.       res += testRun()
  42.       count -= 1
  43.     }
  44.     s"Class ${class_name(s.getClass()).padTo(20, ' ')} | length ${length.toString.padTo(8, ' ')} | time ${res / 1000000.0 / runs}ms"
  45.   }
  46.   def test_different_lengths(st: Class[_ <: SortImpl[Int]]) = {
  47.     val s = st.newInstance()
  48.     warmup(s, warm_runs)
  49.     Iterator.iterate(64)(_ * 2).takeWhile(_ <= max_length).map(test(s)).mkString("\n")
  50.   }
  51.   def test_classes(xs: Class[_ <: SortImpl[Int]]*) = {
  52.     xs.map(test_different_lengths).mkString("\n==============\n")
  53.   }
  54.  
  55.   def class_name(x: Class[_]) = {
  56.     x.getName().reverse.takeWhile(_ != '.').reverse
  57.   }
  58. }
  59.  
  60. trait Ord[@spec T] {
  61.   def lt(a: T, b: T): Boolean
  62. }
  63. object Ord {
  64.   implicit object ordInt extends Ord[Int] {
  65.     def lt(a: Int, b: Int) = a < b
  66.   }
  67. }
  68. object OrdRev {
  69.   implicit object ordInt extends Ord[Int] {
  70.     def lt(a: Int, b: Int) = a > b
  71.   }
  72. }
  73.  
  74. trait SortImpl[@spec T] {
  75.   def sortInPlace(x: Array[T])(implicit ord: Ord[T]): Unit
  76.   @inline def swap(x: Array[T], i1: Int, i2: Int) = {
  77.     val tmp = x(i1)
  78.     x(i1) = x(i2)
  79.     x(i2) = tmp
  80.   }
  81. }
  82.  
  83. class SimpleSort[@spec T] extends SortImpl[T] {
  84.   def sortInPlace(x: Array[T])(implicit ord: Ord[T]) = {
  85.     var i1 = 0
  86.     while (i1 < x.length) {
  87.       var i2 = i1 + 1
  88.       while (i2 < x.length) {
  89.         if (ord.lt(x(i2), x(i1))) {
  90.           swap(x, i1, i2)
  91.         }
  92.         i2 += 1
  93.       }
  94.       i1 += 1
  95.     }
  96.   }
  97. }
Success #stdin #stdout 4.45s 382144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Class SimpleSort           | length 64       | time 0.3906958ms
Class SimpleSort           | length 128      | time 0.9938904000000001ms
https://ideone.com/IYTzkp
language:
Scala (scala 2.12.8)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!