V sredo, 19. marca 2014 ob 13:15 bo v P3 potekal Seminar FRI z naslovom Multi-Pivot Quicksort: Theory and Experiments. Predaval bo Alejandro López-Ortiz iz Univerze v Waterlooju, Kanada.
Povezava na prosojnice in video posnetek.
Povzetek predavanj
Recently Vladimir Yaroslavskiy proposed a dual pivot quicksort algorithm that, contrary to prior theory and intuition, outperforms standard quicksort by a a significant margin under the Java JVM. More recently, this algorithm has been analysed in terms of comparisons and swaps by Wild and Nebel but fail to resolve the disagreement between theory and practice. We provide strong theoretical and practical evidence that cache behavior is causing most of the performance differences in these algorithms.
Lastly, we propose 3-pivot variant showing a 7-8% performance improvement over the previously best known quicksort algorithms.
Vabljeni!
