Как стать автором
Поиск
Написать публикацию
Обновить

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

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

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

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

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

Всего голосов 2: ↑2 и ↓0+2
Если только для следующего разряда, то да, сработает.
Хотя немного собьёт стройность конструкции, ведь что тогда считать на последнем шаге, видимо добавить проверку на не исполнение.
Мысль мне нравиться попробую посмотрю на изменение производительности.
Всего голосов 1: ↑1 и ↓0+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: ↑1 и ↓0+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;
//==================================================

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

Публикации

Показать лучшие за всё время

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr