Сортировка небольшого количества элементов

Question

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

До скольких элементов можно ожидать выгоды от кодирования до inline void sort_n(int *list)?4?5?6?

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

Answer 1

Вы профиль ваше заявление, и это оказалось узким местом? Или вы пытаетесь переоптимизировать?

Bubblesort тоже может работать очень хорошо. В частности, когда ваши данные уже отсортированы, это на самом деле оптимально и превзойдет любое слияние учебников или сортировку кучи. Если вы не дадите полных ограничений (стоимость замены элементов, требования к стабильности, на месте или нет ...), никто не сможет ответить на этот вопрос полностью.

В любом случае, для четырех элементов довольно очевидно, как реализовать эффективную сортировку слиянием в строке.

Для нечетных (не степенных 2) размеров я считаю, что сортировка с обратной вставкой является обычной оптимизацией. Посмотрите на реализацию сортировки Javas. Я считаю, что он уже имеет такую ​​небольшую оптимизацию массива. Вы проверяли, что процедура сортировки, которую вы бы вызвали, еще не выполняет такого рода оптимизации?

Answer 2

Посмотрите на сортировку сетей.

Несколько ссылок:
http://en.wikipedia.org/wiki/Sorting_network
http://www.cs.uky.edu/~lewis/essays/algorithms/sortnets/sort-net.html
Самый быстрый вид массива фиксированной длины 6 int массив

Answer 3

Всем ответам на вопросы по оптимизации должно предшествовать предупреждение о том, что вы должны профилировать и оптимизировать только узкие места, поэтому: обязательно сделайте это.

В духе C / C ++ я теперь сделаю Доверяйте, чтобы вы сделали это и ответили на вопрос, который вы задали.

Вы определяете ответ на свой вопрос с помощью итеративного профилирования.lib sort.Используйте этот шаблон всякий раз, когда это уместно в вашем коде.Затем напишите шаблон специализации для наименьшего N случая, для которого у вас еще нет специализации.После написания этой специализации, профилируйте свою программу и посмотрите, добились ли вы значительного прироста производительности.Если вы получаете прирост производительности, который вы считаете значительным, повторите.Как только вы напишите специализацию и не получите от нее много, остановитесь.

Answer 4

Для любого разумного количества элементов вы всегда получите выигрыш в производительности от явного кодирования сравнений. Однако сортировка такого количества элементов занимает так мало времени, что в любом случае не имеет значения, какой метод вы используете.

Пороговое значение, при котором вы не получите никакого выигрыша в производительности, - это когда вы получаете столько кода, что он больше не помещается в кэш ЦП, поэтому пороговое значение будет отличаться в зависимости от того, на каком процессоре вы его используете. .

Вам также следует подумать, как бы вы протестировали такой код. Чем больше у вас кода, тем сложнее будет убедиться, что он не содержит ошибок.

Answer 5

Сортировка вставок и пузырьковая сортировка обычно используются для небольших данных.

Я полагаю, что сортировка вставок предпочтительна, ссылаясь на эти 2 текста Википедии:

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

И

Пузырьковая сортировка также плохо взаимодействует с современным аппаратным обеспечением ЦП. Для этого требуется как минимум вдвое больше записей, чем для сортировки вставкой, вдвое больше пропусков кэша и асимптотически больше ошибочных предсказаний ветвлений. Эксперименты по сортировке строк Astrachan в Java показывают, что сортировка пузырьков примерно в 5 раз медленнее, чем сортировка вставкой, и на 40% медленнее сортировки выделения.

Как всегда, вы должны указывать профиль, если вы действительно обеспокоены скоростью.

Answer 6

Сначала вам потребуется выполнить некоторое профилирование своего приложения, чтобы определить, стоит ли выполнять эту оптимизацию вашего времени.Я подозреваю, что это не будет.Функции стандартной библиотеки (или повышения) почти наверняка будут лучшим выбором для сортировки.

Answer 7

Мне сказали, что стандартные сортировки библиотек оптимизировали случаи для небольших n - я никогда не пытался это проверить.