highly professional scums

dual-pivot quicksort

September 11, 2009, 7:44 pm

Все истинно гениальное очень просто.

Не прошло и 50 лет.

Category: Uncategorized | Comment (RSS) | Trackback

kayru

Идея ведь совсем на поверхности была.
Почему раньше про это никто не подумал? =\
look4awhile

интересно, а 3 и более pivot-а кто-нибудь уже попробовал?
какой-нибудь N-pivot? адаптивно N от размера, скажем?
kayru

2 look4awhile: По-моему, дополнительные операции сравнения перевесят сохраненные операции обмена.
CreatorCray

Сбацал бы кто performance тест на C++ со сравнением хотяб с std::sort
kayru

2CreatorCray: приведенный в пдфе код практически без изменений компилируется как с++
kayru

http://www.everfall.com/paste/id.php?5srxcy7g5hcb

std::sort: 252436
dual-pivot: 185687
ratio: 0.735581

vs2008, intel c2d e6850

В среднем прирост колебется в пределах 20-25%
CreatorCray

2kayru: блин, точно… :)

В общем получается что на DWORDах новый qsort делает старый в раза 1.5-2
Но с ростом размера сортируемых объектов новый начинает ацки сливать.
Pingback: highly professional scums » Blog Archive » Bubblesort, кеши и быстродействие()