Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 53
Спасибо, сам коллекционирую сортировки и не перестаю удивляться, что всё время узнаю о существовании новых алгоритмов. К тем примерно ста более-менее разным сортировкам, о которых мне известно после прочтения статьи добавились spinsort, pdqsort, flat stable sort… Иногда очень удивляюсь насколько изобретательны программисты, которые придумывают всё новые и новые способы упорядочивания. Какая-то удивительно неисчерпаемая тема.
На досуге внимательно ознакомлюсь с материалом и утащу в свою сокровищницу несколько новых драгоценных камней.
На досуге внимательно ознакомлюсь с материалом и утащу в свою сокровищницу несколько новых драгоценных камней.
Благодарю вас, но неужели знали про новейшую быструю сортировку с двумя опорными точками?
К тем примерно ста более-менее разным сортировкам, о которых мне известноВнушительная цифра. Не хотите опубликовать в виде статьи список своей коллекции? Хотя бы всего несколько строк на каждую сортировку:
— Номер (от 1 до 100)
— Название
— Краткая характеристика (простая, быстрая, похожа на предыдущую и т.д.)
— Ссылка на источник.
Думаю, что такой справочный список будет очень полезен. (Посмотрел, что у Вас много публикаций по сортировкам, но меньше 100 :), но и такому количеству Ваших публикаций индекс для поиска по ним будет полезен).
И спасибо автору!
Я потихоньку составляю своеобразный справочник всех сортировок в виде excel-приложения с макросами. Там и краткая справка по каждой сортировке и примерно для половины алгоритмов реализована пошаговая визуализация на vba. Приложение доступно, если интересно, то в моих статьях без особого труда найдёте ссылку на него.
Текущий список выглядит так (картинка кликабельна):
А вот эта штука тут есть? https://fuchsia.googlesource.com/fuchsia/+/refs/heads/master/src/graphics/lib/compute/hotsort/
-
del
А где сортировка воронкой от разработчика rybvv? Жаль ту тему удалили, такие жаркие комменты были.
В одном своём проекте на Pascal под Win64, нужен был максимально быстрый способ сортировать массив из миллионов INT рандомизированных значений.
Попробовав разные алгоритмы, написал разновидность комбинированного Q-sort и Insert-sort на Assembler. Эмпирическим путём выяснил, на малых размерах массива 16-24 элементов, Сортировка вставками показывает феноменальное быстродействие и не требует дополнительной памяти, достаточно регистров.
Для уменьшения выделения памяти на быструю сортировку правая часть разделения по опорному элементу рассчитывалась итеративно, тем самым меньше нагружая стек, что критично на огромных массивах.
Работало много быстрее библиотечных функций.
Попробовав разные алгоритмы, написал разновидность комбинированного Q-sort и Insert-sort на Assembler. Эмпирическим путём выяснил, на малых размерах массива 16-24 элементов, Сортировка вставками показывает феноменальное быстродействие и не требует дополнительной памяти, достаточно регистров.
Для уменьшения выделения памяти на быструю сортировку правая часть разделения по опорному элементу рассчитывалась итеративно, тем самым меньше нагружая стек, что критично на огромных массивах.
Работало много быстрее библиотечных функций.
Провожу код:
procedure qSort_insSort(var m : Array of LongWord; l,r : LongWord);
procedure ASM_QSort assembler;
ASM
@@START_SORT:
MOV R10,RDX
SUB R10,20 // Если отрезок меньше 20 элементов сортируем вставками (так быстрее)
CMP R10,RCX
JA @@ASM_QSort // Иначе сортируем быстрой сортировкой со срединным опорным элементом
// Сортировка вставками --------------------------------------------------------
MOV R8,RCX // i:=0;
@@I_BEGIN:
ADD R8,4 // i:=i+1;
CMP R8,RDX // while (i<=r) do
JA @@END // i>r
MOV R9,R8 // j:=i;
@@J_BEGIN:
CMP R9,0 // j<=0
JNA @@I_BEGIN // Оканчиваем итерацию j
MOV R10,R9 // (j)
SUB R9,4 // (j-1)
MOV EAX,DWord[R9] // m[j-1]
MOV EBX,DWord[R10] // m[j]
CMP EAX,EBX // m[j-1]<=m[j]
JNA @@I_BEGIN // Оканчиваем итерацию j
MOV DWord[R9],EBX
MOV DWord[R10],EAX
JMP @@J_BEGIN
// Qsort с рекурсией -----------------------------------------------------------
@@ASM_QSort:
MOV R8,RCX
ADD R8,RDX
SHR R8,3
SHL R8,2
MOV R10D,DWord[R8] // находим срединный элемент
MOV R8,RCX // i:= P1; j:= P2;
MOV R9,RDX
@@i_START: // while (o < m[j]) do dec(j);
MOV EAX,DWord[R8]
CMP EAX,R10D
JNL @@j_START // если больше или равно
ADD R8,4
JMP @@i_START
@@j_START: // while (PLongWord(j)^ > o) do dec(j,4);
MOV EBX,DWord[R9]
CMP EBX,R10D
JNG @@j_STOP // если меньше или равно
SUB R9,4
JMP @@j_START
@@j_STOP:
CMP R8,R9 // if (i <= j) then
JG @@NO_XCHG // если меньше или равно
MOV EAX,DWord[R8] // temp:=m[i]; m[i]:=m[j]; m[j]:=temp;
MOV EBX,DWord[R9]
MOV DWord[R8],EBX
MOV DWord[R9],EAX
ADD R8,4 // inc(i); dec(j);
SUB R9,4
@@NO_XCHG:
CMP R8,R9 // until (i > j);
JNG @@i_START // если меньше или равно
CMP RCX,R9 // if (P1 < j) then
JNB @@SORT1 // Jump, если больше или равно
PUSH R8 // i
PUSH RDX // p2
// Первый аргумент (p1) уже в регистре RCX
MOV RDX,R9 // Устанавливаем второй аргумент (j)
CALL ASM_QSort // вызываем Сортировку первого отрезка (рекурсивно)
POP RDX // p2
POP R8 // i
@@SORT1:
CMP R8,RDX // if (i < P2) then
JNB @@END // Jump, если больше или равно
MOV RCX,R8 // Устанавливаем первый аргумент (i)
// Второй аргумент (p2) уже в регистре RDX
JMP @@START_SORT // вызываем Сортировку второго отрезка (Без рекурсии)
@@END:
END;
// Вызов процедуры сортировки
begin
ASM
CMP R8,R9 // Если L>=R
JNB @@NO_RUN
CMP RDX,R9 // Если LENGTH(M)>=R
JA @@NO_RUN
CMP R8,0 // Если L<0
JB @@NO_RUN
CMP RDX,0 // Если LENGTH(M)=0
JE @@NO_RUN
LEA RDX,[RCX+R9*4]
LEA RCX,[RCX+R8*4]
CALL ASM_QSort
XOR RAX,RAX
JMP @@END
@@NO_RUN:
MOV RAX,1
@@END:
END;
end;
Какой у вас интересный и выразительный Паскаль получился...
Сам проект на паскале, но одна высоконагруженная функция на ассемблере это же мелочь, правда?
Паскаль как и С очень близки к железу по организации доступа памяти. В данном случае в целях оптимизации была использована передачи аргументов в функцию через регистры, не используя стек. Для обычных задач это не требуется, но тут выжимал все соки.
Паскаль как и С очень близки к железу по организации доступа памяти. В данном случае в целях оптимизации была использована передачи аргументов в функцию через регистры, не используя стек. Для обычных задач это не требуется, но тут выжимал все соки.
Добавил несколько строк кода
и получил, что отсортировало с ошибкой. Может пришлёте версию, которая работает? Возможно, что что-то сделал не так сам — в этом случае надеюсь на корректирующую информацию.
const SS = 100;
var a: array[1 .. SS]of longword;
var i: longint;
begin
for i := 1 to SS do a[i] := random(SS);
qSort_insSort(a, 0, SS - 1);
for i := 1 to SS - 1 do
if a[i - 1] > a[i] then begin
writeln('error i = ', i, ' a[i-1] = ', a[i - 1], ' a[i] = ', a[i]);
halt(2)
end;
end.
и получил, что отсортировало с ошибкой. Может пришлёте версию, которая работает? Возможно, что что-то сделал не так сам — в этом случае надеюсь на корректирующую информацию.
Благодарю за интерес к вопросу.
Собственно, у Вас должно всё нормально выводиться, но учтите, собирать проект нужно только под 64-битной версией компилятора. У Win32 и Win64 разные соглашения о вызовах. Если не разберётесь пишите в личку.
Собственно, у Вас должно всё нормально выводиться, но учтите, собирать проект нужно только под 64-битной версией компилятора. У Win32 и Win64 разные соглашения о вызовах. Если не разберётесь пишите в личку.
Заголовок спойлера
Procedure test();
const n=16;
var m:Array of LongWord;
i:LongWord;
begin
SetLength(m,n);
Randomize;
for i:=0 to Length(m)-1 do m[i]:=Random(9000)+1000;
for i:=0 to n-1 do WRITE(inttostr(m[i])+' ');
WRITELN('');
qSort_insSort(@m[0],0,n-1);
for i:=0 to n-1 do WRITE(inttostr(m[i])+' ');
WRITELN('');
end;
Благодарю вас. Но почему в личку? У вас очень интересный код и если кто захочет его запустить, то наверняка эта дискуссия ему поможет. Там более паскаль сегодня многие не знают. 3наком с ABI x86, но тут что-то другое. Всё-таки непонятно почему мой код не работает правильно, передаю массив по ссылке, но он при выходе из пп не меняется, a если использую @a[0], то получаю ошибку Error: Call by var for arg no. 1 has to match exactly: Got «Pointer» expected "{Open} Array Of LongWord". :( Если запускаю код из вашего последнего примера, то картинка та же. Извините, сейчас нет времени самому разобраться в коде, жду Ваших подсказок. Повторю, мой код успешно собирается и запускается, только работает некорректно.
Я очень извиняюсь, конечно же:
qSort_insSort(m,0,n-1);
По поводу Вашего кода, проверил загвоздка в том, что вы выделяете память на стеке, а нужно только в куче, так как стек и так интенсивно используется в работе процедуры. Так мы используем свободные регистры на адресацию к массиву.
Собрал проект на Lazarus64.
qSort_insSort(m,0,n-1);
По поводу Вашего кода, проверил загвоздка в том, что вы выделяете память на стеке, а нужно только в куче, так как стек и так интенсивно используется в работе процедуры. Так мы используем свободные регистры на адресацию к массиву.
Собрал проект на Lazarus64.
У меня память выделяется не на стеке, а статично — это не проблема, если не хотим более 4 ГБ в массиве. Проблема была в том, что ABI для Microsoft Windows другой, а я с этой системой работаю мало и этого не знал. Пришлось чуть править код и использовать такой
Получил ожидаемые результаты. На том же компьютере для 108 случайных чисел — 9.5 сек., а 109 случайных чисел — 107.8 сек. Это 15-е место среди приведенных сортировок, между qsort_dualpivot и spin. Отставание от qsort_dualpivot примерно 7%. Все прочие быстрые сортировки биты, а qsort_dualpivot также использует вставки. Но отставание от лидера — почти в 3 раза. Ещё почти уверен, что если перенести паскаль-код на С или С++ и скомпилировать с оптимизацией, то скорость будет примерно такая же или даже чуть быстрее из-за странных оптимизационных трюков. Обогнать оптимизирующий компилятор ручной работой с ассемблером сегодня очень сложно.
код для Linux
ASM
CMP RDX,RCX // Если L>=R
JNB @@NO_RUN
CMP RSI,RCX // Если LENGTH(M)>=R
JA @@NO_RUN
CMP RDX,0 // Если L<0
JB @@NO_RUN
CMP RSI,0 // Если LENGTH(M)=0
JE @@NO_RUN
LEA RAX,[RDI+RCX*4]
LEA RCX,[RDI+RDX*4]
MOV RDX,RAX
CALL ASM_QSort
XOR RAX,RAX
JMP @@END
@@NO_RUN:
MOV RAX,1
@@END:
END;
Получил ожидаемые результаты. На том же компьютере для 108 случайных чисел — 9.5 сек., а 109 случайных чисел — 107.8 сек. Это 15-е место среди приведенных сортировок, между qsort_dualpivot и spin. Отставание от qsort_dualpivot примерно 7%. Все прочие быстрые сортировки биты, а qsort_dualpivot также использует вставки. Но отставание от лидера — почти в 3 раза. Ещё почти уверен, что если перенести паскаль-код на С или С++ и скомпилировать с оптимизацией, то скорость будет примерно такая же или даже чуть быстрее из-за странных оптимизационных трюков. Обогнать оптимизирующий компилятор ручной работой с ассемблером сегодня очень сложно.
Вы провели отличную работу. Пришёл к такому же выводу: микроассемблерные вставки не стоят тех усилий что на них затрачиваются, особенно при смене компилятора или платформы. Это был отличный опыт, отрицательный результат не менее ценен. Уверен из алгоритма можно ещё немного выжать, но зачем? Для большинства повседневных задач хватает библиотечных функций.
Благодарю вас. Сделал
И оказалось, что в данном случае ассемблерные вставки дали преимущество над g++ -O3 примерно в 12%. Код сортировки вставками можно чуть улучшить, взять, например, из quick_double_pivot. Само использование вставок даёт при сортировке случайных чисел примерно 10% ускорения. Спасибо за интересный код.
код на С
void MQSort(vector<int> &m, int l, int r) {
LOOP:
if (r - l <= 20) {
int i = l + 1, j;
while (i <= r) {
j = i++;
while (j > 0 && m[j - 1] > m[j]) {
swap(m[j - 1], m[j]);
--j;
}
};
return;
}
int o = m[(l + r)/2], i = l, j = r;
do {
while (m[i] < o) ++i;
while (o < m[j]) --j;
if (i <= j)
swap(m[i++], m[j--]);
} while (i <= j);
if (l < j) MQSort(m, l, j);
if (i < r) {
l = i;
goto LOOP;
}
}
И оказалось, что в данном случае ассемблерные вставки дали преимущество над g++ -O3 примерно в 12%. Код сортировки вставками можно чуть улучшить, взять, например, из quick_double_pivot. Само использование вставок даёт при сортировке случайных чисел примерно 10% ускорения. Спасибо за интересный код.
Как вариант оптимизации, предлагаю Вам поиграться с коэффициентом выбора разбиения "<20" возможно на некоторых диапазонах его стоит делать меньше или больше, я выбрал среднее, возможно есть более оптимальные значения.
del
Исправил грубую ошибку в ассемблерном коде и немного изменил алгоритм, получил небольшой прирост в скорости (3-9%). Всё сильно зависит от исходных данных. Чем больше повторов в значениях тем быстрее работает относительно прежнего.
Код
// Комбинированная сортировка --------------------------------------------------
procedure qSort_insSort2(var m : Array of LongWord; l,r : LongWord);
procedure ASM_QSort assembler;
ASM
@@START_SORT:
MOV R8,RCX // i:=0; Используется в обоих алгоритмах экономим 3 байта
MOV RAX,RDX
SUB RAX,RCX
CMP RAX,R11
JGE @@Q_Sort // Иначе сортируем быстрой сортировкой со срединным опорным элементом
// Сортировка вставками --------------------------------------------------------
//MOV R8,RCX // i:=0;
@@I_BEGIN:
ADD R8,R12 // i:=i+1;
CMP R8,RDX // while (i<=r) do
JA @@END // i>r
MOV R9,R8 // j:=i;
@@J_BEGIN:
CMP R9,RCX // j<=0
JNA @@I_BEGIN // Оканчиваем итерацию j
MOV R10,R9 // (j)
SUB R9,R12 // (j-1)
MOV EAX,DWord[R9] // m[j-1]
MOV EBX,DWord[R10] // m[j]
CMP EAX,EBX // m[j-1]<=m[j]
JNA @@I_BEGIN // Оканчиваем итерацию j
MOV DWord[R9],EBX // Меняем местами
MOV DWord[R10],EAX
JMP @@J_BEGIN
// Qsort с рекурсией -----------------------------------------------------------
@@Q_Sort:
//MOV R8,RCX
ADD R8,RDX
SHR R8,3
SHL R8,2
MOV R10D,DWord[R8] // находим срединный элемент
MOV R8,RCX // i:= P1;
MOV R9,RDX // j:= P2;
@@i_START: // while (o < m[j]) do dec(j);
MOV EAX,DWord[R8]
CMP EAX,R10D
JNL @@j_START // если больше или равно
ADD R8,R12
JMP @@i_START
@@j_START: // while (PLongWord(j)^ > o) do dec(j,4);
MOV EBX,DWord[R9]
CMP EBX,R10D
JNG @@j_STOP // если меньше или равно
SUB R9,R12
JMP @@j_START
@@j_STOP:
CMP R8,R9 // if (i <= j) then
JG @@NO_XCHG // если меньше или равно
MOV EAX,DWord[R8] // temp:=m[i]; m[i]:=m[j]; m[j]:=temp;
MOV EBX,DWord[R9]
MOV DWord[R8],EBX
MOV DWord[R9],EAX
ADD R8,R12 // inc(i); dec(j);
SUB R9,R12
@@NO_XCHG:
CMP R8,R9 // until (i > j);
JNG @@i_START // если меньше или равно
CMP RCX,R9 // if (P1 < j) then
JNB @@SORT1 // Jump, если больше или равно
PUSH R8 // i
PUSH RDX // p2
// Первый аргумент (p1) уже в регистре RCX
MOV RDX,R9 // Устанавливаем второй аргумент (j)
CALL ASM_QSort // вызываем Сортировку первого отрезка (рекурсивно)
POP RDX // p2
POP R8 // i
@@SORT1:
CMP R8,RDX // if (i < P2) then
JNB @@END // Jump, если больше или равно
MOV RCX,R8 // Устанавливаем первый аргумент (i)
// Второй аргумент (p2) уже в регистре RDX
JMP @@START_SORT // вызываем Сортировку второго отрезка (Без рекурсии)
@@END:
END;
begin
ASM
CMP R8,R9 // Если L>=R
JNB @@NO_RUN
CMP R9,RDX // Если R>LENGTH(M)
JA @@NO_RUN
CMP R8,0 // Если L<0
JB @@NO_RUN
CMP RDX,0 // Если LENGTH(M)=0
JE @@NO_RUN
LEA RDX,[RCX+R9*4]
LEA RCX,[RCX+R8*4]
MOV R11,100 // Будем хранить константу сравнения в регистре R11 так экономим 1 байт инструкций на каждом цикле
MOV R12,4
CALL ASM_QSort
XOR RAX,RAX
JMP @@END
@@NO_RUN:
MOV RAX,1
@@END:
END;
end;
Результат получился почти никакой. Ускорение только менее 1%. Оптимизировать современные ассемблеры штука непростая, тут две команды могут быть намного быстрее эквивалентной одной, неопределенности из-за поведения предикторов переходов и много других тонкостей. Приведу ещё некоторые данные по результатам работы с вашим кодом с миллиардом чисел: на нулевых данных — 33 cек. (20.5 место — между разными Шеллами), на случайных 0 и 1 — 36 сек. (9.5 место — между Шеллом и flat_stable), на диапазоне из 100 случайных чисел — 50.5 сек. (12.5 место — между std::sort и qsort_hoare2), на упорядоченных числах — 36.7 сек. (18.5 место — между Шеллом и утроенным массивом), на числах c инвертированным порядком — 37 сек. (11.5 место — между хешем и утроенным массивом), на частично упорядоченных числах — 48.3 сек. (7.5 место — между spread и flat_stable), на числах c частично инвертированным порядком — 48.2 сек. (9.5 место — между spread и spin), по заполнения типа 7 данных привести не могу — их пришлось бы ждать возможно больше года. :) Может как-нибудь перепишу ваш код в С++ и добавлю данные в таблицы…
30 лет (в 1989 году) назад написал на турбопаскале свой первый профессиональный код — библиотеку сортировок. Алгоритмы черпал из третьего тома Кнута — быстрая, двойными включениями, прямым выбором, пузырьковая, шейкер, пирамидальная.
В 1991 году в рамках диплома пытался создать адаптивную (с точки зрения выбора алгоритма сортировки) систему для прикладных задач. Но все это так и осталось дипломом — в продакте используется исключительно быстрая сортировка. Кстати и по сей день — что является предметом моей гордости :)
В 1991 году в рамках диплома пытался создать адаптивную (с точки зрения выбора алгоритма сортировки) систему для прикладных задач. Но все это так и осталось дипломом — в продакте используется исключительно быстрая сортировка. Кстати и по сей день — что является предметом моей гордости :)
В каком продакшен? Быстрая сортировка сегодня — это не лучший выбор. Другие и быстрее, и стабильнее. А мой пример с qsort показывает, что хитрые способы выбора опорной точки не гарантируют от зависания.
Продакшен — учетные ментовские задачи уровня райотдела и города (люди, оружие, прописка, загранпаспорта и т.д.). Написано, как Вы понимаете, очень давно по современным меркам. Реализация алгоритма изначально — классическая рекурсивная, по Кнуту. Потом добавили вариацию нерекурсивную. В таком виде эта штука 30 лет и работает :) Естественно, без зависаний :)
А какой алгоритм вы бы посоветовали как дефолтную замену qsort? Без оптимизации под конкретную задачу с конкретными требованиями, а просто «вот это нужно сейчас отсортировать».
Как показывают тесты, до десятков миллионов чисел даже сортировки Шелла чуть быстрее и последние стабильны, т.е. гарантируют, что зависания не случится. Для меня самого был сюрприз, что qsort сломалась на миллиарде чисел — случай скорее редкостный, но и не невозможный. Рекомедую «просто для сортировки» использовать средства из коробки — std::sort, std::stable_sort — работают существенно быстрее qsort, имеют гарантию от сюрпризов и работают с любыми данными. Если нужно сортировать большие массивы си-строк, то использование (s)radixsort даст ускорение в несколько раз, а spread-сортировка будет наибыстрейшей во многих других случаях. Если совсем мало памяти, то метод Шелла не подведет, отработает достаточно быстро. Опций много и лучше всего подбирать алгоритм по задаче.
Спасибо за ответ!
Так std::sort — это ж и есть плюсовая шаблонная реализация quicksort, разве нет?
Так std::sort — это ж и есть плюсовая шаблонная реализация quicksort, разве нет?
нет, писал же — это интроспективная сортировка, которая иногда использует коды быстрой, но не всегда. И стандартом С++ прямо запрещено использовать быструю сортировку, так как std::sort всегда должна быть по порядку NlogN. Хотя мой материал показывает, что heapsort, которую иногда используют вместо быстрой, несколько медленнее, но гораздо быстрее N2.
И стандартом С++ прямо запрещено использовать быструю сортировку, так как std::sort всегда должна быть по порядку NlogN.
Гм. Тут, как мне кажется, Вы неверно выразились. Позвольте сделать утверждение: «Не существует алгоритма сортировки, который имеет худшую сложность NlogN». Наверное, в стандартах C++ прописано что-то иное.
Что касается сортировки Шелла, то там лучшее время N log2 N (где двоечка — это квадрат логарифма), в то время как у быстрой среднее время N log N. Худшее время у них одинаковое N2 (квадрат). Источники — раз и два.
Поэтому можно сколько угодно написать «как показывают тесты ...», но математику никто не отменял и сути проистекающих процессов это не изменит.
Теперь что касается сортировки миллионов и миллиардов чисел. Можно ли привести пример прикладной области, в которой регулярно приходится сортировать такие большие наборы чисел и причем каждые раз разные? Конечно, мы можем пробовать конкретные реализации алгоритмов на прочность, как японскую бензопилу, из спортивного интереса. Но в реальной жизни это скорее всего означает большую ошибку проектирования.
Насчет Шелла вы, возможно, не поняли о чем речь. N2 — это для случая плохих смещений — кто же с такими работает? А для хороших смещений в тексте статьи и в википедии предел худшести другой — N(log N/log log N)2 — это, повторю, очень мало отличается от Nlog N и мои результаты это очень хорошо подтверждают. Что касается, что миллиард — это много, то это почти смешно. Читал, что какие-то авторитеты в не так уж далёкое время утверждали, что 64 КБ — это много, а всем известный Билл говорил чуть позже примерно то же про 640 КБ… Данных много и гораздо больше миллиардов единиц. Как и писал, есть стабильные методы побыстрее Шелла, например, flat_stable… По std::sort смотрите стандарт — en.cppreference.com/w/cpp/algorithm/sort — поэтому правильное утверждение «существует много алгоритмов с худшим случаем NlogN» и более того поразрядные сортировки работают стабильно на любых данных с O(N).
Насчет Шелла вы, возможно, не поняли о чем речь.
Давайте я еще раз повторю свою мысль — лучшее время сортировки Шелла по вычислительной сложности уступает среднему времени быстрой сортировки. Это математически достоверный результат, а не «как показывают мои тесты». Вот Вам пруф о том, что средний результат сортировки Шела хуже N log N.
Вы совершенно правы, никто с этим не спорит и не спорил. Но разница столь мала, что это преимущество быстрой сортировки с std::qsort (gcc) проявляется только на десятках и более миллионов единиц сортировки (извините, что приходится повторятся).
Извиняюсь, не заменил в начале ложного утверждения, так как концовка была правильной. Лучшее время сортировки Шелла никак не уступает среднему времени быстрой сортировки. Тут всё очень просто, так лучшее время для Шелла — это на упорядоченной последовательности, отрабатывает гораздо быстрее лучшего времени быстрой. И причем тут тесты?
Я говорил не про время, а про алгоритмическую сложность. Лучшее, среднее и худшее время есть доказанные математические формулы. Ссылки на них приводил — сравнение формул (N log2 N) vs (N log N) весьма наглядно. [Двойка в логарифме означает квадрат логарифма].
А тесты здесь притом — Вы в своих доводах упоминаете «как показывают мои тесты» и дальше декларация чего-то. Это, хм-м, не аргумент. Вы можете сколько угодно на примерах демонстрировать скорость сортировки Шелла, но против формул не попрешь. Или Вы с ними не согласны?
А тесты здесь притом — Вы в своих доводах упоминаете «как показывают мои тесты» и дальше декларация чего-то. Это, хм-м, не аргумент. Вы можете сколько угодно на примерах демонстрировать скорость сортировки Шелла, но против формул не попрешь. Или Вы с ними не согласны?
Мои тесты именно и подтверждают все формулы, кроме сортировок деревом и кучей. Последние случаи, как раз, хороший повод проверить эти методы кому-нибудь ещё. Могу предположить, что мне нужно кое-что объяснить. Что в формулах о скорости обычно присутствует символ О, который означает соответствие с точностью до множителя. Так вот эти множители они для практики весьма важны. У Шелла этот множитель меньше, чем у быстрой сортировки и это объясняет почему Шелл до довольно больших массивов обгоняет быструю.
Что касается, что миллиард — это много, то это почти смешно.
То есть реальных примеров привести не можете? Обсуждаем сферического коня в вакууме?
поэтому правильное утверждение «существует много алгоритмов с худшим случаем NlogN» и более того поразрядные сортировки работают стабильно на любых данных с O(N).
Я был неправ, а Вы правы в отношении худшей сложности. Например, вот — сортировка интросорт, имеет среднюю и наихудшую производительность N log N.
Только мне совершенно непонятно, почему Вы упоминаете сортировку Шелла в своей рекомедации — далеко не самый лучший алгоритм с точки зрения вычислительной сложности.
Сортировка Шелла по сути является улучшенной версией сортировки вставками, поэтому, не исключено, что является одним из наилучших вариантов для крупных почти упорядоченных массивов.
Сортировка простыми вставками на почти упорядоченных массивах достигает сложности O(n), мне пока неясно, почему в аналогичных условиях «шелл» должен показывать худшие результаты.
Сортировка простыми вставками на почти упорядоченных массивах достигает сложности O(n), мне пока неясно, почему в аналогичных условиях «шелл» должен показывать худшие результаты.
Э-э-э, изначально вопрос звучал как «А какой алгоритм вы бы посоветовали как дефолтную замену qsort? Без оптимизации под конкретную задачу с конкретными требованиями, а просто «вот это нужно сейчас отсортировать».» и никто не говорил про «крупные почти упорядоченные массивы».
То есть фрагмент ответа «Рекомедую «просто для сортировки» использовать средства из коробки» мне абсолютно понятен, а вот зачем всплыла сортировка Шелла — нет. Ну да ладно — возможно, ответ кроется в личных симпатиях автора :) Я же питаю симпатию к qsort :)
То есть фрагмент ответа «Рекомедую «просто для сортировки» использовать средства из коробки» мне абсолютно понятен, а вот зачем всплыла сортировка Шелла — нет. Ну да ладно — возможно, ответ кроется в личных симпатиях автора :) Я же питаю симпатию к qsort :)
Извините, но вы то, что выше, читали? там про эту интроспективную сортировку упоминалось не раз. Алгоритм Шелла не самый быстрый, но по совокупности свойств (скорости, требованию к дополнительной памяти, стабильности и простоте) вполне достойный. Поэтому его наверное и используют в таких критических местах как ядра ОС.
Могу предположить, что если бы в интросорт использовали сортировку Шелла, а не кучей, то это было бы быстрее для случаев, когда быстрая сортировка не идёт.
Мне кажется, что Ваше первое образование было гуманитарным, а потом Вы увлеклись сортировками.
Нигде в Ваших упоминаниях сортировки интро выше не звучало про её худшую вычислительную сложность N log N. Я же упомянул этот алгоритм исключительно в этом контексте — это была иллюстрация признания моей ошибки.
А что касается достойности алгоритма — не могу спорить, это такое понятие, которое формулой не измеришь. Нахождение его в ядре ОС означает, что алгоритм очень прозрачный и простой и разработчики совершенно к месту применяют Принцип Оккама.
Нигде в Ваших упоминаниях сортировки интро выше не звучало про её худшую вычислительную сложность N log N. Я же упомянул этот алгоритм исключительно в этом контексте — это была иллюстрация признания моей ошибки.
А что касается достойности алгоритма — не могу спорить, это такое понятие, которое формулой не измеришь. Нахождение его в ядре ОС означает, что алгоритм очень прозрачный и простой и разработчики совершенно к месту применяют Принцип Оккама.
del
del
del
Весьма заинтересовало, как всё-таки хипсорт на очень больших массивах стал тормозить. Не может тут дело быть в том, что он не влезает в кэш и делает по сути рандомные обращения в сортируемые массив? То есть он продолжает оставаться O(N*log N), но уже в случае с неэффективным кэшем.
Почему только на больших? Куча на числовых данных любого размера отстаёт по порядку даже от Шелла, но обычно чуть обгоняет дерево. А вот на строках куча обгоняет Шелла, что означает, что дорогих операций сравнения там всё же поменьше. Предполагая, что алгоритмы кучи и дерева заслуживают более тщательного изучения, официальные текущие данные по ним явно немного лучше реальных. Кэш, конечно, влияет, но он влияет и на другие алгоритмы. Осмелюсь утверждать, что у кучи и дерева (точнее их стандартных реализаций) имеем скорее O(Nlog2N) или даже чуть хуже. Провести соответствующие тесты совсем несложно…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
И ещё о сортировках