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
Seguici
ossblog è un supplemento alla testata Blogo.it registrata presso il Tribunale di Milano n. 487/06, P. IVA 04699900967. Contatti, Chi siamo, Condizioni di utilizzo, Privacy.
© 2004-2012 Blogo.it, alcuni diritti riservati sotto licenza Creative Commons.
Per informazioni pubblicitarie e progetti speciali su Ossblog.it contattare la concessionaria esclusiva Populis Engage.
barra
02 ott 2011 - 20:56 - #1Ci fossero più sviluppatori come il buon Kolivas….
hellview81
02 ott 2011 - 22:31 - #2grande
qqwer
03 ott 2011 - 10:10 - #3pensavo non ci fosse piu’ nulla da dire in fatto di sort e invece…. bravo Kolivas!!!!
brunoliegibastonliegi
03 ott 2011 - 12:20 - #4BREVETTIAMOLO!!!!!!!!!!!!
anaoaea
03 ott 2011 - 13:27 - #5Esistono svariati tipi di sort specifici e questo è fra quelli, nulla esclude che siano applicabili comunque a dati statisticamente casuali.
Sta al programmatore capire quale algoritmo specifico di sort utilizzare se possibile, altrimenti utilizzare il più rapido, quello che usa meno risorse,ecc.
six110
03 ott 2011 - 15:36 - #6Alla faccia dell’anestesista “appassionato di informatica”…
nowhereman
03 ott 2011 - 16:26 - #7ha rilasciato un algoritmo di sorting sotto GPLv3?? wtf??
Kim Allamandola
03 ott 2011 - 18:08 - #8@brunoliegibastonliegi #4 && nowhereman #7
Io sarei più che favorevole a brevettare ogni singola riga di codice open col
vincolo del brevetto al pubblico dominio (ovvero puoi usare gratis il brevetto
solo a patto che l’uso che ne fai ricada a sua volta nel pubblico dominio),
peccato costi troppo.
Se si potesse fare Apple, Microsoft, Oracle ecc avrebbero finito non solo di
monopolizzare il mercato ma anche di esistere non avendo nessuna soluzione
del tutto proprietaria usabile!
0xdeadbeef
03 ott 2011 - 19:35 - #9Esercizio assai apprezzabile, ottimizza il caso peggiore per piccoli insiemi di dati, parzialmente ordinati o con ripetizioni utilizzando arbitrariamente 3 bucket.
Ha quindi rilasciato un’implementazione sotto GPL3, ma da qui a dire che se avesse potuto lo avrebbe brevettato ce ne passa.
barra
03 ott 2011 - 20:45 - #10@Kim
Da non esperto in materia ipotizzo: Il buon Kolivas ha sviluppato questo bel codice, non lo brevetta. Arriva MS che “copia” il codice e lo brevetta. Ok c’è la prior art ma come dicevi tu nell’opensource non ci sono i soldi per “combattere” ad armi pari con MS, che si fa?
Kim Allamandola
03 ott 2011 - 22:18 - #11@barra #10
Con la prior art sei a posto: il tuo codice originale è opensource quindi sia
l’algoritmo che la paternità dello stesso è esplicita; il costo nel momento in
cui la Microsoft ti citasse per violazione di brevetto sarebbe del tutto
sostenibile dalla maggior parte dei singoli, dalla FSF, dalla community ecc.
anzi porterebbe un po’ di soldi in cassa coi danni che seguono.
Il costo non è la difesa attiva come nel caso sopracitato, il costo è a priori
il brevetto per *impedire* giocando al loro stesso gioco che possano sfruttare
il tuo lavoro e nel caso lo facciano il costo è il processo dove tu denunci la
Microsoft o chi per essa e devi provare le tue accuse.
Dimostrare la prior art su codice Opensource pubblico e pubblicato è immediato,
dimostrare che un programma closed ti copia in violazione della tua licenza
non lo è, almeno non lo è per piccole cose, se non ha copiato tanto ma solo
piccole percentuali per programma complessivo.
Il mio discorso è dato che questo mercato non può più vivere, persino aziende
come Google chiedono a gran voce la fine dei brevetti software, che ricordo
per l’ennesima volta IN EUROPA NON CI SONO, più spinte si danno per finire di
levarlo dai piedi meno problemi, costi ecc ci sono!
Ps nell’Opensource ci sono capitali in ballo belli grossi eh, non sono solo cose di
programmatori hobbisti! Ci girano miliardi di dollari, aziende come Google, IBM,
HP sino a Netgear, TomTom ecc *dipendono* in larga parte da progetti open e
sono membri attivi della FSF ed altre organizzazioni con fondi finanziari, codice
e portafoglio di brevetti. Ovviamente non brevettano ciò che non gli interessa
né brevettano a nome di altri del codice!