Friday, June 17, 2011

Sleep Sort! With Actors! For No Reason!

The world's stupidest, racy sort algorithm ported to Scala actors for no good reason.

import scala.actors._
import Actor._

def sleepSort(xs : List[Int]) : List[Int] = {
   def sorter(aggregator : Actor, n : Int) = actor {
      reactWithin(n * 1000) {
        case TIMEOUT => {
           aggregator ! n
           exit
        }
      }
   }

   xs map (sorter(self, _)) foreach (_.start)

   val inputLength = xs.length

   def aggregate(result : List[Int], resultLength : Int) : List[Int] = 
     if (resultLength == inputLength) {
        result.reverse 
     } else receive {
        case n : Int => 
          aggregate(n :: result, resultLength + 1)
     }

   aggregate(List[Int](), 0)
}

Example usage:

scala> sleepSort(List(3,1,2))
res0: List[Int] = List(1, 2, 3)

Caveats: Can take a shockingly long time. Doesn't handle negative numbers. Doesn't handle actor failures. Races are possible. If you try to use this in real code then you will be fired and possibly shot.

2 comments:

Josh Suereth said...

WOW!  That's the best scaling implementation of sleep-sort I've seen.  It would only be better if you had a eBPM rule-based implementation. Then it would be fast *AND* smart.

James Iry said...

Oooh.