HabrArkady 4 мар 2020 в 04:05

О быстрой сортировке, сложности 2*N

2 мин

10K

Алгоритмы*

Из песочницы

Recovery Mode

-63

155

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

Petrenuk 4 мар 2020 в 04:25

Что за алгоритм? Кем разработан?
Знакома ли авторам big-O нотация? Если вы говорите об асимптотической сложности алгоритма, выражение 2*N не имеет смысла, пишут O(N). Иначе вам придется пояснять что такое N. Операции? Сравнения?

HabrArkady 7 мар 2020 в 03:30

Я специально написал, что сложность 2*N. Я нигде не понимал это как O(2*N). Прекрасно знаю, что означает O(N). Это может быть и 2*N, и 10*N, и 1000*N. Вообще запись O(N) означает k*N, где k много меньше N (k<<N). Почему я написал, что сложность 2*N. Алгоритм линейный, в нем нет сравнений элементов друг с другом. С каждым элементом выполняются определенные действия. Это одно N. Второе N – это накладные расходы. В реальности они много меньше N, но я поднял границу до N. Вот почему я написал, что сложность алгоритма 2*N. Если бы накладные расходы были сравнимы с N или кратны N, тогда я бы написал, что сложность алгоритма O(N). Но накладные расходы много меньше N.

Petrenuk 7 мар 2020 в 05:03

Я поддерживаю вашу увлечённость алгоритмами и ни в коем случае не стремлюсь охладить ваш энтузиазм. Но если вы хотите чтобы ваш анализ воспринимали серьезно, желательно придерживаться строгой общепринятой терминологии. Если вы используете big-O нотацию, читателю сразу понятно что речь идёт об асимптотической сложности, которая растёт линейно с увеличением объема входных данных. Если вы пишете «сложность алгоритма 2*N», это можно интерпретировать как угодно. Есть хорошие причины почему в научных исследованиях пользуются строгими метриками, например системой СИ. Если бы в каждой статье по астрофизике использовались произвольные аршины и попугаи, сравнивать результаты было бы чрезвычайно сложно. И ваше пояснение про накладные расходы не делает картину более понятной.

По поводу алгоритма и сложности. Давно известно что алгоритмы основанные только на сравнениях имеют оптимальную сложность O(nlogn). Любые варианты с меньшей сложностью так или иначе используют ограниченность пространства ключей, либо другие свойства данных. Скорее всего вы изобрели radix, или counting sort, или trie, или какой-то вариант другой известной идеи. Может быть вы придумали что-то новое и полезное, в таком случае снимаю шляпу! Но из статьи этого не видно.

Сам факт того что какой-то кастомный алгоритм сортировки для определенного типа данных может быть быстрее std::sort никого не удивит. std::sort это универсальный алгоритм основанный только на сравнениях, который не использует знания о типах данных никаким образом. Когда программист вызывает std::sort, он как бы говорит системе: интерпретируй мои данные как абстрактные ключи и используй operator< для их сравнения, я знаю что я делаю. Создатели stl не пытались предоставить наибыстрейший алгоритм сортировки для всех возможных типов данных.

lair 7 мар 2020 в 11:18

Прекрасно знаю, что означает O(N).
С каждым элементом выполняются определенные действия. Это одно N.

Нет, вы явно не знаете, что означает O(N).

в нем нет сравнений элементов друг с другом

Значит, это не универсальный алгоритм сортировки. Что и требовалось доказать.

indomit 4 мар 2020 в 04:30

Четырех миллионов строк недостаточно чтобы сравнить эти алгоритмы.
Сложность std:sort — O(N·log(N)).
log(4 500 000) = 6,6.
Т.е сравниваются алгоритмы сложности (как бы) «О(6N)» и «O(2N)», а это по сути одна и та же сложность. Так же при такой схожей сложности еще влияет и качество реализации алгоритма.

Чтобы их сравнить нужно чтобы log(N) был как минимум на порядок больше двух.
Это речь о 10^20 строк. Как часто нам приходится сортировать такое количество данных? Не думаю что в реальном использовании этих алгоритмов можно почувствовать значительную разницу.

HabrArkady 4 мар 2020 в 04:46

Четыре миллиона это только слова. Каждое слово состоит из букв. Сортировка полная, т.е. сортировка не только по первой букве, а по всем буквам. Если в среднем каждое состоит из, предположим, состоит k-букв, то нужно умножить 4 миллиона на k. Тогда будет столько сортировок. Максимальная длина слова равна 96 символам. Нет сортировка сложности не «O(2N)», а именно 2N.

alexxisr 4 мар 2020 в 06:13

тогда что такое N?
количество слов? букв? бит? разрядность регистра в процессоре?

HabrArkady 4 мар 2020 в 06:26

N — это количество элементов массива, которые сортируются за каждый проход.

maxzhurkin 4 мар 2020 в 07:19

Тогда при чём тут буквы?

HabrArkady 4 мар 2020 в 07:53

В статье написано, что в сортировке были и латиница, и кириллица, и знаки препинания, и управляющие символы. Сортировать возможно все — абсолютно все. Главное, чтобы было задано правило сортировки, правило, по которому сортировать.

maxzhurkin 4 мар 2020 в 08:01

Но всё это не имеет никакого отношения к сложности алгоритма

HabrArkady 4 мар 2020 в 12:18

Да, не имеет. Я упоминул, что в сортировке есть и латиница, и кириллица, и знаки препинания, и управляющие символы, чтобы показать универсальность метода.

picul 4 мар 2020 в 19:43

Справедливости ради логарифм там ближе к двоичному чем к десятичному, но учитывая смысл O-нотации разницы нет.

PleaseKING 4 мар 2020 в 05:41

Ссылку бы на алгоритм… А так какой-то конь сферический. И еще бы описание методики измерения — как мерялось время? Как память? И уж вообще шикарно бы код выложить.

HabrArkady 4 мар 2020 в 06:07

К сожалению не все от меня зависит. Разрешили выложить только сравнительные результаты, которые приведены в таблицах.
Описание методики измерения времени — стандартное (код ниже)
start = clock();
программа сортировки (сначала одна, потом другая);
finish = clock();
duration = (double)(finish — start);
std::cout << "\n Время сортировки — ", std::cout << duration, std::cout << "\n";

PleaseKING 4 мар 2020 в 06:23

А сколько раз проверяли? А память как считали? А что с одинаковыми значениями? А сложность у вас наихудшая, средняя, ещё какая?

HabrArkady 4 мар 2020 в 06:39

Очень много раз прогонял. Память показана в «сеанс диагностики — память процессора».
В 7-ом тесте «Война и мир» представлена 4-ре раза, а весь текст дублирован дважды.

PleaseKING 4 мар 2020 в 06:59

Очень много — это сколько? 100, 1000, 100000, миллион,…? Вообще такие вещи делают в цикле сотни тысяч раз.

А что будет на уже отсортированном массиве? На отсортированном в обратную сторону? На случайном?

Память — обычно делают свой heap и считают, плюс максимальный размер стека...

fougasse 4 мар 2020 в 09:34

Такие вещи сначала в псевдокоде анализируют, как мне кажется.

remzalp 4 мар 2020 в 07:34

У нас есть такие ракеты… но мы вам о них не расскажем…

spirit1984 4 мар 2020 в 12:49

Не надо, а то сейчас еще автор мультфильм покажет, как его алгоритм быстро сортирует)

xkondorx 4 мар 2020 в 08:15

А какой смысл от статьи если она не раскрывает тему? Какая от алгоритма польза, если его нельзя применить даже теоретически потому, что применять нечего? Почитал коменты и ни в одном ответе не видел конкретики. Если нельзя выкладывать конкретику то и не нужна такая статья. Ну или напишите статью о методиках тестирования новых методов сортировок, от нее хоть польза будет.

НЛО прилетело и опубликовало эту надпись здесь

HabrArkady 4 мар 2020 в 06:33

Это сложность каждого прогона. Что значит худшего случая? Первоначальный массив — он абсолютно произвольный, никаким образом неупорядоченный, без каких-либо закономерностей — это худший случай?

НЛО прилетело и опубликовало эту надпись здесь

HabrArkady 4 мар 2020 в 06:48

Не знаю, меня это не очень интересует. Просто как происходит сортировка текста: сначала сортируется массив по 1-ому символу, затем данный массив разбивается на подмассивы, у которых 1-ая буква одинакова. После этого каждый подмассив сортируете заново. И так до последней буквы. И по этой же схеме работают все алгоритмы сортировки текста.

НЛО прилетело и опубликовало эту надпись здесь

HabrArkady 4 мар 2020 в 08:04

Умеет. Есть программа для сортировки чисел (в том числе десятичных, отрицательных). Возможна сортировка любых объектов, главное задать правило для сортировки.

НЛО прилетело и опубликовало эту надпись здесь

SquareRootOfZero 4 мар 2020 в 09:04

Это, скорее, либо поразрядная сортировка (англ. radix sort, в комментах ниже упомянутый), либо блочная сортировка (англ. bucket sort). Они бывают вполне себе линейны (O(N)), но не для произвольных данных, а только для «подходящих» (например, много-много объектов, среди которых много-много повторов, или значения ограничены узкими рамками, и т. п.) Разницы между O(2n) и O(kn) тут не будет, потому что k не зависит от объёма данных (т. е. оба варианта сводятся к O(n)). Вполне себе тема, но если автор(ы) претендуют на универсальность алгоритма, то хотя бы результаты тестов надо было привести на разных типах данных, а не только на строках. А если авторы изобрели более эффективный алгоритм именно для сортировки строк (либо какого-то класса объектов со сходными ограничениями), то и сравнивать надо не с универсальными quicksort/mergesort из std::sort(), а со специализированными функциями сортировки строк.

НЛО прилетело и опубликовало эту надпись здесь

SquareRootOfZero 4 мар 2020 в 10:18

Так а что он там раскрыл? Его комментарий, на который вы отвечали — это вольная цитата из статьи в Википедии «Алгоритм сортировки», раздел «Сортировка строк». Это radix+bucket, где вы там увидали «вариацию QuickSort»?

alexxz 4 мар 2020 в 08:56

Судя по описанию, вы изобрели Поразрядную сортировку или Radix sort. (https://ru.m.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80%D1%8F%D0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0) И да, она хорошо работает в задаче о сортировке слов.

HabrArkady 4 мар 2020 в 11:17

В Visual Studio используется, по моим данным, сортировка TimSort. Там та самая схема сортировки: первоначально сортируются все слова по первой букве, далее выбираются все слова с одинаковой первой буквой и начинают их сортировать по второй букве и т.д. Это стандартная схема сортировки текстовых данных на современном этапе хоть в python, хоть в java. Она никак не связана с Поразрядной сортировкой или Radix-сортировкой.

JekaMas 4 мар 2020 в 11:31

Вики говорит, что TimSoft заточен под случаи, когда у нас нередки упорядоченные или частично упорядоченные подмассивы и что это сочетание сортировок слиянием и вставкой. В описании алгоритма приводится всё по шагам. Выглядит, как оптимизированный под конкретные случаи merge sort.
Ничего о сортировке по первой букве, затем по второй не увидел https://ru.m.wikipedia.org/wiki/Timsort
Да и доступная визуализация алгоритма это показывает.

Признаться, я не понимаю, что вы говорите.

HabrArkady 4 мар 2020 в 12:01

У нас массив, например, 50 слов, который необходимо отсортировать. Сортируем данный массив, в результате получаем: первые 10 слов начинаются, пускай, на букву «в», далее 14 слов — на букву «к», далее 8 слов на букву «c», и т.д. Отсортировав данный массив, переходим к следующему этапу: берем первые 10 слов и начинаем сортировать их по 2-ой букве, которые в свою очередь разбиваются на подмассивы, которые в свою очередь будут упорядочены. Получим, например, 4-ре слова вторая буква — «а», 4-ре слова вторая буква «е» и оставшиеся 2 слова — вторая буква «с». Далее берем 4-ре слова, начинающиеся на «ва» и сортируем их. И так далее, до последней буквы. Далее сортируем слова, начинающиеся на «ве», и также до последней буквы. Далее сортируем слова, начинающиеся на «вс», и также до последней буквы. После этого возвращаемся к 14 словам начинающимся на букву «к». И также по описанной выше схеме. Эта схема не привязана к какому-либо методу сортировки, она общая для текстовой сортировки. По данной схеме сортируются все тексты, независимо от того как сортировать, хоть TimSort, хоть пузырком или как там еще.

JekaMas 4 мар 2020 в 12:09

TimSort описан иначе. По вашей схеме у вас будет M подмассивов, где M зависит от N, и каждый подмассивов будет сортироваться столько раз, сколько букв в самом длинном слове. Если сложность одной сортировки по одной букве N, длина наибольшего слова K, то мы получим, O(N^2*K).
Товарищи по цеху, если я ошибаюсь, то поправите мою оценку описанного алгоритма.

HabrArkady 4 мар 2020 в 12:38

Данная схема — это не сортировка TimSort. TimSort можно применять, когда сортируете 50 слов, или 10 слов, или 14 слов и на каждом этапе в отдельности. По данной схеме просто происходит сортировка текстовой информации. Вместо TimSort-а можно использовать любой другой метод на каждом этапе. По поводу сложности O(N^2*K). Данная сложность справедлива, если мы используем метод сложности O(N^2) и все слова выравниваем по длине максимального слова. Реально, если мы используем метод сложности O(N^2), то, для нашего примера, — O(50^2) + O(10^2) + O(14^2) +…. Но O(50^2) больше всего остального, поэтому сложность считается, как O(50^2).

JekaMas 4 мар 2020 в 12:41

Можно не писать штуки вроде O от конкретного числа?

HabrArkady 4 мар 2020 в 12:49

Это не я написал, как Вы выразились шутку, O(2N). Я говорю, именно, об 2*N.

JekaMas 4 мар 2020 в 12:58

То есть у вас время всегда с одним и тем же коэффициентом, вы это имеете в виду? Ну ок, тогда O(N)

JekaMas 4 мар 2020 в 12:44

Я вам написал, что такая оценка получается при использовании алгоритма сортировки O(N).
Если взять O(nlog(n)), то в итоге получится O(N^2log(N)*K)

lair 4 мар 2020 в 12:19

Это стандартная схема сортировки текстовых данных на современном этапе хоть в python, хоть в java.

Какой конкретно способ сортировки вы называете "стандартной схемой сортировки текстовых данных в python"? Приведите конкретную функцию.

bay73 4 мар 2020 в 07:09

У "прогонов" сложности не бывает. У них только время выполнения бывает. Сложность бывает у алгоритмов. И у алгоритмов она бывает разной (амортизированная, средняя, для худшего случая и т.п.)

НЛО прилетело и опубликовало эту надпись здесь

dmitryredkin 4 мар 2020 в 08:43

Уважаемый, ну вам же уже ответили. Я попытаюсь вас просветить. Математически доказано, что невозможно построить алгоритм, который бы мог отсортировать ЛЮБЫЕ данные быстрее, чем O(N log N).
Т.е. ваше утверждение, что ваш алгоритм бытрее std:sort на ЛЮБЫХ данных — некорректен. СУЩЕСТВУЕТ контрпример, на которм стандартный алгоритм будет быстрее.
Увы, без деталей реализации невозможно такой контрпример найти.
Существует МАССА алгоритмов, которые быстрее стандратного на определенном типе данных. Ваш — один из них.
Поймите, интерес к деталям обусловлен не желанием украсть вашу коммерческую тайну, а просто мы пытаемся подтолкнуть вас к осознанию положения вещей.

OldFisher 4 мар 2020 в 09:13

Строго говоря — невозможно при наличии определённых ограничений («in-place» и всё такое). Так-то всякие зануды и буквоеды легко могут предъявить counting sort, который работает за O(N) в лучшем и худшем случаях.

alexdesyatnik 4 мар 2020 в 11:43

Там только одно ограничение: при сортировке используется сравнение объектов между собой. Counting sort, radix sort и прочие объекты между собой не сравнивают, потому и линеарифмическая нижняя граница на них не распространяется.

dmitryredkin 4 мар 2020 в 11:55

Но чуда все равно не будет. Даже если не называть эти опреации сравнением, всё равно в реальной релизации БУДУТ примеры, когда специализированные алгоритмы будут медленнее универсального.

alexxisr 4 мар 2020 в 12:29

нет — берем массив и раскладываем элементы из него в другой массив по индексу равному элементу — получаем упорядоченный массив за линейное время (может быть еще раз пройтись чтобы убрать неиспользуемые места)
— ни одного сравнения, но нужно очень много памяти.

adictive_max 4 мар 2020 в 12:40

— ни одного сравнения, но нужно очень много памяти.

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

dmitryredkin 13 мар 2020 в 18:58

Нет, не получится. Контрпример:
Берем массив [0, MAXINT_64], и сортируем вашим алгоритмом.
Вам понадобится MAXINT_64 сравнений, чтобы пройти по «отсортированной» памяти и найти все (2) вставленных значения, а классическому алгоритму будет достаточно 1-го сравнения.

cadovvl 4 мар 2020 в 11:49

А вы слышали про SleepSort? Она вообще за один проход сортирует.

dmitryredkin 4 мар 2020 в 08:56

Что значит худшего случая?

Без деталей алгоритма не скажешь. Где-то — полностью отсортированный массив. Где-то — отсортированный задом наперед. Где-то — полностью случайные данные. Где-то — массив, состоящий из одного значения элементов…

HabrArkady 4 мар 2020 в 11:26

Я же указал, что было первоначальными массивами. Какая закономерность есть в «Войне и мире», в «Тихом Доме» и в остальных произведениях. Это абсолютно случайные данные, без каких-либо закономерностей. Разве, что в 3-ем и 7-ом тестах: вторая часть полностью повторяет первую. Но поверьте: данная закономерность нигде не используется. В остальных тестах даже такой закономерности нет.

dmitryredkin 4 мар 2020 в 11:57

Вот видите, вы уже сузили рамки своего алгоритма до «сортировка слов, слов много разных, они распеределены по определённому закону».
На таких данных ваш алгоритм вполне может показывать линейную зависимость.
Только именно это и надо указывать в заголовке.

HabrArkady 4 мар 2020 в 12:58

Ну по какому закону они распределены, где я об этом говорил или как-то там еще упоминал.

fougasse 4 мар 2020 в 14:49

По равномерному? Опровергайте.

HabrArkady 4 мар 2020 в 15:21

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

fougasse 4 мар 2020 в 17:27

А доказать сможете, что оно равномерное, распределение?

fougasse 4 мар 2020 в 09:35

Вы, случайно, с любителем анимированных флагов и определителем случайностей не знакомы?

ktotaika 4 мар 2020 в 12:44

Сначала подумала, что это просто весна, но открыла профиль, и, вот это да, очередной повелитель brand new сортировок, приглашенный valemak'ом.
Хмммммм… *подозрительно щурится*

fougasse 4 мар 2020 в 14:42

Я даже в профиль не смотрел, а оказалось, что товарищ valemak очередного гения призвал.
Интересно услышать мотивацию, т.к. один раз ещё можно поверить в случайность, но второй подряд срыватель покровов.
Подозрительно, очень подозрительно.

ktotaika 4 мар 2020 в 14:46

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

fougasse 4 мар 2020 в 14:49

Ясно.
Интересно, что товарищам кто-то довольно кучно ставит плюсики, что уже ставит под сомнение игнорирование их судеб «полноправными» пользователями.

DaylightIsBurning 4 мар 2020 в 11:51

Я построил самый быстрый самолёт!
А какую скорость замеряли: взлета, посадки, загрузки, максимальную полетную, воздушную (калиброванную, истинную, эквивалентную), путевую, сваливания, крейсерскую или другую какую может?
А что такое скорость?

warmbellycat 5 мар 2020 в 12:31

Хм…
Допустим у нас есть некий алгоритм, реализован в виде функции, на вход которой приходит массив. Внутри этой функции есть 3 невложенных foreach:

someFunction(someArray) {

 foreach(someArray){

 }

 foreach(someArray){

 }

 foreach(someArray){

 }

 return someResult

}

Какова сложность данного алгоритма в big-O нотации?
Внутри циклов нет других циклов.
А у такого варианта какова сложность:

someFunction(someArray) {

 foreach(someArray){

 foreach(someArray){

 foreach(someArray){

 }

 }

 }

 return someResult

}

alexdesyatnik 4 мар 2020 в 06:29

Очередной вечный двигатель? Алгоритмы сортировки, основанные на сравнении, в принципе не могут быть лучше O(N log N), это достаточно легко доказывается математически.

НЛО прилетело и опубликовало эту надпись здесь

HabrArkady 4 мар 2020 в 06:56

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

bay73 4 мар 2020 в 07:07

У нас есть эликсир жизни, но мы вам его не покажем. Просто поверьте на слово.

alexdesyatnik 4 мар 2020 в 07:09

Если изобрели что-то вроде radix-сортировки для строк, сравнивать «другой подход» с сортировкой сравнениями (будь то std::sort или что-то ещё) некорректно и неинтересно.

Roman_Cherkasov 4 мар 2020 в 06:31

А если не сложно, объясните пожалуйста кто-нибудь, почему из серии тестов выбирается наименьшее значение? Почему не среднее?

HabrArkady 4 мар 2020 в 06:51

Если выбирать среднее или максимальное, тогда в 8 столбце значения получаются не 15%, а значительно больше

НЛО прилетело и опубликовало эту надпись здесь

remzalp 4 мар 2020 в 07:40

Вот только распределение будет разным. Слова, если брать русский — очень много слов, начинающихся менее чем с 30 строчных букв (за минусом йыьъ), это уже 5 бит сравнения в самом частом случае, плюс довольно мало слов с заглавных. В случае с числами — много чисел, у которых первый байт в диапазоне от 0 до 255, что как бы уже вынуждает сравнивать 8 бит для каждого байта. В некоторых реализациях это способно хорошо ускорить процесс.

НЛО прилетело и опубликовало эту надпись здесь

remzalp 4 мар 2020 в 08:21

Да даже недавние бенчмарки реализации wc на хаскелле —
habr.com/ru/post/489958
на «хороших» данных работает лучше всех, на случайных данных — уже не так уж и экстремально быстро.

На данный момент как раз почему-то в качестве набора данных для сортировки использован естественный текст. Причина?

remzalp 4 мар 2020 в 07:44

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

В итоге он реализовал немного допиленный arm qemu, который логирует в файл выполняемые инструкции в процессе работы программы. Почему ARM? бОльшая линейность и зависимость только от оптимизации компилятора, а не особенности предсказания ветвлений.

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

powerman 4 мар 2020 в 07:50

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

remzalp 4 мар 2020 в 08:25

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

Зато подсчет инструкций позволяет в один проход получить повторяемый результат, а не гонять набор тестов, прогревая процессорный кэш, дисковый кэш и потом занимаясь статистикой — минимальное время взять? среднее? медиану?

Здесь бенчмарк достаточно запустить один раз и все случайные факторы просто не оказывают влияние. Да, не нравится ограниченность именно RISC архитектурой, но…

Ogra 4 мар 2020 в 10:19

А вот на x86 нет смысла считать процессорные инструкции. Предсказание ветвлений и кэш дают огромный прирост в скорости, игнорировать его нельзя. Александреску рассказывал об этом, с примерами, когда «теоретически» более быстрый код с меньшим числом сравнений и инструкций выполняется медленнее, чем код с большим числом.

НЛО прилетело и опубликовало эту надпись здесь

remzalp 4 мар 2020 в 08:50

Ну, условия достаточные для повторения результатов — конкретная версия поставляется с конкретным компилятором и в комплекте идут вполне себе конкретные библиотеки.

НЛО прилетело и опубликовало эту надпись здесь

Cykooz 4 мар 2020 в 09:39

Предлагаю автору сравнить свой алгоритм сортировки ещё с Intellij Idea, Eclipse, Vim, Emacs (функция M-x::sort-lines) и обязательно с «Microsoft Notepad».

nickavery 4 мар 2020 в 08:39

Судя по всему, мы наблюдаем результат лабораторной работы по алгоритмам и структурам данных. Был изобретен my_radix_sort.

alexxz 4 мар 2020 в 08:51

Уважаемый автор, вы предлагаете читателям судить ниочём. Нет ни алгориитма, ни описания его работы, ни упоминания на каком оборудовании проводились ваши опыты. Также видно, что для оценки сложности вы не использовали стандартных инструментов оценки сложности (нотация О большое для классов функций). Ознакомьте нас хотя бы с оценкой сложности алгоритма std:sort в вашей системе.

lair 4 мар 2020 в 11:45

Недавно был разработан алгоритм быстрой сортировки, сложность которого определяется как 2*N (2 умножить на N).

Простой вопрос: это алгоритм общего назначения или специализированный?

cadovvl 4 мар 2020 в 11:46

Я так понял, это новый уровень троллинга? Ну, что сортировка, которая умеет только сравнивать элементы, не может иметь сложность лучше O(N*log(N)) — это бог с ним, не будем догматиками. Но мы всерьез должны обсуждать тезис «у меня есть мифический алгоритм, существование которого не доказано, но вы должны в него верить, а, чтоб вам лучше верилость, я покажу вам табличку, красиво оформленную в Excel»? Как давно Хабр стал религиозным сайтом?

kinall 4 мар 2020 в 12:13

А внутре у него, сталбыть, неонка?

fireSparrow 4 мар 2020 в 13:32

Нейронка.

spirit1984 4 мар 2020 в 12:51

А все-таки, почему сведения о таком фундаментальном прорыве в теории алгоритмов сортировки вдруг публикуются не в каком-то уважаемом научном издании, а на Хабре, который вполне себе приличный сайт, но явно не то место, куда изначально отправляют такие разработки?)

Ogra 4 мар 2020 в 12:56

А где здесь прорыв? Алгоритмы сортировки с O(N) известны и используются.
То, что radix sort лучше подходит для сортировки строк, чем сортировки сравнениями — тоже не новость. В особо секретных документах даже можно найти, почему так происходит ;)

spirit1984 4 мар 2020 в 12:53

Напомнило)

valemak 4 мар 2020 в 12:55

Спасибо Бабушкину, что он подмышки бреет :-)

yleo 4 мар 2020 в 13:28

Если я правильно предполагаю, то автор пишет про "Сортировку Таноса" (автор называл её "Русской сортировку половинками", но я категорически против использования такого названия), которая является ~~велосипедом~~ вариантом QuickSort. Видимо по некомпетентности valemak не распознал велосипед и написал вышеупомянутую статью (ничего страшного, бывает).

Однако, дальше хуже:

valemak пригласил на Хабр пользователя Danilin78 (автор упомянутой сортировки), который умудрился отличится двумя вариантами своей статьи (1, 2) получившими недвусмысленную оценку "бред" и т.п.
Теперь valemak пригласил пользователя HabrArkady, который написал обсуждаемую статью о "вновь разработанном алгоритме сортировки", демонстрируя элементарное незнание темы, без описания алгоритма и/или демонстрации исходного кода, неся откровенную пургу в комментариях и т.д и т.п.

Поэтому у меня вопрос к valemak: кто все эти люди и что вы там все употребляете?

valemak 4 мар 2020 в 13:33

Прошу не забывать, что Владимир Рыбинкин (автор «сортировки воронкой») также был дважды приглашён по моим инвайтам.

fireSparrow 4 мар 2020 в 13:34

У вас там какая-то секта?

valemak 4 мар 2020 в 13:45

Всё объясняется достаточно просто.

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

Мне иногда пишут авторы собственных наработок, просят дать инвайт. Как правило, даю :-) За саморегулирующийся Хабр не переживаю. Также осмелюсь заметить, что в комментариях обсуждения статей моих «крестников» всегда получаются бурными и доставляющими :-)

yleo 4 мар 2020 в 13:44

Ну так и что в итоге с "сортировкой воронкой"?

Если дадите ссылку на исходный код референстной или оптимизированной реализации, то обещаю выложить результаты тестов с исходниками.

valemak 4 мар 2020 в 13:54

Не в курсе, это к Рыбинкину (попробуйте ему написать на емайл). У меня так и не дошли руки как следует вникнуть в его алгоритм и сделать анимацию — но когда-нибудь реализация и этой сортировки пополнит мою коллекцию :-)

michael_v89 4 мар 2020 в 22:44

Это модифицированная сортировка слиянием. Используется linked list.
Есть текущий подмассив, изначально пустой. Идем по исходному массиву, который сортируем.
Первый элемент просто добавляем в подмассив, следующие сравниваем с головой и хвостом подмассива, если меньше головы добавляем в голову, если больше хвоста добавляем в хвост. Для добавления в голову и нужен linked list, иначе придется сдвигать все элементы. Хотя наверно можно заменить его на массив в 2 раза больше исходного.
Если элемент находится между головой и хвостом, откладываем подмассив в буфер подмассивов, создаем новый пустой подмассив, добавляем туда.
После прохода по исходному массиву есть некоторое количество отсортированных подмассивов. Мержим их попарно, всегда берем самые минимальные по длине. Можно либо отсортировать по длине другим алгоритмом (автор предлагал пузырек), либо поддерживать отсортированность при добавлении. Но после каждого слияния длина результирующего массива меняется, надо это учитывать.
Изначально у автора было несколько рабочих подмассивов, они получаются каждый следующий короче предыдущего, поэтому он назвал алгоритм "сортировка воронкой". Для произвольных данных число сравнений в этом случае увеличивается, поэтому он сделал один подмассив, а название оставил.

В TimSort тоже есть определение отсортированных подмассивов (run), там они определяются в самом массиве, сравнение происходит с предыдущим элементом. В реализации MergeSort это тоже иногда добавляют, сам алгоритм от этого не меняется. Соответственно, от такого модифицированного MergeSort сортировка воронкой отличается только дополнительным сравнением с головой текущего run. Она значительно лучше работает на данных, специально для нее подходящих (2, 8, 2, 8, 1, 9, ...), на всех остальных работает чуть хуже, так как часто происходят 2 сравнения и потом все равно создание нового подмассива из одного элемента вместо одного сравнения на элемент для первоначального разбиения в модифицированном MergeSort. Может быть некоторый выигрыш от того, что мержатся минимальные подмассивы, а не соседние, но в TimSort это обрабатывается лучше.

В обычном MergeSort для первоначального разбиения будет ноль сравнений, так как просто всегда берется подмассив из 1 элемента, но в большинстве случаев это увеличивает число сравнений при слиянии. Для полностью случайных данных обычный MergeSort будет чуть лучше модифицированного (на N/2 сравнений), что заметно на небольших массивах. Для всех остальных случаев будет лучше модифицированный MergeSort или TimSort. Сортировка воронкой подходит для очень узкого круга вариантов.

yleo 4 мар 2020 в 22:51

Спасибо.

HabrArkady 4 мар 2020 в 13:48

Нет, я не пишу про сортировку Таноса, с ней ничего общего нет и в помине. Это сначала. Во-вторых, не трогайте Valemak. В-третьих, для того, чтобы о чем-то рассуждать, надо знать, о чем рассуждаешь. В статье, самое главное, это результаты тестирования, приведенные в таблицах. Все остальное — это общие рассуждения, помогающие что-то понять, чтобы меньше задавать вопросов. Самый главный результат — это то, что по новому алгоритму, выигрыш по быстродействию более 15%, а по затратам на память — практически двукратный. И чем больше объем сортируемой информации, тем более стремительный выигрыш мы будем иметь.
И, наконец, если очень хочется ругаться, то пришли e-mail. Поругаемся. А хамить здесь, не надо!!!

lair 4 мар 2020 в 13:52

Самый главный результат — это то, что по новому алгоритму, выигрыш по быстродействию более 15%, а по затратам на память — практически двукратный.

… по сравнению с чем?

(это просто к разговору "надо знать, о чем рассуждаешь")

HabrArkady 4 мар 2020 в 13:57

По сравнению с функцией std::sort, используемой в Visual Studio 2017. По-моему, как в таблицах, так и в текстах об этом не единожды об этом упоминается.

lair 4 мар 2020 в 14:01

std::sort — функция сортировки общего назначения (она работает для любых элементов, для которых определено отношение "элемент a идет раньше элемента b"). Ваша сортировка является сортировкой общего назначения?

HabrArkady 4 мар 2020 в 14:08

Да, этой сортировкой можно, сортировать все. Там нет привязки, к чему-либо. Я об этом уже писал не единожды.

lair 4 мар 2020 в 14:10

Да, этой сортировкой можно, сортировать все.

Покажите результаты сравнения (и код бенчмарка) для сравнения объектов с интерфейсом a.GoesBefore(b). Или опишите, каким образом ваш алгоритм работает для таких объектов.

DaylightIsBurning 4 мар 2020 в 14:26

Не верим! Это примерно то же самое, что сказать что Вы придумали вечный двигатель. Если Вы несогласны, то продемонстрируйте пожалуйста результаты релевантных тестов, а не что-то левое, что вы показали в статье.

HabrArkady 4 мар 2020 в 15:36

Что значит _релевантных_ тестов, и почему Вы решили, что данные тесты — это что-то левое.

lair 4 мар 2020 в 16:14

Потому что в этих тестах используются строки (для которых известен алгоритм сортировки со сложностью O(n)), а не элементы, для которых определена только операция сравнения (и для которых доказана невозможность сортировки со сложностью быстрее O(n log n)). Без демонстрации на операциях сравнения ваше утверждение о том, что ваша сортировка универсальна, бездоказательно.

yleo 4 мар 2020 в 16:53

Если ваш алгоритм требует определения для элементов больше отношения "a < b", то мерятся скоростью следует не c std::sort (универсальной сортировкой), а чем-то менее универсальным. В этом случае рекомендую этот пост — там Travis Downs ничего нового не придумал, но итеративно с ~~танцами и песнями~~ пояснениями и иллюстрациями дошел до хороших показателей для radixsort. Соответственно, хотелось-бы увидеть сопоставление результатов с вашим алгоритмом.

Кроме этого, при сравнении с std::sort следует измерять результаты для разных случаев (с разным распределением и упорядочиванием) исходных данных. В качестве заготовки могу предложить более-менее приемлемый тест и показать результаты (на всякий — сам тест критиковать не стоит, а просто сделать лучше/правильно и опубликовать).

yleo 4 мар 2020 в 17:31

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

yleo 7 мар 2020 в 13:33

HabrArkady, вы покажите результаты stresstest с вашим алгоритмом или не намерены этого делать?

HabrArkady 7 мар 2020 в 15:12

Разъясните, пожалуйста, что Вы хотите, чтобы я сделал более подробно. Какие тесты я должен сделать.

yleo 7 мар 2020 в 16:47

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

Клонировать git-репозиторий https://github.com/erthink/sort;
Для проверки собрать проект посредством CMake и запустить runme;
Добавить вашу реализацию сортировки по аналогии добавления radixsort;
Запустить runme и показать результаты.

Для информации:

это простейший бенчмарк сортировок сделанный сотрудником google ~10 лет назад.
я добавил несколько сценариев распределения данных (для оценки скорости yysort-сортировки сделанной для libmdbx.
только-что добавил сборку посредством CMake и упомянутую ранее реализацию radixsort.

Пример результатов

Running tests with random:
extra.h yysort1_int64         - ok,   822818.0 usec
extra.h yysort2_int64         - ok,   854933.0 usec
extra.h sort_rela589n_int64   - ok,  1576849.0 usec
extra.h radix_sort7_int64     - ok,   185674.0 usec
sort.h tim_sort               - ok,  1402058.0 usec
sort.h quick_sort             - ok,  1077905.0 usec
extra.h std_sort_int64        - ok,  1009962.0 usec
extra.h std_stable_int64      - ok,  1059595.0 usec
sort.h heap_sort              - ok,  1102937.0 usec
sort.h merge_sort             - ok,  1421193.0 usec
sort.h shell_sort             - ok,  1862364.0 usec
sort.h merge_sort_in_place    - ok,  1246581.0 usec
sort.h grail_sort             - ok,  1699774.0 usec
sort.h sqrt_sort              - ok,  1455058.0 usec
stdlib qsort                  - ok,  1927199.0 usec
-------
Running tests with random 50% duplicates:
extra.h yysort1_int64         - ok,   810166.0 usec
extra.h yysort2_int64         - ok,   849615.0 usec
extra.h sort_rela589n_int64   - ok,  1572379.0 usec
extra.h radix_sort7_int64     - ok,   212029.0 usec
sort.h tim_sort               - ok,  1398433.0 usec
sort.h quick_sort             - ok,  1088323.0 usec
extra.h std_sort_int64        - ok,  1065503.0 usec
extra.h std_stable_int64      - ok,  1071353.0 usec
sort.h heap_sort              - ok,  1093484.0 usec
sort.h merge_sort             - ok,  1415888.0 usec
sort.h shell_sort             - ok,  1838834.0 usec
sort.h merge_sort_in_place    - ok,  1253441.0 usec
sort.h grail_sort             - ok,  1693643.0 usec
sort.h sqrt_sort              - ok,  1453816.0 usec
stdlib qsort                  - ok,  1949698.0 usec
-------
Running tests with random two values:
extra.h yysort1_int64         - ok,   248878.0 usec
extra.h yysort2_int64         - ok,   122961.0 usec
extra.h sort_rela589n_int64   - ok, 89906420.0 usec
extra.h radix_sort7_int64     - ok,   145132.0 usec
sort.h tim_sort               - ok,   436794.0 usec
sort.h quick_sort             - ok,   112741.0 usec
extra.h std_sort_int64        - ok,   272012.0 usec
extra.h std_stable_int64      - ok,   309151.0 usec
sort.h heap_sort              - ok,   558226.0 usec
sort.h merge_sort             - ok,   492002.0 usec
sort.h shell_sort             - ok,   350249.0 usec
sort.h merge_sort_in_place    - ok,   364930.0 usec
sort.h grail_sort             - ok,   586547.0 usec
sort.h sqrt_sort              - ok,   552624.0 usec
stdlib qsort                  - ok,   772211.0 usec
-------
Running tests with random of 0..9:
extra.h yysort1_int64         - ok,   391730.0 usec
extra.h yysort2_int64         - ok,   301675.0 usec
extra.h sort_rela589n_int64   - ok,  7404398.0 usec
extra.h radix_sort7_int64     - ok,   133223.0 usec
sort.h tim_sort               - ok,   835698.0 usec
sort.h quick_sort             - ok,   272618.0 usec
extra.h std_sort_int64        - ok,   417282.0 usec
extra.h std_stable_int64      - ok,   547843.0 usec
sort.h heap_sort              - ok,   944833.0 usec
sort.h merge_sort             - ok,   796068.0 usec
sort.h shell_sort             - ok,   674562.0 usec
sort.h merge_sort_in_place    - ok,   678547.0 usec
sort.h grail_sort             - ok,  1639136.0 usec
sort.h sqrt_sort              - ok,   868220.0 usec
stdlib qsort                  - ok,  1242882.0 usec
-------
Running tests with mixed-pattern (1/2 sorted, 1/6 reverse, 1/3 random):
extra.h yysort1_int64         - ok,   613579.0 usec
extra.h yysort2_int64         - ok,   663289.0 usec
extra.h sort_rela589n_int64   - ok,   657258.0 usec
extra.h radix_sort7_int64     - ok,   183325.0 usec
sort.h tim_sort               - ok,   552537.0 usec
sort.h quick_sort             - ok,   838606.0 usec
extra.h std_sort_int64        - ok,   792180.0 usec
extra.h std_stable_int64      - ok,   525126.0 usec
sort.h heap_sort              - ok,  1032734.0 usec
sort.h merge_sort             - ok,   748048.0 usec
sort.h shell_sort             - ok,  1676758.0 usec
sort.h merge_sort_in_place    - ok,   586180.0 usec
sort.h grail_sort             - ok,   953395.0 usec
sort.h sqrt_sort              - ok,   772525.0 usec
stdlib qsort                  - ok,  1062228.0 usec
-------
Running tests with mixed-pattern 50% duplicates:
extra.h yysort1_int64         - ok,   609025.0 usec
extra.h yysort2_int64         - ok,   660484.0 usec
extra.h sort_rela589n_int64   - ok,   659025.0 usec
extra.h radix_sort7_int64     - ok,   225606.0 usec
sort.h tim_sort               - ok,   622718.0 usec
sort.h quick_sort             - ok,   824485.0 usec
extra.h std_sort_int64        - ok,   788281.0 usec
extra.h std_stable_int64      - ok,   522923.0 usec
sort.h heap_sort              - ok,  1031538.0 usec
sort.h merge_sort             - ok,   754849.0 usec
sort.h shell_sort             - ok,  1642628.0 usec
sort.h merge_sort_in_place    - ok,   590366.0 usec
sort.h grail_sort             - ok,   990525.0 usec
sort.h sqrt_sort              - ok,   774448.0 usec
stdlib qsort                  - ok,  1124386.0 usec
-------
Running tests with mixed-pattern two values:
extra.h yysort1_int64         - ok,   200132.0 usec
extra.h yysort2_int64         - ok,    83036.0 usec
extra.h sort_rela589n_int64   - ok, 67483405.0 usec
extra.h radix_sort7_int64     - ok,   140106.0 usec
sort.h tim_sort               - ok,   160123.0 usec
sort.h quick_sort             - ok,    97190.0 usec
extra.h std_sort_int64        - ok,   225158.0 usec
extra.h std_stable_int64      - ok,   205413.0 usec
sort.h heap_sort              - ok,   511215.0 usec
sort.h merge_sort             - ok,   356849.0 usec
sort.h shell_sort             - ok,   297061.0 usec
sort.h merge_sort_in_place    - ok,   162143.0 usec
sort.h grail_sort             - ok,   374851.0 usec
sort.h sqrt_sort              - ok,   409156.0 usec
stdlib qsort                  - ok,   566768.0 usec
-------
Running tests with mixed-pattern of 0..9:
extra.h yysort1_int64         - ok,   285522.0 usec
extra.h yysort2_int64         - ok,   203379.0 usec
extra.h sort_rela589n_int64   - ok,  3868783.0 usec
extra.h radix_sort7_int64     - ok,   134041.0 usec
sort.h tim_sort               - ok,   306421.0 usec
sort.h quick_sort             - ok,   184143.0 usec
extra.h std_sort_int64        - ok,   312547.0 usec
extra.h std_stable_int64      - ok,   295135.0 usec
sort.h heap_sort              - ok,   887521.0 usec
sort.h merge_sort             - ok,   465153.0 usec
sort.h shell_sort             - ok,   500991.0 usec
sort.h merge_sort_in_place    - ok,   304824.0 usec
sort.h grail_sort             - ok,   873295.0 usec
sort.h sqrt_sort              - ok,   540994.0 usec
stdlib qsort                  - ok,   746061.0 usec
-------
Running tests with sorted:
extra.h yysort1_int64         - ok,   106663.0 usec
extra.h yysort2_int64         - ok,    16666.0 usec
extra.h sort_rela589n_int64   - ok,    69891.0 usec
extra.h radix_sort7_int64     - ok,   251164.0 usec
sort.h tim_sort               - ok,    11735.0 usec
sort.h quick_sort             - ok,   251402.0 usec
extra.h std_sort_int64        - ok,   173910.0 usec
extra.h std_stable_int64      - ok,   143127.0 usec
sort.h heap_sort              - ok,   964730.0 usec
sort.h merge_sort             - ok,   282217.0 usec
sort.h shell_sort             - ok,   224989.0 usec
sort.h merge_sort_in_place    - ok,    24654.0 usec
sort.h grail_sort             - ok,   436444.0 usec
sort.h sqrt_sort              - ok,   283779.0 usec
stdlib qsort                  - ok,   456411.0 usec
-------
Running tests with sorted 93.75%:
extra.h yysort1_int64         - ok,   278289.0 usec
extra.h yysort2_int64         - ok,   289340.0 usec
extra.h sort_rela589n_int64   - ok,   655408.0 usec
extra.h radix_sort7_int64     - ok,   260584.0 usec
sort.h tim_sort               - ok,   468728.0 usec
sort.h quick_sort             - ok,   637118.0 usec
extra.h std_sort_int64        - ok,   329171.0 usec
extra.h std_stable_int64      - ok,   336014.0 usec
sort.h heap_sort              - ok,   984870.0 usec
sort.h merge_sort             - ok,   519161.0 usec
sort.h shell_sort             - ok,  1534410.0 usec
sort.h merge_sort_in_place    - ok,   518192.0 usec
sort.h grail_sort             - ok,   800571.0 usec
sort.h sqrt_sort              - ok,   661784.0 usec
stdlib qsort                  - ok,   888571.0 usec
-------
Running tests with reverse:
extra.h yysort1_int64         - ok,   181535.0 usec
extra.h yysort2_int64         - ok,   194451.0 usec
extra.h sort_rela589n_int64   - ok,    84785.0 usec
extra.h radix_sort7_int64     - ok,   256737.0 usec
sort.h tim_sort               - ok,    31284.0 usec
sort.h quick_sort             - ok,   301640.0 usec
extra.h std_sort_int64        - ok,   177571.0 usec
extra.h std_stable_int64      - ok,   197487.0 usec
sort.h heap_sort              - ok,   909687.0 usec
sort.h merge_sort             - ok,   382207.0 usec
sort.h shell_sort             - ok,   344173.0 usec
sort.h merge_sort_in_place    - ok,   281081.0 usec
sort.h grail_sort             - ok,   491918.0 usec
sort.h sqrt_sort              - ok,   333204.0 usec
stdlib qsort                  - ok,   511167.0 usec
-------
Running tests with 111......000:
extra.h yysort1_int64         - ok,   157486.0 usec
extra.h yysort2_int64         - ok,    20157.0 usec
extra.h sort_rela589n_int64   - ok, 89831003.0 usec
extra.h radix_sort7_int64     - ok,   138863.0 usec
sort.h tim_sort               - ok,    16507.0 usec
sort.h quick_sort             - ok,    43632.0 usec
extra.h std_sort_int64        - ok,   183356.0 usec
extra.h std_stable_int64      - ok,   151969.0 usec
sort.h heap_sort              - ok,   476663.0 usec
sort.h merge_sort             - ok,   288034.0 usec
sort.h shell_sort             - ok,   236196.0 usec
sort.h merge_sort_in_place    - ok,    58724.0 usec
sort.h grail_sort             - ok,   248106.0 usec
sort.h sqrt_sort              - ok,   353212.0 usec
stdlib qsort                  - ok,   458765.0 usec
-------
Running tests with 999..., 888..., ..., ...000:
extra.h yysort1_int64         - ok,   149749.0 usec
extra.h yysort2_int64         - ok,    19980.0 usec
extra.h sort_rela589n_int64   - ok, 32356259.0 usec
extra.h radix_sort7_int64     - ok,   135767.0 usec
sort.h tim_sort               - ok,    32825.0 usec
sort.h quick_sort             - ok,    99056.0 usec
extra.h std_sort_int64        - ok,   175027.0 usec
extra.h std_stable_int64      - ok,   155548.0 usec
sort.h heap_sort              - ok,   820527.0 usec
sort.h merge_sort             - ok,   298793.0 usec
sort.h shell_sort             - ok,   254553.0 usec
sort.h merge_sort_in_place    - ok,   107271.0 usec
sort.h grail_sort             - ok,   429893.0 usec
sort.h sqrt_sort              - ok,   414603.0 usec
stdlib qsort                  - ok,   493637.0 usec
-------
Running tests with all same:
extra.h yysort1_int64         - ok,   166858.0 usec
extra.h yysort2_int64         - ok,    21707.0 usec
extra.h sort_rela589n_int64   - ok,    69098.0 usec
extra.h radix_sort7_int64     - ok,   113107.0 usec
sort.h tim_sort               - ok,    12040.0 usec
sort.h quick_sort             - ok,    18011.0 usec
extra.h std_sort_int64        - ok,   186969.0 usec
extra.h std_stable_int64      - ok,   141784.0 usec
sort.h heap_sort              - ok,    66827.0 usec
sort.h merge_sort             - ok,   287558.0 usec
sort.h shell_sort             - ok,   225105.0 usec
sort.h merge_sort_in_place    - ok,    24957.0 usec
sort.h grail_sort             - ok,   199244.0 usec
sort.h sqrt_sort              - ok,   295538.0 usec
stdlib qsort                  - ok,   437948.0 usec
-------
Running tests with sorted blocks of length 10:
extra.h yysort1_int64         - ok,   780905.0 usec
extra.h yysort2_int64         - ok,   817650.0 usec
extra.h sort_rela589n_int64   - ok,  1581537.0 usec
extra.h radix_sort7_int64     - ok,   182992.0 usec
sort.h tim_sort               - ok,  1293210.0 usec
sort.h quick_sort             - ok,  1029897.0 usec
extra.h std_sort_int64        - ok,   973319.0 usec
extra.h std_stable_int64      - ok,   924195.0 usec
sort.h heap_sort              - ok,  1078477.0 usec
sort.h merge_sort             - ok,  1267130.0 usec
sort.h shell_sort             - ok,  1723112.0 usec
sort.h merge_sort_in_place    - ok,  1112339.0 usec
sort.h grail_sort             - ok,  1576277.0 usec
sort.h sqrt_sort              - ok,  1324452.0 usec
stdlib qsort                  - ok,  1722064.0 usec
-------
Running tests with sorted blocks of length 100:
extra.h yysort1_int64         - ok,   653574.0 usec
extra.h yysort2_int64         - ok,   689053.0 usec
extra.h sort_rela589n_int64   - ok,  1564217.0 usec
extra.h radix_sort7_int64     - ok,   182998.0 usec
sort.h tim_sort               - ok,   675106.0 usec
sort.h quick_sort             - ok,   906428.0 usec
extra.h std_sort_int64        - ok,   832817.0 usec
extra.h std_stable_int64      - ok,   682833.0 usec
sort.h heap_sort              - ok,  1047375.0 usec
sort.h merge_sort             - ok,   933192.0 usec
sort.h shell_sort             - ok,  1457265.0 usec
sort.h merge_sort_in_place    - ok,   889346.0 usec
sort.h grail_sort             - ok,  1296572.0 usec
sort.h sqrt_sort              - ok,  1058781.0 usec
stdlib qsort                  - ok,  1352663.0 usec
-------
Running tests with sorted blocks of length 10000:
extra.h yysort1_int64         - ok,   324255.0 usec
extra.h yysort2_int64         - ok,   376492.0 usec
extra.h sort_rela589n_int64   - ok,   284086.0 usec
extra.h radix_sort7_int64     - ok,   184740.0 usec
sort.h tim_sort               - ok,   124746.0 usec
sort.h quick_sort             - ok,   625609.0 usec
extra.h std_sort_int64        - ok,   491734.0 usec
extra.h std_stable_int64      - ok,   250881.0 usec
sort.h heap_sort              - ok,   986073.0 usec
sort.h merge_sort             - ok,   393951.0 usec
sort.h shell_sort             - ok,   551140.0 usec
sort.h merge_sort_in_place    - ok,   322268.0 usec
sort.h grail_sort             - ok,   652629.0 usec
sort.h sqrt_sort              - ok,   465226.0 usec
stdlib qsort                  - ok,   638257.0 usec
-------
Running tests with swapped size/2 pairs:
extra.h yysort1_int64         - ok,   713246.0 usec
extra.h yysort2_int64         - ok,   747018.0 usec
extra.h sort_rela589n_int64   - ok,  1508257.0 usec
extra.h radix_sort7_int64     - ok,   265747.0 usec
sort.h tim_sort               - ok,  1176319.0 usec
sort.h quick_sort             - ok,   993433.0 usec
extra.h std_sort_int64        - ok,   852194.0 usec
extra.h std_stable_int64      - ok,   865713.0 usec
sort.h heap_sort              - ok,  1074433.0 usec
sort.h merge_sort             - ok,  1163080.0 usec
sort.h shell_sort             - ok,  1831217.0 usec
sort.h merge_sort_in_place    - ok,  1072136.0 usec
sort.h grail_sort             - ok,  1438544.0 usec
sort.h sqrt_sort              - ok,  1222052.0 usec
stdlib qsort                  - ok,  1635037.0 usec
-------
Running tests with swapped size/8 pairs:
extra.h yysort1_int64         - ok,   388071.0 usec
extra.h yysort2_int64         - ok,   415601.0 usec
extra.h sort_rela589n_int64   - ok,   920980.0 usec
extra.h radix_sort7_int64     - ok,   257616.0 usec
sort.h tim_sort               - ok,   657143.0 usec
sort.h quick_sort             - ok,   713389.0 usec
extra.h std_sort_int64        - ok,   451258.0 usec
extra.h std_stable_int64      - ok,   455000.0 usec
sort.h heap_sort              - ok,  1009091.0 usec
sort.h merge_sort             - ok,   667092.0 usec
sort.h shell_sort             - ok,  1659759.0 usec
sort.h merge_sort_in_place    - ok,   675202.0 usec
sort.h grail_sort             - ok,   947886.0 usec
sort.h sqrt_sort              - ok,   798388.0 usec
stdlib qsort                  - ok,  1060413.0 usec
-------
Running tests with known evil data (odd/even swap):
extra.h yysort1_int64         - ok,   106596.0 usec
extra.h yysort2_int64         - ok,   119683.0 usec
extra.h sort_rela589n_int64   - ok,    72005.0 usec
extra.h radix_sort7_int64     - ok,   247649.0 usec
sort.h tim_sort               - ok,    93710.0 usec
sort.h quick_sort             - ok,   280980.0 usec
extra.h std_sort_int64        - ok,   167934.0 usec
extra.h std_stable_int64      - ok,   163389.0 usec
sort.h heap_sort              - ok,   954945.0 usec
sort.h merge_sort             - ok,   312337.0 usec
sort.h shell_sort             - ok,   232719.0 usec
sort.h merge_sort_in_place    - ok,    21145.0 usec
sort.h grail_sort             - ok,   438797.0 usec
sort.h sqrt_sort              - ok,   285045.0 usec
stdlib qsort                  - ok,   507681.0 usec
-------
Running tests with known evil data (odd/even hi/low swap):
extra.h yysort1_int64         - ok,   113151.0 usec
extra.h yysort2_int64         - ok,    71402.0 usec
extra.h sort_rela589n_int64   - ok,   140752.0 usec
extra.h radix_sort7_int64     - ok,   244312.0 usec
sort.h tim_sort               - ok,   292957.0 usec
sort.h quick_sort             - ok,   494097.0 usec
extra.h std_sort_int64        - ok,   162164.0 usec
extra.h std_stable_int64      - ok,   196847.0 usec
sort.h heap_sort              - ok,   943394.0 usec
sort.h merge_sort             - ok,   387820.0 usec
sort.h shell_sort             - ok,   439202.0 usec
sort.h merge_sort_in_place    - ok,   365635.0 usec
sort.h grail_sort             - ok,   655214.0 usec
sort.h sqrt_sort              - ok,   426086.0 usec
stdlib qsort                  - ok,   669278.0 usec

В том числе, видно как ведет себя "новый метод сортировки массива" от rela589n.

cadovvl 9 мар 2020 в 11:56

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

yleo 9 мар 2020 в 16:53

Уж лучше так, чем "хакать" мозг окружающих ;)

spirit1984 4 мар 2020 в 19:50

Если этой сортировкой можно сортировать все, то откуда 2*N и как это стыкуется с теоремой о нижней оценке для сортировки сравнениями?

fougasse 4 мар 2020 в 22:49

Никаким.

HabrArkady 5 мар 2020 в 10:52

Данная сортировка не относится к классу сортировок посредством сравнений.

lair 5 мар 2020 в 11:09

Тогда каким образом вы с ее помощью сортируете объекты для которых определена только операция сравнения?

DaylightIsBurning 6 мар 2020 в 13:47

Тогда каким образом это соотносится с другим Вашим утверждением:

Да, этой сортировкой можно, сортировать все. Там нет привязки, к чему-либо.

HabrArkady 6 мар 2020 в 16:36

К чему вопрос? Как можно сортировать без сравнений? Разработан новый алгоритм, работающий по другим правилам. Можно сортировать текстовую информацию, целые и десятичные числа, положительные и отрицательные.

lair 6 мар 2020 в 16:43

К чему вопрос?

К тому, что ваше утверждение, что ваша сортировка универсальна — некорректно.

Можно сортировать текстовую информацию, целые и десятичные числа, положительные и отрицательные.

Но это не "все". Это текстовая информация, и некоторые виды чисел. У std::sort такого ограничения нет, и поэтому ваше сравнение некорректно.

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

lair 6 мар 2020 в 16:52

Можно сортировать текстовую информацию

О, кстати. Текстовую информацию, да. Любую?

Простой тест — вот есть три слова: linea, llamar, lonja. В каком порядке они будут после вашей сортировки?

HabrArkady 6 мар 2020 в 17:36

Если Вы работаете в кодировке ANSI и сортируете по возрастанию, то так и останется. Кода в кодировке ANSI: i-105, l-108, o-111. Первая буква «l» — у всех общая, поэтому сортироваться будет по 2-ой букве. Другие кодировки также работают.
И что подразумевается под «Любую?»?
К тому, что ваше утверждение, что ваша сортировка универсальна — некорректно. Почему? Я написал, что я могу сортировать текстовую информацию, целые и десятичные числа, положительные и отрицательные. Программа сортирует. После сортировки полностью, один в один, совпадает сортировкой, получаемой функцией std::sort.

lair 6 мар 2020 в 17:45

Если Вы работаете в кодировке ANSI и сортируете по возрастанию, то так и останется. Кода в кодировке ANSI: i-105, l-108, o-111. Первая буква «l» — у всех общая, поэтому сортироваться будет по 2-ой букве.

А это неправильно. Согласно правилам испанского языка (по-моему, в середине 90-х это отменили, правда, но не суть), должно быть вот так:

linea
lonja
llamar

А все потому, что ll — это диграф, на самом деле. И его нельзя сортировать просто по кодам в кодировке.

А если надо неотмененное правило, то пожалуйста: n ñ o, в Юникоде — 006E 00F1 006F.

И что подразумевается под «Любую?»?

А вот ровно пример выше: вы не смогли корректно отсортировать эту текстовую информацию.

Почему?

Потому что есть объекты, которые ваша сортировка сортировать не умеет.

Я написал, что я могу сортировать текстовую информацию, целые и десятичные числа, положительные и отрицательные.

Это называется "специализированная сортировка". Универсальная сортировка, по определению, та, которая умеет сортировать все, для чего определена операция сравнения.

Rsa97 7 мар 2020 в 14:02

Можно и в русском языке пример найти: e (U+0435) → ё (U+0451) → ж (U+0436)
И в немецком: ss → ß → st
И, подозреваю, в любом другом языке, в котором используются грависы, акуты, циркумфлексы и прочие седильи и лигатуры.

DaylightIsBurning 6 мар 2020 в 17:45

Как можно сортировать без сравнений?

ну вот же, например: radix sort, pigeonhole sort, counting sort. Эти сортировки имеют сложность худшего случая O(N), но у них у всех есть существенные ограничения, как и у Вашей. Вы же сами сказали, что Ваша сортировка «не относится к классу сортировок посредством сравнений». Зачем тогда спрашиваете?

Ogra 4 мар 2020 в 14:01

Функция std::sort является универсальной, ваша — специализированной для строк. Как ваш алгоритм ведет себя на сортировке чисел по сравнению с std::sort? Притом как целых, так и с плавающей запятой? Неизвестно.

HabrArkady 4 мар 2020 в 14:17

Пожалуйста, прочитайте комментарии. Я писал, уже, что она универсальна, на ней можно, и в том числе, числа (как десятичные, так и отрицательные).

Ogra 4 мар 2020 в 14:19

Э нет, так не пойдет, покажите результаты. Я не сомневаюсь в том, что это возможно, но я сомневаюсь, что вы сохраните 15% эффективности по сравнению с std::sort. Особенно в том, что касается чисел с плавающей запятой.

HabrArkady 4 мар 2020 в 14:59

15% — это реальные значения для текстовой информации, без всякого подгона, мухлежа. Для плавающей запятой сортировка также работает, но я не тестировал настолько, чтобы дать такую же информацию, как по текстовой.

DaylightIsBurning 4 мар 2020 в 16:24

Это 15% по сравнению с относительно медленным алгоритмом, а потому неинтересно. А на плавающей запятой стоило бы потестировать.

DaylightIsBurning 6 мар 2020 в 13:50

> без всякого подгона, мухлежа
Сознательного подгона и мухлежа. Подгон и мухлеж очень часто возникает в результате незнания, потому в университетах долго и сложно учат методикам проведения и анализа экспериментов, и годами два раза в неделю тренируют студентов практикумами, что бы они набрались опыта в этом деле. Правильные тесты — это сложно.

DreamChild 4 мар 2020 в 18:17

для того, чтобы о чем-то рассуждать, надо знать, о чем рассуждаешь

Вот-вот. Жаль, что вы сами не следуете этому принципу, путая IDE с языком программирования и не зная, как работает O-нотация (сложность 2*N)

JekaMas 4 мар 2020 в 14:01

Вы попали в точку, судя по ответам ниже.

dbalabanov 5 мар 2020 в 10:39

фух, теперь понятно, что это мне напомнило.

fougasse 4 мар 2020 в 17:34

-50 за 12 часов — хорошее достижение, не каждому дано, приглашенные прогрессируют.

spirit1984 4 мар 2020 в 17:50

Видимо, человек задался целью побить легендарные треды про BolgenOS

softaria 5 мар 2020 в 12:25

Непонятна цель написания этой статьи. Похвастаться тайным алгоритмом, который у вас есть?

cadovvl 5 мар 2020 в 12:55

Я проверил: ни одного комментария автора статьи без отрицательной оценки. Или флешмоб, или кому-то стоит подумать.

DaylightIsBurning 6 мар 2020 в 13:52

А с какими комментариями автора Вы согласны?

cadovvl 6 мар 2020 в 14:43

Откровенно говоря, я их даже не читал после второго. А имеет смысл?

НЛО прилетело и опубликовало эту надпись здесь

HabrArkady 15 мар 2020 в 11:29

Всем большое спасибо за интерес, проявленный к данной статье.
А как Вы отнесетесь, если я сообщу следующую информацию.

Я разработал алгоритм деления длинных чисел и написал программу на C++ в Visual Studio 2017. Также были проверены эти данные на MathLab, Java и других программах и языках.

Получил следующие результаты:
Разделил 100-значное десятичное число на 35-значное десятичное число в цикле 100 000 раз.
Время расчета на тестах (MathLab, Java и другие программы и языки) составляет — от 1/2 минуты и выше.
На моей программе рассчитывается на одном процессоре — 0,1 секунды.

Затем я разделил 225-значное десятичное число на 53-значное десятичное число в цикле 1 000 000 раз. На моей программе рассчитывается на одном процессоре – около 3 секунд.

yleo 15 мар 2020 в 17:53

Вы так и не показали воспроизводимых результатов оценки вашей сортировки. Инструкции вам были предложены неделю назад.
Закодируйте и покажите ваш "бенчмарк деления" на актуальной версии python (там внутри GMP) и ~~посмешите~~ порадуйте нас результатами.

Пока вы этого не сделаете на ваши придумки не рационально обращать внимание.

lair 15 мар 2020 в 17:53

А как Вы отнесетесь, если я сообщу следующую информацию.

Так же, как к тому, что вы написали в статье: как к ничем не подтвержденному заявлению.

michael_v89 15 мар 2020 в 18:04

А у меня есть алгоритм деления больших чисел, написанный на C лет 10 назад, я его запустил и получил следующие результаты.

Разделил 200-значное десятичное число на 73-значное десятичное число в цикле 100 000 раз.
На моей программе рассчитывается на одном процессоре — 0,07 секунды.

Затем я разделил 339-значное десятичное число на 117-значное десятичное число в цикле 1 000 000 раз.
На моей программе рассчитывается на одном процессоре – около 1 секунды.

LborV 20 мар 2020 в 15:55

Господа, не кажется ли вам что это школьник/школьники на информатике рандомно сделали прогу и под острыми впечатлениями решили писать сюда? Где судя по комментам были раздавлены в пух и прах)))

retar 25 апр 2023 в 09:46

Я сравнил алгоритмы сортировки Visual Studio 2017 std::sort, CLion std::sort, notepad++ std::sort, GoLand sort.strings(string) и алгоритм сортировки на 1С со сложностью O(1). Самым быстрым оказался алгоритм сортировки из Vim со сложностью O(надо было сделать еще вчера).

Присоединюсь к ораторам выше: что за алгоритм? что значит 2N? где код на гитхабе? Или это очередная секретная разработка ФСО совместно с ротой охраны штаба ЗВО?

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

О быстрой сортировке, сложности 2*N

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

Публикации

Истории