Какая самая быстрая быстрая сортировка - таблица рейтингов для алгоритмов сортировки?

Я пытался оптимизировать свою быструю сортировку для повышения производительности. Для целочисленных элементов размером 4M (1 ‹< 22) (4 байта каждый) параллельный алгоритм быстрой сортировки занимает 0,5 (0,499703) секунды для сортировки в системе, которая может поддерживать 72 параллельных потока (72 ядра). Мне интересно узнать об эффективных способах дальнейшей оптимизации моей параллельной быстрой сортировки. Кроме того, вас интересует сравнение с другими алгоритмами сортировки, есть ли таблица рейтингов для всех алгоритмов сортировки с учетом определенной рабочей нагрузки?


sorting mergesort quicksort heapsort bucket-sort
person user1147800    schedule 16.04.2012    source источник
comment
Все дело в Big Oh и априорном знании набора ключей   -  person Mitch Wheat    schedule 16.04.2012
comment
Все было намного проще, когда все сортировки выполнялись в одном потоке. Теперь, когда разработчики загружают свои многоядерные процессоры частями работы, оптимизация алгоритма и его метаданных становится в значительной степени зависимой от архитектуры - размеры кеша и т. Д. Я еще не видел много работы по этому поводу или каких-либо таблиц / графиков / диаграмм. / алгоритмы, которые могут предложить лучший алгоритм сортировки и метаданные в различных системах.   -  person Martin James    schedule 16.04.2012
comment
Я подал в суд на набор случайных ключей, сгенерированный rand (). В самом деле, Big (O) важен, также как и параллелизм. Некоторые алгоритмы вряд ли будут эффективно распараллеливать. Некоторые другие, например, сглаженная сортировка, обладают лучшими свойствами большого O, но их трудно реализовать.   -  person user1147800    schedule 16.04.2012

Ответы (1)


arrow_upward
0
arrow_downward

Насколько мне известно, канонической таблицы лидеров для алгоритмов сортировки не существует. Производительность алгоритма сортировки зависит от множества различных факторов - получаемого вами распределения входных данных, размера входных данных, выбора языка программирования, типа и настроек используемого компилятора, количества ядер, температуры окружающей среды в помещении. комнату, операционную систему и т. д.

Что касается вашего другого вопроса - как оптимизировать быструю сортировку - не видя вашего кода, трудно сказать наверняка. Вот список распространенных оптимизаций быстрой сортировки, которые вы можете попробовать.

  1. Переключение на более быструю сортировку для небольших входных данных: сортировка вставкой выполняется за квадратичное время, но для небольших входных данных она может быть намного, намного быстрее, чем быстрая сортировка. Реализации быстрой сортировки нередко переключаются на сортировку вставкой, когда количество элементов для сортировки падает ниже определенного порога, что может значительно сократить время выполнения.

  2. Добавляем самоанализ. Introsort - это быстрый вариант быстрой сортировки, который отслеживает глубину рекурсии и переключается на heapsort, когда кажется, что алгоритм вырождается. Это гарантирует, что время выполнения будет O (n log n) и потребует лишь небольших затрат, если этот случай не сработает.

  3. Использование лучшего алгоритма разбиения. Dual-pivot quicksort недавно появился на сцене как альтернатива традиционным алгоритмам разделения. У него лучшая производительность на многих входах. Кроме того, рассмотрите возможность использования схемы разделения, которая изящно обрабатывает повторяющиеся элементы, если вы ожидаете, что вы получите входные данные с большим количеством дубликатов.

  4. Внедрите устранение обратного вызова. Многие реализации быстрой сортировки запускают два рекурсивных вызова для двух подмассивов, которые необходимо отсортировать, но на самом деле в этом нет необходимости. Вы можете запустить один рекурсивный вызов, а затем обработать второй вызов как хвостовой вызов, перезаписав параметры исходного вызова и поместив все это в цикл while.

person templatetypedef    schedule 26.08.2015