25.10.2013

Sleep++ [Sortieren im Schlaf]

Durch einen Eintrag bei Twitter bin ich über eine kurze Notiz zu "SleepSort" gestolpert. Dort wurde ein Blogeintrag empfohlen in dem eine kurzer Algorithmus zur Sortierung von Zahlen-Arrays vorgestellt wurde. Die Idee ist einfach und schnell erklärt.






Das Array wird von vorne bis hinten durchlaufen, für jede Zahl wird ein Prozess geforkt. Dieser wartet exakt die Zeitspanne, die durch die Zahl definiert wird und gibt diese danach aus. Als Bash-Skript total elegant:


Das muss doch auch mit Java gehen, oder nicht? Ja, es geht, zwar nicht so kurz und mit Sicherheit dadurch nicht ganz so elegant, aber es geht. Einstiegspunkt ist die Methode sort(int[] numbers) in der Klasse SleepSort.


In der Methode wird ein ExecutorService mit einem fixen Pool an Threads definiert. Für jede Zahl wird nun ein SortRunnable erzeugt, welches im Anschluss gestartet wird. Dieses sorgt in einer einfachen Implementierung dafür, dass eine bestimmte Zeit gewartet und im Anschluss das Ergebnis erweitert wird


Nachdem alle Threads gestartet sind und die Verarbeitung läuft, wird der ExecutorService für weitere Threads mittels shutdown() für weitere Threads geblockt und ein Timeout definiert. In diesem Fall ist das Timeout recht leicht zu berechnen, als Basis habe ich die Summe der Zahlen plus einen gewissen Puffer gewählt.


Zeit für einen kleinen Test, die Implementierung ist ja bereits fertig. Für den Test werden mehrere Arrays mit Zufallszahlen erstellt.

 

Diese werden nun in einzelnen Tests abgearbeitet, so dass eine grobe Betrachtung der Laufzeit vorgenommen werden kann.

Für 10 Zahlen:

 

Für 100 Zahlen:

 

Für 1000 Zahlen:

 

Schnell wird ersichtlich, dass in diesem Fall die Laufzeit der sehr einfachen Implementierung stark von der Größe der Zahlen abhängig ist. Sollten die Zahlen insgesamt sehr groß sein, so ist es zwingend notwendig das Intervall für die Wartezeit herab zu setzen. Auch die Grenze des Suchverfahrens ist mit der einfachen Implementierung schnell erreicht, mehr als 10000 Threads werden für die meisten Systeme Overkill sein und daher zum Absturz führen. Auch minimale Unterschiede in den Zahlenreihen können zu einer fehlerhaften Ausgabe führen, da durch das Verwalten der Vielzahl von Threads ein gewisser Overhead bei der Abarbeitung zu spüren ist.

Insgesamt also eher eine Spielerei (zumindest mit Java), aber eine gute Möglichkeit sich mit Threading auseinanderzusetzen. Für eine Übung im Rahmen einer Schulung sicherlich ein nettes Beispiel, für die Realität eher nicht.