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