BitSorting Алгоритм со сложностью О(n)

image

Предыстория


В свободное от работы время решил поразмыслить, а нельзя ли создать алгоритм соритировки который имел бы сложность O(n) не занимал бы много дополнительной памяти и мог бы быть легко распараллелен. И добился некоторого результата.

Представим, что у нас есть следующий набор чисел:
  • 123
  • 12345
  • 22345
  • 12345678
  • 1

Как мы, будучи людьми будем сортировать этот массив данных? Правильно, будем выбирать самое, визуально длинное, число.
А если длина одинаковая, то будем сравнивать цифры в одном разряде. Я подумал, что можно точно также заставить работать компьютер.

Алгоритм


Итак, имеем на входе массив чисел размером N:
int[] array = new int[n]

Далее, каждый элемент массива представляем в двоичном виде и сохраняем в новом списке:
bool[][] bitMatrix = new bool[n][]; //битовая матрица нашего массива
for (int i = 0; i < array.Length; i++)
{
	BitArray bitArray = new BitArray (new int[1]{ array [i] });
	bool[] bits = new bool[bitArray.Length];
	bitArray.CopyTo (bits, 0);
	Array.Reverse (bits);
	bitMatrix [i] = bits;
}

Мы получили следующую матрицу:
image

Затем следует самая интересная часть: рекурсивная сортировка.
Для начала, давайте посмотрим на то, как бы мы сортировали эту битовую матрицу:
  1. Смотрим на первую колонку
  2. Выбираем все элементы где первый бит равен 1 в один список
  3. Выбираем все элементы где первый бит равен 0 во второй список
  4. Повторяем действия 2 и 3 для первого и второго списков, но уже для колонки номер два

image

Код будет выглядеть следующим образом:
private void SortAlgorithm(bool[][] bitMatrix, int columnNumber)
{
	List<bool[]> ones = new List<bool[]> ();
	List<bool[]> zeros = new List<bool[]> ();

	for (int i = 0; i < bitMatrix.Length; i++)
	{
		if (bitMatrix[i][columnNumber])
			ones.Add(bitMatrix[i]);
		else
			zeros.Add(bitMatrix[i]);
	}

	columnNumber++;

	if (columnNumber == MAX_COLUMN_COUNT)//MAX_COLUMN_COUNT = sizeof(int)*8
	{
		sortedBitMatrix.AddRange(ones);
		sortedBitMatrix.AddRange(zeros);
		return;
	}

	if (ones.Count != 0)
		SortAlgorithm (ones.ToArray(), columnNumber);
	if (zeros.Count != 0)
		SortAlgorithm (zeros.ToArray(), columnNumber);
}

sortedBitMatrix используется для хранения отсортированной битовой матрицы.
Для преобразования битовой матрицы обратно в массив воспользуемся следующим методом:
private int[] ConvertBitMatrixToArray(List<bool[]> bitMatrix)
{
	int[] resultArray = new int[bitMatrix.Count];
	int count = 0;
	for (int i = 0; i < bitMatrix.Count; i++)
	{
		bool[] bits = bitMatrix [i];
		Array.Reverse(bits);
		BitArray bitArray = new BitArray(bits);
		int[] tmpArray = new int[1];
		bitArray.CopyTo(tmpArray, 0);
		resultArray [count] = tmpArray [0];
		count++;
	}
	return resultArray;
}

Результатом метода будет отсортированный массив.

А как же распараллеливание?


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

Сложность


Для сортировки заданного массива нам нужны следующие итерации:
  1. Создание битовой матрицы: n
  2. Поиск нулей и единиц: 32n
  3. Преобразование отсортированной битовой матрицы: n


Итого: 34n, что является O(n)

Интересно Ваше мнение.
Спасибо за внимание.

P.S. github.com/koljaka/BitSorting
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 33

    +29
    Вы открыли для себя Radix Sort — en.wikipedia.org/wiki/Radix_sort
      +1
      После первого подзаголовка тоже сразу её вспомнил. Неспроста подробный обзор существующих методов — обязательная часть описания любых работ как-либо претендующих на новизну)
        0
        Ну то понятно, вариация поразрядной сортировки по старшим цифрам. Оригинальной находкой является перевод числа в двоичный вид и уже затем обработка разрядов.

        Из очевидных минусов. Обычному msd radixsort этот метод в принципе проигрывает и по времени (хотя, формально и там и там O(n)) и по памяти. У поразрядки временная сложность k * n, где k — максимальное количество разрядов (причём речь о 10-чных числах). При переводе в биты количество разрядов намного увеличивается, значит и работать будет дольше. По памяти тоже всё хуже, в поразрядке хранить матрицу для всех чисел не требуется.

        Из возможных плюсов. Обработка матрицы из нулей и единиц предоставляет те возможности для распараллеливания, которых нет у классической поразрядной сортировки. Так что квантовая версия BitSortiong, возможно, представляет практический интерес.
          +1
          Оригинальной находкой является перевод числа в двоичный вид и уже затем обработка разрядов.
          Да обычный вариант binary radix sort. В общем-то алгоритму всё равно что из себя представлют разряды, и даже являются ли они позиционной нумерацией в числах (потому можно, например, строки сортировать и прочие сложные штуки).
        +7
        O(N*k), k — число бит в типе данных
          0
          причем k>log(N). Полагаю, что сортировки с временем O(N) нереализуемы, O(N*log(N)) — максимум чего можно добиться, и это как-то можно вывести в рамках теории информации.
            +1
            Неверно. Сортировка подсчётом — типичный пример сортировки с линейным временем работы. Предполагается, что все данные — числа от 1 до X (где X=O(n)).

            Однако если элементы можно лишь сравнивать между собой и ничего больше, то требуется хотя бы O(N*log(N)) сравнений, чтобы выяснить, к какой из N! перестановок элементов относится изначальная и отсортировать элементы соответственно.
              0
              >> Предполагается, что все данные — числа от 1 до X (где X=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).
                        –1
                        Откуда 16 гигабайт?!!! Не пугайте меня так.
                          0
                          В чем проблема? 32/8 * 2^32B = 16GB.
                            0
                            А, вы имели в виду массив Int32. Тогда извиняюсь, все верно. Я почему-то подумал о байтах.
                          0
                          Обычно используется стандартная машина, которая может выполнять вычисления с числами величины не больше 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
                              w часто не участвует в сложности алгоритма. В частности, сложность сортировки подсчетом w не содержит. Зато ее сложность содержит параметр max_input. Если он оказывается O(N), то и вся сложность станет O(N). Если max_input равняется 2^w, то сложность будет O(2^w).
                    0
                    Смотря что сортировать. Целые числа можно сортировать быстрее. При этом, разумеется, используются не только сравнения, но и арифметические операции над ними. На практике смысла в этом более быстром алгоритме нет.
                    0
                    Думал, что k можно уменьшать путем распараллеливания. Вернее уменьшать N, что повлечет за собой изменение k.
                      0
                      Без наезда, действительно интересно.
                      Вы можете сформулировать, что означает, что алгоритм имеет сложность O(f(x)) для данной f(x)?
                        –1
                        Могу попробовать: O(f(x)) означает то, как изменится значение f(x) при увеличении размера х на 1 бит.
                          0
                          Это значит, что если мы будем считать, что время выполнения каждой элементарной операции процессором константно (не обязательно одинаково для разных операций, но всегда не больше какой-то константы), а время выполнения программы в секундах в зависимости от размера входных данных N (например, размера массива) обозначим T(N), то будет выполнено математическое утверждение T(N) = O(f(N)), которое означает, что lim (N->+inf) T(N)/f(N) существует, конечен и не равен 0.
                            –7
                            Советую вам забыть эти вузовские определения.
                            Big O абсолютна никак не связана в математике с временем и процессорами.
                              0
                              Всегда рад послушать опытного человека. Чем же оно отличается?
                                0
                                Пока что я не знаю ни одного примера, который противоречил бы моему определению, данному выше. И поверьте, я знаю немало стандартных алгоритмов
                                  +2
                                  Как минимум 0=O(1) (предел может быть равен 0) и sin(x)=O(1) (предел может не существовать вовсе) при x->+inf.
                        0
                        Ну, а во вторых — можно существенно проще, если формализовать термин «много дополнительной памяти». Если мы например сортируем безнаковые целы, и массив размером с максимальное значение элемента для нас не является «большим» количеством дополнительной памяти. То сортировка подсчетом (http://en.wikipedia.org/wiki/Counting_sort) параллелится лучше некуда. А реализация ее тоже проще некуда.
                          –1
                          Возможно, я что-то не понял, но вроде как первый проход (по старшей цифре) не распараллелится, хотя он занимает половину времени работы программы. Так что для меня это не «хорошо параллелящийся алгоритм»
                            0
                            Автор, еще для Вас гениальная идея: на каждом проходе делить не на 2 части, а на 65536 в зависимости от значения старших 16 бит — тогда для int32 потребуется всего два прохода.
                            И хотелось бы заметить, что таким образом можно сортировать не только целые числа, но и вещественные, и строки
                              0
                              Вы отталкиваетесь от мысли, что числа записываются 32-я битами. Что совсем не так, бывают числа и куда большие, которые тоже надо сортировать.
                              Как выше вам уже сказали, вы «придумали» Radix Sort. Могу вам ещё посоветавать почитать про Bucket Sort, у него тоже O(n)
                              А вообще, уже давно доказано, что лучше чем O(nlogn) [точнее O(log(n!)), что почти тоже самое] достич невозможно для общего случая сортировки.
                                0
                                Могу вам ещё посоветавать почитать про Bucket Sort, у него тоже O(n)
                                Ну, они довольно похожи потому что. Фактически Radix Sort это Bucket Sort по каждому разряду, нет?

                              Only users with full accounts can post comments. Log in, please.