Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 33
Вы открыли для себя Radix Sort — en.wikipedia.org/wiki/Radix_sort
После первого подзаголовка тоже сразу её вспомнил. Неспроста подробный обзор существующих методов — обязательная часть описания любых работ как-либо претендующих на новизну)
Ну то понятно, вариация поразрядной сортировки по старшим цифрам. Оригинальной находкой является перевод числа в двоичный вид и уже затем обработка разрядов.
Из очевидных минусов. Обычному msd radixsort этот метод в принципе проигрывает и по времени (хотя, формально и там и там O(n)) и по памяти. У поразрядки временная сложность k * n, где k — максимальное количество разрядов (причём речь о 10-чных числах). При переводе в биты количество разрядов намного увеличивается, значит и работать будет дольше. По памяти тоже всё хуже, в поразрядке хранить матрицу для всех чисел не требуется.
Из возможных плюсов. Обработка матрицы из нулей и единиц предоставляет те возможности для распараллеливания, которых нет у классической поразрядной сортировки. Так что квантовая версия BitSortiong, возможно, представляет практический интерес.
Из очевидных минусов. Обычному msd radixsort этот метод в принципе проигрывает и по времени (хотя, формально и там и там O(n)) и по памяти. У поразрядки временная сложность k * n, где k — максимальное количество разрядов (причём речь о 10-чных числах). При переводе в биты количество разрядов намного увеличивается, значит и работать будет дольше. По памяти тоже всё хуже, в поразрядке хранить матрицу для всех чисел не требуется.
Из возможных плюсов. Обработка матрицы из нулей и единиц предоставляет те возможности для распараллеливания, которых нет у классической поразрядной сортировки. Так что квантовая версия BitSortiong, возможно, представляет практический интерес.
Оригинальной находкой является перевод числа в двоичный вид и уже затем обработка разрядов.Да обычный вариант binary radix sort. В общем-то алгоритму всё равно что из себя представлют разряды, и даже являются ли они позиционной нумерацией в числах (потому можно, например, строки сортировать и прочие сложные штуки).
O(N*k), k — число бит в типе данных
причем k>log(N). Полагаю, что сортировки с временем O(N) нереализуемы, O(N*log(N)) — максимум чего можно добиться, и это как-то можно вывести в рамках теории информации.
Неверно. Сортировка подсчётом — типичный пример сортировки с линейным временем работы. Предполагается, что все данные — числа от 1 до X (где X=O(n)).
Однако если элементы можно лишь сравнивать между собой и ничего больше, то требуется хотя бы O(N*log(N)) сравнений, чтобы выяснить, к какой из N! перестановок элементов относится изначальная и отсортировать элементы соответственно.
Однако если элементы можно лишь сравнивать между собой и ничего больше, то требуется хотя бы O(N*log(N)) сравнений, чтобы выяснить, к какой из N! перестановок элементов относится изначальная и отсортировать элементы соответственно.
>> Предполагается, что все данные — числа от 1 до X (где X=O(n)).
И они должны быть целыми (ну или по крайней мере из конечного множества, модуль которого не больше чем O(n)).
И они должны быть целыми (ну или по крайней мере из конечного множества, модуль которого не больше чем O(n)).
На самом деле это заблуждение. Для неповторяющихся чисел (или набором чисел с процентом неповторяющихся, линейно зависящим от длинны последовательности, например 10% чисел разные) сортировка подсчетом дает O(N*Log(N)). Абстрагируясь от всего — у вас хотябы объем входных данных будет N*Log(N). Так что O(N), где N — количество чисел — это в каком-то роде софистика.
Не заблуждение, софистикой, по-моему, занялись вы. Это вопрос терминологии: какие операции считать выполняющимися за константное время. Если считать, что базовые операции с числами выполняются за константу, то сложность будет такая, как я указал. Если считать, что за константу выполняютя лишь операции с битами (или другими разрядами), а разрядов — O(logN), то сортировка подсчётом будет работать за O(NlogN) (т.е. за объём входа), а сортировки сравнениями — O(Nlog^2N), т.е. в logN раз дольше, так как на каждое сравнение требуется O(logN) операций.
И тут внезапно мы получаем ограничение на размер сортируемых чисел. Тогда можно чего уж там — принять за константу операцию сортировки, ограничить размер массиваа 16 гигабайтами (все различные числа Int32) и говорить что любой массив сортируется за константу. В общем же операции с числами не могут занимать константное время до тех пор пока разрзядность не ограничена сверху.
Да, конечно. Но смысла это не меняет — сортировка подсчётом работает за O(input), любая сортировка сравнениями в худшем случае — хотя бы в O(logN) раз дольше.
С тем что оно асимптотически быстрее никто и не спорит, изначальный посыл был ответом на:
Неверно. Сортировка подсчётом — типичный пример сортировки с линейным временем работы. Предполагается, что все данные — числа от 1 до X (где X=O(n)).И в такой формулировке просто противоречие, если X in O(n), тогда ну никак не выйдет общее время O(n).
Откуда 16 гигабайт?!!! Не пугайте меня так.
Обычно используется стандартная машина, которая может выполнять вычисления с числами величины не больше 2^w за O(1) и при этом все числа во входных данных так же ограничены числом 2^w (включая N), если не оговорено противное. При этом символ O берется при w и N стремящихся к бесконечности, поэтому нельзя сказать, что любая сортировка работает за O(1). Сортировка подсчетом в такой модели — это O(max(max_input, N)).
Я еще раз процитирую:
Неверно. Сортировка подсчётом — типичный пример сортировки с линейным временем работы. Предполагается, что все данные — числа от 1 до X (где X=O(n)).Опять же ваш комментарий точно так же противоречив:
При этом символ O берется при w и N стремящихся к бесконечностиЕсли мы берем асимптотику для w и N, тогда у нас по любому в ответе должно быть O(f(w, N)), и т.к. w явно не с нулевым коэффициентом, то O(N) опять же не подходит. Если у вас max_input = N*2^w — тогда оно и выходит N*lg(N) в худшем случае.
Смотря что сортировать. Целые числа можно сортировать быстрее. При этом, разумеется, используются не только сравнения, но и арифметические операции над ними. На практике смысла в этом более быстром алгоритме нет.
Думал, что k можно уменьшать путем распараллеливания. Вернее уменьшать N, что повлечет за собой изменение k.
Без наезда, действительно интересно.
Вы можете сформулировать, что означает, что алгоритм имеет сложность O(f(x)) для данной f(x)?
Вы можете сформулировать, что означает, что алгоритм имеет сложность O(f(x)) для данной f(x)?
Могу попробовать: O(f(x)) означает то, как изменится значение f(x) при увеличении размера х на 1 бит.
Это значит, что если мы будем считать, что время выполнения каждой элементарной операции процессором константно (не обязательно одинаково для разных операций, но всегда не больше какой-то константы), а время выполнения программы в секундах в зависимости от размера входных данных N (например, размера массива) обозначим T(N), то будет выполнено математическое утверждение T(N) = O(f(N)), которое означает, что lim (N->+inf) T(N)/f(N) существует, конечен и не равен 0.
Советую вам забыть эти вузовские определения.
Big O абсолютна никак не связана в математике с временем и процессорами.
Big O абсолютна никак не связана в математике с временем и процессорами.
Ну, а во вторых — можно существенно проще, если формализовать термин «много дополнительной памяти». Если мы например сортируем безнаковые целы, и массив размером с максимальное значение элемента для нас не является «большим» количеством дополнительной памяти. То сортировка подсчетом (http://en.wikipedia.org/wiki/Counting_sort) параллелится лучше некуда. А реализация ее тоже проще некуда.
Возможно, я что-то не понял, но вроде как первый проход (по старшей цифре) не распараллелится, хотя он занимает половину времени работы программы. Так что для меня это не «хорошо параллелящийся алгоритм»
Автор, еще для Вас гениальная идея: на каждом проходе делить не на 2 части, а на 65536 в зависимости от значения старших 16 бит — тогда для int32 потребуется всего два прохода.
И хотелось бы заметить, что таким образом можно сортировать не только целые числа, но и вещественные, и строки
И хотелось бы заметить, что таким образом можно сортировать не только целые числа, но и вещественные, и строки
Вы отталкиваетесь от мысли, что числа записываются 32-я битами. Что совсем не так, бывают числа и куда большие, которые тоже надо сортировать.
Как выше вам уже сказали, вы «придумали» Radix Sort. Могу вам ещё посоветавать почитать про Bucket Sort, у него тоже O(n)
А вообще, уже давно доказано, что лучше чем O(nlogn) [точнее O(log(n!)), что почти тоже самое] достич невозможно для общего случая сортировки.
Как выше вам уже сказали, вы «придумали» Radix Sort. Могу вам ещё посоветавать почитать про Bucket Sort, у него тоже O(n)
А вообще, уже давно доказано, что лучше чем O(nlogn) [точнее O(log(n!)), что почти тоже самое] достич невозможно для общего случая сортировки.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
BitSorting Алгоритм со сложностью О(n)