RadixSort, сортировка из красной книги

Май 8, 2012 — Шарахов А.П.

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

Самый большой миф о RadixSort

Мы будем рассматривать LSD-модификацию алгоритма поразрядной сортировки. Ее плюсы: скорость и устойчивость, минусы: дополнительная память и узкая специализация. Сразу же необходимо кое-что прояснить. Распространено мнение, что RadixSort на порядки превосходит по скорости QuickSort и другие сортировки, основанные на сравнениях. Но это не так. Совсем не так.

Программист редко сортирует числа, еще реже – только числа. Обычно требуется сортировать объекты, которые могут иметь числовые атрибуты. Т.е. требуется, чтобы процедура сортировки вызывала функцию получения ключа, что в некотором смысле аналогично вызову функции сравнения объектов быстрой сортировкой. Эта небольшая деталь – большой тормоз для RadixSort, что очень хорошо заметно на малых списках.

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

Фазы распределения

Экспериментально установлено, что для поразрядной сортировки 32-битных чисел оптимальным является 8-битный разряд и соответственно 4 фазы распределения. С целью достижения максимальной скорости все фазы распределения выделены в отдельные процедуры, например:

procedure Phase4(List, Temp, Cur: pointer; RadixKey: TRadixKey);
var
  j, k: integer;
begin;
  repeat;
    dec(pPointer(Cur));
    j:=RadixKey(pPointer(Cur)^) shr 24;
    k:=pIntegerArray(Temp)[j-256];
    pPointerArray(List)[k]:=pPointer(Cur)^;
    pIntegerArray(Temp)[j-256]:=k-1;
    until Cur=Temp;
  end;

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

Фаза подсчета

Особенностью функции подсчета является расположение массива счетчиков непосредственно перед временным списком. Так сделано для обеспечения высокой скорости работы фаз распределения.

В качестве результата функция подсчета возвращает флаги пропуска фаз распределения. Флаги вычисляются на основе анализа количества нулевых счетчиков для каждой фазы. Очевидно, что если оно равно 255 для двух последовательных фаз, то эти фазы можно пропустить, т.к. все данные попадут в одну корзину.

function Phase0(List, Temp, Cur: pointer; RadixKey: TShaRadixKey): integer;
const
  Skip: array[0..15] of integer= (0, 0, 0, 3, 0, 0, 6, 3, 0, 0, 0, 3, 12, 12, 12, 15);
var
  i, j, k, Zeros: integer;
begin;
  k:=0;
  for j:=-1024 to -1 do pIntegerArray(Temp)[j]:=k;
 
  repeat;
    dec(pPointer(Cur));
    j:=RadixKey(pPointer(Cur)^);
    inc(pIntegerArray(Temp)[j and 255 - 1024]);
    inc(pIntegerArray(Temp)[j shr 8 and 255 - 768]);
    inc(pIntegerArray(Temp)[j shr 16 and 255 - 512]);
    inc(pIntegerArray(Temp)[j shr 24 - 256]);
    until Cur=List;
 
  j:=-1024; k:=-1; Zeros:=0;
  repeat;
    if j and 255=0 then begin;
      k:=-1; Zeros:=Zeros shl 8;
      end;
    i:=pIntegerArray(Temp)[j];
    if i=0 then inc(Zeros);
    inc(k,i);
    pIntegerArray(Temp)[j]:=k;
    inc(j);
    until j=0;
 
  k:=0; Zeros:=Zeros xor -1;
  for j:=1 to 4 do begin;
    k:=k+k;
    if Zeros and $FF=0 then inc(k);
    Zeros:=Zeros shr 8;
    end;
  Result:=Skip[k];
  end;

Основная процедура

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

procedure ShaRadixSort(List: pointer; Count: integer; RadixKey: TShaRadixKey; RadixKeyHigh: TShaRadixKey= nil);
var
  Temp: array of pointer;
  Skip: integer;
begin;
  if Count<=0 then exit;
  SetLength(Temp, Count+1024);
  repeat;
    Skip:=Phase0(List, @Temp[1024], @pPointerArray(List)[Count], RadixKey);
    if Skip and 1=0 then Phase1(List, @Temp[1024], @pPointerArray(List)[Count], RadixKey);
    if Skip and 2=0 then Phase2(List, @Temp[1024], @Temp[Count+1024], RadixKey);
    if Skip and 4=0 then Phase3(List, @Temp[1024], @pPointerArray(List)[Count], RadixKey);
    if Skip and 8=0 then Phase4(List, @Temp[1024], @Temp[Count+1024], RadixKey);
    RadixKey:=RadixKeyHigh;
    RadixKeyHigh:=nil;
    until not Assigned(RadixKey);
  end;

Функции получения ключа

Примерный вид функций следующий:

//ascending order, signed integers
function ShaRadixKeyInteger(Item: pointer): integer;
begin;
  Result:=Cardinal(Item^) xor $80000000;
  end;
 
//ascending order, unsigned integers or low part of int64
function ShaRadixKeyCardinal(Item: pointer): integer;
begin;
  Result:=Cardinal(Item^);
  end;
 
//ascending order, high (signed) part of int64
function ShaRadixKeyInt64High(Item: pointer): integer;
type
  PCardinalArray= ^TCardinalArray;
  TCardinalArray= array[0..1] of cardinal;
begin;
  Result:=PCardinalArray(Item)[1] xor $80000000;
  end;

Для работы с 64-битным ключом требуются 2 функции, работающие с половинами ключа. Кроме того, для правильной поразрядной сортировки чисел со знаком необходимо, чтобы функция получения ключа инвертировала знаковый разряд. Если требуется сортировать данные в убывающем порядке, то надо дополнительно инвертировать все биты ключа:

//descending order, signed integers
function ShaRadixKeyIntegerDesc(Item: pointer): integer;
begin;
  Result:=Cardinal(Item^) xor $7FFFFFFF;
  end;
 
//descending order, unsigned integers or low part of int64
function ShaRadixKeyCardinalDesc(Item: pointer): integer;
begin;
  Result:=Cardinal(Item^) xor $FFFFFFFF;;
  end;
 
//descending order, high (signed) part of int64
function ShaRadixKeyInt64HighDesc(Item: pointer): integer;
type
  PCardinalArray= ^TCardinalArray;
  TCardinalArray= array[0..1] of cardinal;
begin;
  Result:=PCardinalArray(Item)[1] xor $7FFFFFFF;
  end;

Скорость поразрядной сортировки

Давайте измерим скорость поразрядной, гибридной и быстрой сортировок на массиве 10^5 указателей на случайные целые 32- и 64-битные числа. В качестве гибридной сортировки возьмем HybridSortSha_0AA_ASM, в качестве быстрой – сортировку из библиотеки RTL Delphi.

Для сравнения 32-битных чисел будем использовать самую быструю на Земле функцию сравнения:

function ShaCompareInt(Item1, Item2: Pointer): Integer;
var
  Second: integer;
begin;
  Result:=Integer(Item1^);
  Second:=Integer(Item2^);
  if Result xor Second>=0
    then Result:=Result-Second
    else Result:=Result or 1;
  end;

а для сравнения 64-битных чисел – ассемблерную функцию:

function ShaCompareInt64(Item1, Item2: Pointer): Integer;
asm
      mov ecx, dword ptr [eax+4]
      cmp ecx, dword ptr [edx+4]
      jg @GT
      je @Low
@LT:  or eax, -1
      ret
@Low: mov ecx, dword ptr [eax]
      cmp ecx, dword ptr [edx]
      jb @LT
      je @EQ
@GT:  mov eax, 1
      ret
@EQ:  xor eax, eax
      end;

Типичные результаты измерений приведены в таблице:

 Sort time of 10^5 items, ms
=============================
            Key length, bits
 Procedure ------------------
                32       64
-----------------------------
 RadixSort     2.84    6.94
 HybridSort   10.03   12.88
 QuickSort    13.16   17.27

Как и следовало ожидать, с преимуществом в 3.6 раза (в 1.8 для 64 бит) относительно ближайшего конкурента победила поразрядная сортировка. Если вас не смущает необходимость выделения дополнительной памяти под копию сортируемого списка, то можете забрать исходники.

на главную

Прикрепленный файл	Размер
ShaRadixSorts.pas	5.01 кб

Добавить комментарий

Comments (2)

Тест

Июль 7th, 2014 — Гость

Тема крутая
А ты не можешь выложить тестовое приложение, которые выдали тебе такой замер времени? Есть пара идей по улучшению алгоритма. Для чистоты эксперимента лучше взять твоё тестовое приложение.