Поразрядная сортировка LSD (Radix Sort)



    В последнее время публикуется множество статей посвященных различным алгоритмам сортировки и их сравнению, решил внести и свои пять копеек.

    Хочу рассказать про свой излюбленный алгоритм для поразрядной сортировки LSD (least significant digit — сначала младший разряд) с подсчётом (Radix Sort). Классический алгоритм был несколько переосмыслен автором в сторону некоторых оптимизаций в пользу ускорения и простоты.

    Итак, предложенная сортировка является устойчивой. Сортировать будем целые 32 битные числа. Для работы потребуется ~(n+4Кбайт) дополнительной памяти, что несколько расточительно, но позволяет добиться некоторого увеличения производительности.

    В данной разновидности LSD не используются сравнения и обмены, алгоритм полностью линеен. Вычислительная сложность O(N).

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

    Сортировка происходит по месту, для экономии памяти.

    //==================================================
    // RADIX сортировка (авторская версия by rebuilder)
    // Устойчивый алгоритм сортировки, полностью линеен.
    // Вычислительная сложность О(n), доп память ~(n+4k)
    //==================================================
    procedure RSort(var m: array of Longword);
    //-------------------------------------------------- 
       procedure Sort_step(var source, dest, offset: array of Longword; const num: Byte);
       var i,temp : Longword;
           k : Byte;
       begin
         for i := High(source) downto 0 do
         begin
           temp := source[i];
           k := temp SHR num;
           dec(offset[k]);
           dest[offset[k]] := temp;
         end;
       end;
    //-------------------------------------------------- 
    // Объявляем массив корзин первым, для выравнивания на стеке
    var s : array[0..3] of array[0..255] of Longword;  
        i,k : longword;
        // Смещение байт внутри переменной k
        offset : array[0..3] of byte absolute k;       
        m_temp : array of Longword;
    begin
      SetLength(m_temp, Length(m));                
      // Быстрая очистка корзин    
      FillChar(s[0], 256 * 4 * SizeOf(Longword), 0);   
    
      // Заполнение корзин
      for i := 0 to High(m) do                         
      begin
        k := m[i];
        Inc(s[0,offset[0]]);
        Inc(s[1,offset[1]]);
        Inc(s[2,offset[2]]);
        Inc(s[3,offset[3]]);
      end;
    
      // Пересчёт смещений для корзин
      for i := 1 to 255 do                             
      begin
        Inc(s[0,i], s[0,i-1]);
        Inc(s[1,i], s[1,i-1]);
        Inc(s[2,i], s[2,i-1]);
        Inc(s[3,i], s[3,i-1]);
      end;
    
      // Вызов сортировки по байтам от младших к старшим
      Sort_step(m, m_temp, s[0], 0);                   
      Sort_step(m_temp, m, s[1], 8);
      Sort_step(m, m_temp, s[2], 16);
      Sort_step(m_temp, m, s[3], 24);
    
      SetLength(m_temp, 0);                            
    end;
    //==================================================
    ...
    SetLength(m, n);
    for i := 0 to n - 1 do 
      m[i] := Random(65536 * 65536);  
    ...
    RSort(m);  
    ...
    

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

    Последовательность выполнения состоит из двух этапов:

    1. Для каждого блока (по восемь двоичных разрядов – 1 байт (оптимальная величина)), методом подсчёта, вычисляется его положение в новом массиве.
    2. Последовательно для каждого блока (от младших разрядов к старшим) производится перемещение на рассчитанную ранее позицию.

    Улучшения:

    1. Для массива смещений используем выравнивание в памяти, а благодаря небольшому объёму он помещается в L1 – кэша процессора.
    2. Массив смещений заполняется сразу для всех разрядов, что позволяет пройтись по массиву для подсчёта только однажды.
    3. Расчёт позиций начинается не с головы массива, а с конца, это решает две задачи:
      • конец массива на первом проходе уже находится в «прогретом» кэше, что при больших массивах, даёт небольшое ускорение;
      • во-вторых нисходящий цикл к нулю короче на одну инструкцию ассемблера, на каждом шаге цикла, относительно восходящего цикла.
    4. Для каждой итерации (из четырёх) не используется вложенный цикл, пусть так менее красиво, но экономятся ещё несколько инструкций процессора.

    Из-за простоты код практически идентичен по скорости как 32, так и 64 битной сборке компилятора. При необходимости легко представить версию алгоритма для 16 и 64 разрядных чисел.

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



    Предложения и замечания по поводу оптимизаций одобряются.

    Спасибо.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 11

      +2
      На геймдеве была обширная тема про поразрядную сортировку. Мы там дошли до того, что обсуждали алиасинг кеша при prefetch-е записи в память.
        +1
        Занятное обсуждение, однако мне видится что несколько переусложнили решение вопроса. Могу конечно ошибаться. За ссылку спасибо.
          +3

          А если комбинировать sort step c подсчетом? По логике это будет только 2КБ сверху даже для 64х битных чисел, ведь после sort step старый подсчет больше не нужен.

            +1
            Идея заманчивая, но нет. К моменту сортировки нужно уже знать место вставки элемента. Эта информация и содержится в вычисленном заранее массиве.
            Если производить подсчёт в каждом шаге, то придется дополнительно обходить основной массив каждый раз. Это займёт гораздо больше операций, хотя да, мы экономим пару килобайт. На малых массивах это имеет смысл, а на миллионе элементов каждый дополнительный проход очень дорог.
              +2

              В sort step и так происходит обход каждого элемента основного массива, я предлагаю в том же цикле и делать подсчет для следующей перестановки, меняя массивы счётчиков. Да, эти 256 значений нужно будет занулять и потом пересчитать смещения, но это же и так делается.

                +1
                Если только для следующего разряда, то да, сработает.
                Хотя немного собьёт стройность конструкции, ведь что тогда считать на последнем шаге, видимо добавить проверку на не исполнение.
                Мысль мне нравиться попробую посмотрю на изменение производительности.
                  +1
                  Падение скорости получилась в среднем на 13% при n>1000, стоит ли это 2Кб памяти, сомнительно.
                  На меньших длинах есть небольшой выигрыш. Возможно данный код поддаётся улучшению.
                  Код
                  //======================================================
                  procedure RSort2(var m: array of Longword);
                  //--------------------------------------------------
                     procedure Sort_step(var source, dest, s_source, s_dest: array of Longword; const num: Byte);
                     var i,temp : Longword;
                         k,num1,num2 : Byte;
                         offset : array[0..3] of byte absolute temp;
                     begin
                       if num<3 then                                    // устанавливаем байт для проверки на следующем шаге
                         num2 := num+1
                       else
                         num2:=0;
                  
                       for i := 1 to 255 do                             // Пересчёт смещений для текущей корзины
                         Inc(s_source[i], s_source[i-1]);
                  
                       FillChar(s_dest, 256 * SizeOf(Longword), 0);
                  
                       num1 := num*8;
                       for i := High(source) downto 0 do
                       begin
                         temp := source[i];
                         Inc(s_dest[offset[num2]]);
                         k := temp SHR num1;
                         Dec(s_source[k]);
                         Dest[s_source[k]] := temp;
                       end;
                  
                     end;
                  //------------------------------------------------------------------------------
                  var s : array[0..1] of array[0..255] of Longword;  // Объявляем массив двух корзин первым, для выравнивания на стеке
                      i : longword;
                      k : Byte;
                      m_temp : array of Longword;
                  begin
                    SetLength(m_temp, Length(m));                    // Объявляем временный массив
                    FillChar(s[0], 256 * SizeOf(Longword), 0);       // Быстрая очистка первой корзины
                  
                    for i := 0 to High(m) do                         // Заполнение первой корзины
                    begin
                      k := m[i];
                      Inc(s[0,k]);
                    end;
                  
                    Sort_step(m, m_temp, s[0], s[1], 0);             // Вызов сортировки по байтам от младших к старшим
                    Sort_step(m_temp, m, s[1], s[0], 1);
                    Sort_step(m, m_temp, s[0], s[1], 2);
                    Sort_step(m_temp, m, s[1], s[0], 3);
                  
                    SetLength(m_temp, 0);                            // Высвобождаем память
                  end;
                  //======================================================
                  

                    +1
                    Вариант с отдельной функцией сортировки на последнем шаге, падение меньше около 4-5%, уже приемлемо.
                    код
                    //==================================================
                    procedure RSort2(var m: array of Longword);
                    //--------------------------------------------------
                       procedure Sort_step(var source, dest, s_source, s_dest: array of Longword; const num: Byte);
                       var i,temp : Longword;
                           k,num1,num2 : Byte;
                           offset : array[0..3] of byte absolute temp;
                       begin
                         num2 := num+1;                                   // устанавливаем байт для проверки на следующем шаге
                    
                         for i := 1 to 255 do                             // Пересчёт смещений для текущей корзины
                           Inc(s_source[i], s_source[i-1]);
                    
                         FillChar(s_dest, 256 * SizeOf(Longword), 0);
                    
                         num1 := num*8;
                         for i := High(source) downto 0 do
                         begin
                           temp := source[i];
                           Inc(s_dest[offset[num2]]);
                           k := temp SHR num1;
                           Dec(s_source[k]);
                           Dest[s_source[k]] := temp;
                         end;
                    
                       end;
                    //--------------------------------------------------
                       procedure Sort_step_last(var source, dest, s_source : array of Longword);
                       var i,temp : Longword;
                           k : Byte;
                       begin
                         for i := 1 to 255 do                             // Пересчёт смещений для текущей корзины
                           Inc(s_source[i], s_source[i-1]);
                    
                         for i := High(source) downto 0 do
                         begin
                           temp := source[i];
                           k := temp SHR 24;
                           Dec(s_source[k]);
                           Dest[s_source[k]] := temp;
                         end;
                       end;
                    //--------------------------------------------------
                    var s : array[0..1] of array[0..255] of Longword;  // Объявляем массив двух корзин первым, для выравнивания на стеке
                        i : longword;
                        k : Byte;
                        m_temp : array of Longword;
                    begin
                      SetLength(m_temp, Length(m));                    // Объявляем временный массив
                      FillChar(s[0], 256 * SizeOf(Longword), 0);       // Быстрая очистка первой корзины
                    
                      for i := 0 to High(m) do                         // Заполнение первой корзины
                      begin
                        k := m[i];
                        Inc(s[0,k]);
                      end;
                    
                      Sort_step(m, m_temp, s[0], s[1], 0);             // Вызов сортировки по байтам от младших к старшим
                      Sort_step(m_temp, m, s[1], s[0], 1);
                      Sort_step(m, m_temp, s[0], s[1], 2);
                      Sort_step_last(m_temp, m, s[1]);
                    
                      SetLength(m_temp, 0);                            // Высвобождаем память
                    end;
                    //================================================== 

                      +2
                      Я предполагаю что падение связано с уменьшением доступного для сортируемых массивов кэша. Ваш оригинальный алгоритм в цикле работал с 1КБ массивом счётчиков, а новый работает с двумя массивами, т.е. 2КБ.
                      P.S. Прикольно, что 4*256 = 1024, а 4*16 = 64 (т.е. массив целиком вмещается в кеш-линию если счётчики на пол-байта). В плане кэша MSD был бы лучше, так как уже после одного прохода элементы не будут перемещаться по всему массиву, а только внутри группы.
                        +1
                        Пробовал с проходом по 4 бита, падение 30-40%, видимо тут уже кэш не даёт такого преимущества как встроенные инструкции процессора на 1 байтовые вычисления и повторные проходы.
                        Есть желание опробовать гибрид MSD и LSD для разных проходов, если будут интересные результаты, напишу.
                          +1
                          MSD мне не очень нравится накладными расходами на внутренние циклы, размерность которых вероятностная величина. Не вижу как их сделать эффективно.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое