Действительно ли qsort stdlib является рекурсивным?
Я считал это qsort просто универсальный вид, без обещаний о реализации. Я не знаю о том, как библиотеки варьируются от платформы до plaform, но предположения, что реализации Mac OS X и Linux широко подобны, qsort рекурсивные реализации и/или требуют большого количества стека?
У меня есть большой массив (сотни тысяч элементов), и я хочу отсортировать его, не унося мой стек к забвению. С другой стороны, какие-либо предложения для эквивалента для больших массивов?
9 ответов
Вот версия от BSD, авторское право Apple, предположительно используемая в OS X в то или иное время:
http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/ qsort.c
Он рекурсивен по вызовам, хотя верхняя граница глубины рекурсии, как объясняет Блинди, мала.
Вот версия из glibc, предположительно используемая в системах Linux в то или иное время:
http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c
Это не рекурсивный вызов. По той же причине, по которой ограничение на рекурсию вызовов невелико, он может использовать небольшой фиксированный объем стека для управления своей рекурсией цикла.
Можно мне потрудиться поискать последние версии? Нет; -)
Для нескольких сотен тысяч элементов массива даже реализация с рекурсивным вызовом не вызовет глубину более 20 уровней. По большому счету, это неглубоко, за исключением очень ограниченных встроенных устройств, у которых не будет достаточно памяти для того, чтобы у вас был массив такого размера, который можно было бы сортировать. Когда N ограничено выше, O (log N), очевидно, является константой , но более того, это обычно вполне управляемая константа. Обычно в 32 или 64 раза «меньше» означает «разумно».
Да, это рекурсивно. Нет, вероятно, он не будет использовать большое количество стека. Почему бы просто не попробовать? Рекурсия - это не какой-то жупел - это предпочтительное решение очень многих проблем.
При быстрой сортировке стек будет логарифмически увеличиваться. Вам понадобится много элементов, чтобы взорвать ваш стек.
Реализация qsort , которая может давать сбой на больших массивах, крайне неработоспособна. Если вы действительно беспокоитесь, я бы выбрал RTFS, но я подозреваю, что любая полуприличная реализация будет либо использовать алгоритм сортировки на месте, либо использовать malloc для временного пространства и вернуться к алгоритму на месте если malloc не работает.
Наихудшая пространственная сложность наивной реализации быстрой сортировки (которая все еще является популярным вариантом для qsort) составляет O (N). Если реализация модифицируется так, чтобы сначала сортировать меньшую заранее и оптимизацию хвостовой рекурсии или используется явный стек и итерация , то пространство для наихудшего случая может быть приведено вплоть до O (log N) (о чем уже писали большинство ответов). Таким образом, вы не взорвете свой стек, если реализация быстрой сортировки не нарушена и библиотека не была нарушена неправильными флагами компилятора. Но, например, большинство компиляторов, которые поддерживают устранение хвостовой рекурсии, не будут выполнять эту оптимизацию в неоптимизированных отладочных сборках. Библиотека, созданная с неправильными флагами (т.е. недостаточная оптимизация, например, во встроенном домене, где вы иногда создаете свою собственную отладочную libc), может тогда привести к сбою стека.
Для большинства разработчиков это никогда не будет проблемой (у них есть протестированные поставщиками библиотеки libc с пространственной сложностью O (log N)), но я бы сказал, что это хорошая идея, чтобы время от времени следить за потенциальными проблемами библиотеки. ко времени.
ОБНОВЛЕНИЕ: Вот пример того, что я имею в виду: ошибка в libc (начиная с 2000 г.), когда qsort начинал перебивать виртуальную память, потому что реализация qsort внутренне переключилась на сортировку слиянием, потому что там достаточно памяти для хранения временного массива.
http://sources.redhat.com/ml/libc-alpha/2000-03/msg00139.html
Знаете, рекурсивная часть очень глубока. За 64 уровня рекурсии (а это ~64*4=~256 байт стека всего) можно отсортировать массив размером ~2^64, т.е. массив такого размера, какой можно адресовать на 64-битном процессоре, что составляет 147573952589676412928 байт для 64-битных целых чисел. Вы даже не можете хранить его в памяти!
Беспокойтесь о вещах, которые имеют значение, имо.
Правильно реализованная qsort не требует более log2(N) уровней рекурсии (т.е. глубины стека), где N - наибольший размер массива на данной платформе. Обратите внимание, что это ограничение действует независимо от того, насколько хороша или плоха разбивка, т.е. это наихудший случай глубины рекурсии. Например, на 32-битной платформе глубина рекурсии никогда не превысит 32 в худшем возможном случае, учитывая разумную реализацию qsort.
Другими словами, если вас беспокоит именно использование стека, вам не о чем беспокоиться, если только вы не имеете дело с какой-то странной низкокачественной реализацией.
Я помню, что читал в этой книге: Программирование на C: A Modern Approach , что спецификация ANSI C не определяет, как реализовать qsort.
И в книге написано, что qsort на самом деле может быть другим видом сортировки, сортировкой слиянием, сортировкой вставкой и почему бы не пузырьковой сортировкой :P
Так что реализация qsort может быть не рекурсивной.
Я бы предположил, что большинство современных реализаций qsort на самом деле используют алгоритм Introsort. Разумно написанный Quicksort в любом случае не разнесет стек (он будет сортировать сначала меньший раздел, что ограничивает глубину стека логарифмическим ростом).
Introsort идет дальше - для ограничения сложности в худшем случае, если он видит, что Quicksort не работает хорошо (слишком много рекурсии, поэтому сложность может быть O(N2), он переключается на Heapsort, который гарантирует сложность O(N log2 N) и также ограничивает использование стека. Поэтому, даже если Quicksort, который он использует, написан небрежно, переход на Heapsort все равно ограничит использование стека.