Что делает реализацию сортировки gcc std::list такой быстрой?

Question

У меня есть реализация связанного списка, и я экспериментирую с алгоритмами Mergesort и QuickSort.

Я не понимаю, почему операция сортировки в std:: list такая быстрая. Посмотрите на std:: list под linux, и он также представляется связанным списком, а не списком на основе массива.

Сортировка слиянием, которую я попробовал, почти идентична версии Дейва Гэмбла: Слияние Сортировка связанного списка

Кроме того, я решил попробовать простую быструю сортировку на основе этого кода: http://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml

Удивительно, но сортировка 10 миллионов случайных чисел с использованием std:: list и sort была примерно в 10 раз быстрее, чем любая из этих других.

А для тех, кто спрашивает, да, мне нужно использовать свой собственный класс списка для этого проекта.

Answer 1

Я взглянул на интересную реализацию GLibC для list:: sort ( исходный код), и он, кажется, не реализует традиционный алгоритм сортировки слиянием (по крайней мере, ни один из тех, что я когда-либо видел).

В основном то, что это делает:

1. Создает серию ведер (всего 64).
2. Удаляет первый элемент списка для сортировки и объединяет его с первым (i=0й) ведро.
3. Если до слияния iэто не пустое ведро, слить iй ведро с i+1й ведро
4. Повторите шаг 3, пока мы не слиться с пустым ведром.
5. Повторите шаги 2 и 3, пока список для сортировки не станет пустым.
6. Объедините все оставшиеся непустые сегменты, начиная с самого маленького до самого большого.

Небольшое примечание: слияние ведра X с ведром Y удалит все элементы из ведра X и добавить их в ведро Y сохраняя все отсортировано. Также обратите внимание, что количество элементов в корзине либо 0 или же 2^i,

Теперь, почему это быстрее, чем традиционная сортировка слиянием? Ну, я не могу сказать наверняка, но вот несколько вещей, которые приходят на ум:

• Он никогда не пересекает список, чтобы найти середину, что также делает алгоритм более дружественным к кешу.
• Поскольку более ранние сегменты малы и используются чаще, merge очищать кэш реже.
• Компилятор может оптимизировать эту реализацию лучше. Нужно будет сравнить сгенерированную сборку, чтобы быть уверенным в этом.

Я почти уверен, что люди, которые реализовали этот алгоритм, тщательно его протестировали, поэтому, если вы хотите получить точный ответ, вам, вероятно, придется спросить его в списке рассылки GCC.