Flashsort in Ruby

Es gibt auf github eine einfache Implementierung von Flashsort in Ruby, nachdem hier auf github schon eine Implementierung in C zu finden ist. Die C-Implementierung ist typischerweise schneller als die libc-Funktion qsort, aber letztlich hängt das von den Daten ab und davon, wie gut die metric-Funktion ist, die man zusätzlich zur Vergleichsfunktion bei Flashsort liefern muss. Man kann sich diese metric-Funktion als eine Art monotone Hashfunktion vorstellen, also gilt

    \[\bigwedge_{a,b: a\le b} m(a) \le m(b) \]

Diese zusätzlich benötigte Funktion oder Methode ist nicht wirklich vorhanden, außer bei numerischen Werten, was den Einsatz von Flashsort etwas erschwert. Entscheidend für eine gute Performance ist eine gute metric-Funktion, allerdings sind bei typischen Text-Dateien schon ziemlich triviale Implementierungen ganz brauchbar.

In diesem Blogbeitrag sind weitere Sortieralgorithmen für Ruby gezeigt.

Share Button

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.


*