highly professional scums

8 Comments

1. kayru:

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

   12 September 2009, 4:11 pm

2. look4awhile:

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

   12 September 2009, 8:17 pm

3. kayru:

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

   12 September 2009, 8:44 pm

4. CreatorCray:

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

   16 September 2009, 9:03 am

5. kayru:

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

   16 September 2009, 11:54 pm

6. kayru:

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

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

   vs2008, intel c2d e6850

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

   17 September 2009, 2:54 am

7. CreatorCray:

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

   В общем получается что на DWORDах новый qsort делает старый в раза 1.5-2
   Но с ростом размера сортируемых объектов новый начинает ацки сливать.

   17 September 2009, 10:36 pm

8. highly professional scums » Blog Archive » Bubblesort, кеши и быстродействие:

   [...] Несколько интересных соображений, навеянных публикациями по dual-pivot quicksort. [...]

   2 October 2009, 6:38 am

Leave a comment

You must be logged in to post a comment.