Извиняюсь, не заменил в начале ложного утверждения, так как концовка была правильной. Лучшее время сортировки Шелла никак не уступает среднему времени быстрой сортировки. Тут всё очень просто, так лучшее время для Шелла — это на упорядоченной последовательности, отрабатывает гораздо быстрее лучшего времени быстрой. И причем тут тесты?
Извините, но вы то, что выше, читали? там про эту интроспективную сортировку упоминалось не раз. Алгоритм Шелла не самый быстрый, но по совокупности свойств (скорости, требованию к дополнительной памяти, стабильности и простоте) вполне достойный. Поэтому его наверное и используют в таких критических местах как ядра ОС.
Вы совершенно правы, никто с этим не спорит и не спорил. Но разница столь мала, что это преимущество быстрой сортировки с std::qsort (gcc) проявляется только на десятках и более миллионов единиц сортировки (извините, что приходится повторятся).
Насчет Шелла вы, возможно, не поняли о чем речь. 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).
нет, писал же — это интроспективная сортировка, которая иногда использует коды быстрой, но не всегда. И стандартом С++ прямо запрещено использовать быструю сортировку, так как std::sort всегда должна быть по порядку NlogN. Хотя мой материал показывает, что heapsort, которую иногда используют вместо быстрой, несколько медленнее, но гораздо быстрее N2.
У меня память выделяется не на стеке, а статично — это не проблема, если не хотим более 4 ГБ в массиве. Проблема была в том, что ABI для Microsoft Windows другой, а я с этой системой работаю мало и этого не знал. Пришлось чуть править код и использовать такой
код для 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 раза. Ещё почти уверен, что если перенести паскаль-код на С или С++ и скомпилировать с оптимизацией, то скорость будет примерно такая же или даже чуть быстрее из-за странных оптимизационных трюков. Обогнать оптимизирующий компилятор ручной работой с ассемблером сегодня очень сложно.
Как показывают тесты, до десятков миллионов чисел даже сортировки Шелла чуть быстрее и последние стабильны, т.е. гарантируют, что зависания не случится. Для меня самого был сюрприз, что qsort сломалась на миллиарде чисел — случай скорее редкостный, но и не невозможный. Рекомедую «просто для сортировки» использовать средства из коробки — std::sort, std::stable_sort — работают существенно быстрее qsort, имеют гарантию от сюрпризов и работают с любыми данными. Если нужно сортировать большие массивы си-строк, то использование (s)radixsort даст ускорение в несколько раз, а spread-сортировка будет наибыстрейшей во многих других случаях. Если совсем мало памяти, то метод Шелла не подведет, отработает достаточно быстро. Опций много и лучше всего подбирать алгоритм по задаче.
Благодарю вас. Но почему в личку? У вас очень интересный код и если кто захочет его запустить, то наверняка эта дискуссия ему поможет. Там более паскаль сегодня многие не знают. 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 показывает, что хитрые способы выбора опорной точки не гарантируют от зависания.
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.
и получил, что отсортировало с ошибкой. Может пришлёте версию, которая работает? Возможно, что что-то сделал не так сам — в этом случае надеюсь на корректирующую информацию.
С таким значением не встречался, а john в смысле толчок, не очень ухоженное отхожее место в штатах широко используют как в разговорах, так и в литературе. Кстати, в культовом монтипитонном фильме Бразилия есть эффектный момент с использованием слова willy — знатоки питона должны знать. :)
Можно предположить, что это такой тонкий американский юмор, такая аллюзия на типовой британский характер, Джона Буля. Англичане это слово не используют. Что касается Дика, то они это называют также willy или peter. Кстати, если что-то даже вполне обычное как-то некстати закончилось, то можно красиво сказать to peter out, например, The hot water always peters out in the middle of my shower — горячая вода всегда кончается, если я принимаю душ.
Тут почти всё от преподавателя зависит, а во многих вузах, к сожалению, значительная часть студентов более того, чтобы законспектировать и не думает, хотя Латех — это не для них, конечно.
Получил ожидаемые результаты. На том же компьютере для 108 случайных чисел — 9.5 сек., а 109 случайных чисел — 107.8 сек. Это 15-е место среди приведенных сортировок, между qsort_dualpivot и spin. Отставание от qsort_dualpivot примерно 7%. Все прочие быстрые сортировки биты, а qsort_dualpivot также использует вставки. Но отставание от лидера — почти в 3 раза. Ещё почти уверен, что если перенести паскаль-код на С или С++ и скомпилировать с оптимизацией, то скорость будет примерно такая же или даже чуть быстрее из-за странных оптимизационных трюков. Обогнать оптимизирующий компилятор ручной работой с ассемблером сегодня очень сложно.
и получил, что отсортировало с ошибкой. Может пришлёте версию, которая работает? Возможно, что что-то сделал не так сам — в этом случае надеюсь на корректирующую информацию.
lwn.net/Articles/22355
www.kernel.org/doc/Documentation/filesystems/seq_file.txt