Il noto kernel hacker, dopo i suoi lavori sul nuovo scheduler BFS e dopo i recenti rilasci sull’algoritmo di compressione per file di grandi dimensioni lrzip, ha sentito l’irrefrenabile bisogno di reinventare la ruota rilasciando con licenza GPLv3 una variante migliorata dell’algoritmo di ordinamento selection sort.
L’idea di fondo consiste nell’accostare strutture dati ausiliarie all’ordinamento per selezione suddividendo gli elementi in tre categorie, al fine di aumentare le prestazioni nello scenario peggiore o in caso di dati ripetuti. Tralasciando i dettagli implementativi, la curiosità intellettuale di Con Kolivas ha portato comunque dei frutti inaspettati in un confronto con l’ottimo quick sort.
I test sono stati effettuati considerando un insieme di 10000 elementi in differenti condizioni statistiche: cksort è risultato nettamente superiore in tutte le configurazioni, eccezion fatta per dati casuali dove l’algoritmo paga in maniera davvero pesante: 658 millisecondi contro 51770 millisecondi. In tutti gli altri set di dati, a mio parere, cksort è stata una rivelazione nonostante il mio scetticismo iniziale: per configurazioni meno casuali o addirittura interlacciate risulta essere dalle 10 alle 6 volte più veloce di quicksort. Davvero notevole per un semplice esperimento.
Non soddisfatto di questa divagazione, Con Kolivas ha già annunciato che prossimamente si concentrerà su un algoritmo di ordinamento di tipo O(n log n) ottimizzato per il calcolo parallelo.
Via | ck Hacking
Con Kolivas reinventa il selection sort é stato pubblicato su Ossblog.it alle 19:48 di domenica 02 ottobre 2011.