Std :: sort проверяет, отсортирован ли вектор?

Question

Я считаю, что стандарт C ++ для std::sort не гарантирует производительность O (n) в уже отсортированном списке. Но все же, мне интересно, насколько вам известно, чтобы какие-либо реализации STL (GCC, MSVC и т. Д.) Выполняли проверку std::is_sorted перед выполнением алгоритма сортировки?

На вопрос по-другому, какую производительность можно ожидать (конечно, без гарантий) от запуска std::sort в отсортированном контейнере?

Примечание: я опубликовал некоторые тесты для GCC 4.5 с поддержкой C ++ 0x в моем блоге. Вот результаты:

Answer 1

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

Однако я видел сравнение производительности libstdc ++ при использовании в linux и против libc ++ новой библиотеки C ++, разработанной Apple / LLVM. Обе эти библиотеки очень эффективны для сортированных или обратно отсортированных данных (намного быстрее, чем в случайном списке), причем новая библиотека значительно быстрее старой и распознает гораздо больше шаблонов.

Чтобы быть уверенным, вам следует подумать о проведении собственных тестов.

Answer 2

Нет . Кроме того, нелогично, чтобы is_sorted() вызывался для любой реализации STL. Поскольку, is_sorted() доступен уже как самостоятельный. И многие пользователи могут не захотеть тратить циклы выполнения без необходимости на вызов этой функции, когда они уже знают, что их контейнер не отсортирован.

STL также должен следовать философии C ++: « оплата за использование ».

Answer 3

Вау!Были ли у вас оптимизации на всем пути?

результаты вашего кода на моей платформе (обратите внимание на значения по вертикальной оси).

Answer 4

Стандартные санкции только std::sort реализации со сложностью O (n log n):

Сложность: Приблизительно N log N (где N == last - first) сравнений в среднем.

См. Раздел 25.3.1.1 Сортировка [lib.sort] (ИСО / МЭК 14882: 2003 (E)).

Таким образом, набор разрешенных функций сортировки ограничен, и вы правы в том, что он не гарантирует линейной сложности.

Идеальным поведением для сортировки является O (n), но в среднем это невозможно.

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

Answer 5

Я предлагаю вам прочитать это сравнение алгоритмов сортировки , оно очень хорошо сделано и информативно, оно сравнивает ряд алгоритмов сортировки друг с другом и с реализацией GCC std :: sort.В диаграммах по данной ссылке вы заметите, что производительность std :: sort для «почти отсортированных» и «почти обратных» линейна по количеству сортируемых элементов, то есть O (n).Таким образом, нет гарантии, но вы можете легко ожидать, что почти отсортированный список будет отсортирован почти за линейное время.Но, конечно, он не выполняет проверку is_sorted, и даже если он будет сортировать отсортированный массив за линейное время, он не будет таким же быстрым, как проверка is_sorted и вообще пропускает сортировку.Вы сами решаете, лучше ли проверить перед сортировкой или нет.

Answer 6

И почему любая реализация делает эту проверку?Что это получит?- Ничего среднего.Хорошее правило проектирования - не загромождать реализацию оптимизациями для угловых случаев, которые не имеют значения в среднем.Этот пример похож на проверку на самостоятельное назначение.Простой ответ: не делай этого.

Answer 7

Нет гарантии, что это проверит. Некоторые реализации будут делать это, другие, вероятно, не будут.

Однако, если вы подозреваете, что ваш ввод может быть уже отсортирован (или почти отсортирован), std::stable_sort может быть лучшим вариантом.