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