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

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

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

Всего голосов 17: ↑17 и ↓0+17
Я специально написал, что сложность 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.
Всего голосов 4: ↑0 и ↓4-4
Я поддерживаю вашу увлечённость алгоритмами и ни в коем случае не стремлюсь охладить ваш энтузиазм. Но если вы хотите чтобы ваш анализ воспринимали серьезно, желательно придерживаться строгой общепринятой терминологии. Если вы используете big-O нотацию, читателю сразу понятно что речь идёт об асимптотической сложности, которая растёт линейно с увеличением объема входных данных. Если вы пишете «сложность алгоритма 2*N», это можно интерпретировать как угодно. Есть хорошие причины почему в научных исследованиях пользуются строгими метриками, например системой СИ. Если бы в каждой статье по астрофизике использовались произвольные аршины и попугаи, сравнивать результаты было бы чрезвычайно сложно. И ваше пояснение про накладные расходы не делает картину более понятной.

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

Сам факт того что какой-то кастомный алгоритм сортировки для определенного типа данных может быть быстрее std::sort никого не удивит. std::sort это универсальный алгоритм основанный только на сравнениях, который не использует знания о типах данных никаким образом. Когда программист вызывает std::sort, он как бы говорит системе: интерпретируй мои данные как абстрактные ключи и используй operator< для их сравнения, я знаю что я делаю. Создатели stl не пытались предоставить наибыстрейший алгоритм сортировки для всех возможных типов данных.
Всего голосов 4: ↑4 и ↓0+4
Прекрасно знаю, что означает O(N).
С каждым элементом выполняются определенные действия. Это одно N.

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


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

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

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

Чтобы их сравнить нужно чтобы log(N) был как минимум на порядок больше двух.
Это речь о 10^20 строк. Как часто нам приходится сортировать такое количество данных? Не думаю что в реальном использовании этих алгоритмов можно почувствовать значительную разницу.
Всего голосов 14: ↑14 и ↓0+14
Четыре миллиона это только слова. Каждое слово состоит из букв. Сортировка полная, т.е. сортировка не только по первой букве, а по всем буквам. Если в среднем каждое состоит из, предположим, состоит k-букв, то нужно умножить 4 миллиона на k. Тогда будет столько сортировок. Максимальная длина слова равна 96 символам. Нет сортировка сложности не «O(2N)», а именно 2N.
Всего голосов 11: ↑3 и ↓8-5
тогда что такое N?
количество слов? букв? бит? разрядность регистра в процессоре?
Всего голосов 5: ↑5 и ↓0+5
N — это количество элементов массива, которые сортируются за каждый проход.
Всего голосов 7: ↑0 и ↓7-7
Тогда при чём тут буквы?
Всего голосов 4: ↑4 и ↓0+4
В статье написано, что в сортировке были и латиница, и кириллица, и знаки препинания, и управляющие символы. Сортировать возможно все — абсолютно все. Главное, чтобы было задано правило сортировки, правило, по которому сортировать.
Всего голосов 7: ↑1 и ↓6-5
Но всё это не имеет никакого отношения к сложности алгоритма
Всего голосов 8: ↑8 и ↓0+8
Да, не имеет. Я упоминул, что в сортировке есть и латиница, и кириллица, и знаки препинания, и управляющие символы, чтобы показать универсальность метода.
Всего голосов 6: ↑0 и ↓6-6
Справедливости ради логарифм там ближе к двоичному чем к десятичному, но учитывая смысл O-нотации разницы нет.
Всего голосов 2: ↑2 и ↓0+2

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

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

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

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

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


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


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

Всего голосов 4: ↑4 и ↓0+4

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

Всего голосов 3: ↑3 и ↓0+3
У нас есть такие ракеты… но мы вам о них не расскажем…
Всего голосов 13: ↑13 и ↓0+13
Не надо, а то сейчас еще автор мультфильм покажет, как его алгоритм быстро сортирует)
Всего голосов 2: ↑2 и ↓0+2
А какой смысл от статьи если она не раскрывает тему? Какая от алгоритма польза, если его нельзя применить даже теоретически потому, что применять нечего? Почитал коменты и ни в одном ответе не видел конкретики. Если нельзя выкладывать конкретику то и не нужна такая статья. Ну или напишите статью о методиках тестирования новых методов сортировок, от нее хоть польза будет.
Всего голосов 13: ↑13 и ↓0+13
НЛО прилетело и опубликовало эту надпись здесь
Это сложность каждого прогона. Что значит худшего случая? Первоначальный массив — он абсолютно произвольный, никаким образом неупорядоченный, без каких-либо закономерностей — это худший случай?
Всего голосов 10: ↑0 и ↓10-10
НЛО прилетело и опубликовало эту надпись здесь
Не знаю, меня это не очень интересует. Просто как происходит сортировка текста: сначала сортируется массив по 1-ому символу, затем данный массив разбивается на подмассивы, у которых 1-ая буква одинакова. После этого каждый подмассив сортируете заново. И так до последней буквы. И по этой же схеме работают все алгоритмы сортировки текста.
Всего голосов 10: ↑1 и ↓9-8
НЛО прилетело и опубликовало эту надпись здесь
Умеет. Есть программа для сортировки чисел (в том числе десятичных, отрицательных). Возможна сортировка любых объектов, главное задать правило для сортировки.
Всего голосов 4: ↑0 и ↓4-4
НЛО прилетело и опубликовало эту надпись здесь
Это, скорее, либо поразрядная сортировка (англ. radix sort, в комментах ниже упомянутый), либо блочная сортировка (англ. bucket sort). Они бывают вполне себе линейны (O(N)), но не для произвольных данных, а только для «подходящих» (например, много-много объектов, среди которых много-много повторов, или значения ограничены узкими рамками, и т. п.) Разницы между O(2n) и O(kn) тут не будет, потому что k не зависит от объёма данных (т. е. оба варианта сводятся к O(n)). Вполне себе тема, но если автор(ы) претендуют на универсальность алгоритма, то хотя бы результаты тестов надо было привести на разных типах данных, а не только на строках. А если авторы изобрели более эффективный алгоритм именно для сортировки строк (либо какого-то класса объектов со сходными ограничениями), то и сравнивать надо не с универсальными quicksort/mergesort из std::sort(), а со специализированными функциями сортировки строк.
Всего голосов 5: ↑5 и ↓0+5
НЛО прилетело и опубликовало эту надпись здесь
Так а что он там раскрыл? Его комментарий, на который вы отвечали — это вольная цитата из статьи в Википедии «Алгоритм сортировки», раздел «Сортировка строк». Это radix+bucket, где вы там увидали «вариацию QuickSort»?
Всего голосов 3: ↑3 и ↓0+3

Судя по описанию, вы изобрели Поразрядную сортировку или 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) И да, она хорошо работает в задаче о сортировке слов.

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

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


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

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

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

Всего голосов 2: ↑2 и ↓0+2
Данная схема — это не сортировка 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).
Всего голосов 3: ↑0 и ↓3-3

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

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

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

Всего голосов 2: ↑2 и ↓0+2

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

Всего голосов 2: ↑2 и ↓0+2
Это стандартная схема сортировки текстовых данных на современном этапе хоть в python, хоть в java.

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

Всего голосов 2: ↑2 и ↓0+2

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

Всего голосов 6: ↑5 и ↓1+4
НЛО прилетело и опубликовало эту надпись здесь
Уважаемый, ну вам же уже ответили. Я попытаюсь вас просветить. Математически доказано, что невозможно построить алгоритм, который бы мог отсортировать ЛЮБЫЕ данные быстрее, чем O(N log N).
Т.е. ваше утверждение, что ваш алгоритм бытрее std:sort на ЛЮБЫХ данных — некорректен. СУЩЕСТВУЕТ контрпример, на которм стандартный алгоритм будет быстрее.
Увы, без деталей реализации невозможно такой контрпример найти.
Существует МАССА алгоритмов, которые быстрее стандратного на определенном типе данных. Ваш — один из них.
Поймите, интерес к деталям обусловлен не желанием украсть вашу коммерческую тайну, а просто мы пытаемся подтолкнуть вас к осознанию положения вещей.
Всего голосов 7: ↑7 и ↓0+7
Строго говоря — невозможно при наличии определённых ограничений («in-place» и всё такое). Так-то всякие зануды и буквоеды легко могут предъявить counting sort, который работает за O(N) в лучшем и худшем случаях.
Всего голосов 3: ↑3 и ↓0+3
Там только одно ограничение: при сортировке используется сравнение объектов между собой. Counting sort, radix sort и прочие объекты между собой не сравнивают, потому и линеарифмическая нижняя граница на них не распространяется.
Всего голосов 3: ↑3 и ↓0+3
Но чуда все равно не будет. Даже если не называть эти опреации сравнением, всё равно в реальной релизации БУДУТ примеры, когда специализированные алгоритмы будут медленнее универсального.
Всего голосов 2: ↑2 и ↓0+2
нет — берем массив и раскладываем элементы из него в другой массив по индексу равному элементу — получаем упорядоченный массив за линейное время (может быть еще раз пройтись чтобы убрать неиспользуемые места)
— ни одного сравнения, но нужно очень много памяти.
Всего голосов 3: ↑2 и ↓1+1
— ни одного сравнения, но нужно очень много памяти.
А ещё, сортировать так можно только чисел, диапазон значений которых не превышает размер доступного адресного пространства. И с количеством повторов, не превышающим диапазон значений адресуемой ячейки. И только если это прямо всамделишные массивы, во всякие списки, хэшы и прочие высоко-уровневые структуры скорость вставки и удаления тоже зависит от количества элементов.
Всего голосов 2: ↑2 и ↓0+2
Нет, не получится. Контрпример:
Берем массив [0, MAXINT_64], и сортируем вашим алгоритмом.
Вам понадобится MAXINT_64 сравнений, чтобы пройти по «отсортированной» памяти и найти все (2) вставленных значения, а классическому алгоритму будет достаточно 1-го сравнения.
Всего голосов 4: ↑4 и ↓0+4
А вы слышали про SleepSort? Она вообще за один проход сортирует.
Всего голосов 3: ↑3 и ↓0+3
Что значит худшего случая?

Без деталей алгоритма не скажешь. Где-то — полностью отсортированный массив. Где-то — отсортированный задом наперед. Где-то — полностью случайные данные. Где-то — массив, состоящий из одного значения элементов…
Всего голосов 2: ↑2 и ↓0+2
Я же указал, что было первоначальными массивами. Какая закономерность есть в «Войне и мире», в «Тихом Доме» и в остальных произведениях. Это абсолютно случайные данные, без каких-либо закономерностей. Разве, что в 3-ем и 7-ом тестах: вторая часть полностью повторяет первую. Но поверьте: данная закономерность нигде не используется. В остальных тестах даже такой закономерности нет.
Всего голосов 4: ↑0 и ↓4-4
Вот видите, вы уже сузили рамки своего алгоритма до «сортировка слов, слов много разных, они распеределены по определённому закону».
На таких данных ваш алгоритм вполне может показывать линейную зависимость.
Только именно это и надо указывать в заголовке.
Всего голосов 4: ↑4 и ↓0+4
Ну по какому закону они распределены, где я об этом говорил или как-то там еще упоминал.
Всего голосов 5: ↑0 и ↓5-5
По равномерному? Опровергайте.
Всего голосов 2: ↑2 и ↓0+2
По равномерному, согласен. Но равномерное распределение не дает какой-то закономерности, которую можно использовать и применить какие-то специальные методы.
Всего голосов 3: ↑0 и ↓3-3
А доказать сможете, что оно равномерное, распределение?
Всего голосов 3: ↑3 и ↓0+3

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

Всего голосов 3: ↑3 и ↓0+3
Сначала подумала, что это просто весна, но открыла профиль, и, вот это да, очередной повелитель brand new сортировок, приглашенный valemak'ом.
Хмммммм… *подозрительно щурится*
Всего голосов 2: ↑2 и ↓0+2
Я даже в профиль не смотрел, а оказалось, что товарищ valemak очередного гения призвал.
Интересно услышать мотивацию, т.к. один раз ещё можно поверить в случайность, но второй подряд срыватель покровов.
Подозрительно, очень подозрительно.
Всего голосов 2: ↑2 и ↓0+2
Да вон парой веток ниже Валерий объяснил, что ему иногда пишут срыватели. Инвайтов ему не жалко, а дальнейшая их судьба — исключительно их же забота. И г-н Рыбинкин — его рук дело.
Всего голосов 2: ↑2 и ↓0+2
Ясно.
Интересно, что товарищам кто-то довольно кучно ставит плюсики, что уже ставит под сомнение игнорирование их судеб «полноправными» пользователями.
Всего голосов 3: ↑3 и ↓0+3
  • Я построил самый быстрый самолёт!
  • А какую скорость замеряли: взлета, посадки, загрузки, максимальную полетную, воздушную (калиброванную, истинную, эквивалентную), путевую, сваливания, крейсерскую или другую какую может?
  • А что такое скорость?
Всего голосов 9: ↑9 и ↓0+9
Хм…
Допустим у нас есть некий алгоритм, реализован в виде функции, на вход которой приходит массив. Внутри этой функции есть 3 невложенных foreach:
someFunction(someArray) {
foreach(someArray){
}
foreach(someArray){
}
foreach(someArray){
}
return someResult
}
Какова сложность данного алгоритма в big-O нотации?
Внутри циклов нет других циклов.
А у такого варианта какова сложность:
someFunction(someArray) {
foreach(someArray){
foreach(someArray){
foreach(someArray){
}
}
}
return someResult
}
Всего голосов 2: ↑2 и ↓0+2
НЛО прилетело и опубликовало эту надпись здесь
К сожалению, я не могу раскрывать все нюансы алгоритма. Могу только сказать следующее. На двигателе внутреннего сгорания невозможно улететь в космос, для этого нужны реактивные двигатели. В новой сортировке используется другой подход, поэтому и получились такие результаты.
Всего голосов 13: ↑0 и ↓13-13

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

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

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

Всего голосов 2: ↑2 и ↓0+2
Если выбирать среднее или максимальное, тогда в 8 столбце значения получаются не 15%, а значительно больше
Всего голосов 9: ↑0 и ↓9-9
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Вот только распределение будет разным. Слова, если брать русский — очень много слов, начинающихся менее чем с 30 строчных букв (за минусом йыьъ), это уже 5 бит сравнения в самом частом случае, плюс довольно мало слов с заглавных. В случае с числами — много чисел, у которых первый байт в диапазоне от 0 до 255, что как бы уже вынуждает сравнивать 8 бит для каждого байта. В некоторых реализациях это способно хорошо ускорить процесс.
Всего голосов 6: ↑6 и ↓0+6
НЛО прилетело и опубликовало эту надпись здесь
Да даже недавние бенчмарки реализации wc на хаскелле —
habr.com/ru/post/489958
на «хороших» данных работает лучше всех, на случайных данных — уже не так уж и экстремально быстро.

На данный момент как раз почему-то в качестве набора данных для сортировки использован естественный текст. Причина?
Всего голосов 3: ↑2 и ↓1+1
Смотрел выступление одного интересного профессора, он занимался вопросом максимального повышения точности подсчета производительности. Потому что на скорость влияет состояние операционной системы, многозадачность, текущие операции, особенности работы хранилища данных.

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

Подход позволяет посчитать с точностью до процессорной инструкции время вычисления, плюс заодно напрямую получить точное количество обработанных байт оперативной памяти.
Всего голосов 4: ↑3 и ↓1+2

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

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

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

Здесь бенчмарк достаточно запустить один раз и все случайные факторы просто не оказывают влияние. Да, не нравится ограниченность именно RISC архитектурой, но…
Всего голосов 3: ↑2 и ↓1+1
А вот на x86 нет смысла считать процессорные инструкции. Предсказание ветвлений и кэш дают огромный прирост в скорости, игнорировать его нельзя. Александреску рассказывал об этом, с примерами, когда «теоретически» более быстрый код с меньшим числом сравнений и инструкций выполняется медленнее, чем код с большим числом.
Всего голосов 6: ↑6 и ↓0+6
НЛО прилетело и опубликовало эту надпись здесь
Ну, условия достаточные для повторения результатов — конкретная версия поставляется с конкретным компилятором и в комплекте идут вполне себе конкретные библиотеки.
Всего голосов 2: ↑2 и ↓0+2
НЛО прилетело и опубликовало эту надпись здесь
Предлагаю автору сравнить свой алгоритм сортировки ещё с Intellij Idea, Eclipse, Vim, Emacs (функция M-x::sort-lines) и обязательно с «Microsoft Notepad».
Всего голосов 8: ↑8 и ↓0+8
Судя по всему, мы наблюдаем результат лабораторной работы по алгоритмам и структурам данных. Был изобретен my_radix_sort.
Всего голосов 7: ↑7 и ↓0+7

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

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

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

Всего голосов 2: ↑2 и ↓0+2
Я так понял, это новый уровень троллинга? Ну, что сортировка, которая умеет только сравнивать элементы, не может иметь сложность лучше O(N*log(N)) — это бог с ним, не будем догматиками. Но мы всерьез должны обсуждать тезис «у меня есть мифический алгоритм, существование которого не доказано, но вы должны в него верить, а, чтоб вам лучше верилость, я покажу вам табличку, красиво оформленную в Excel»? Как давно Хабр стал религиозным сайтом?
Всего голосов 7: ↑7 и ↓0+7
А внутре у него, сталбыть, неонка?
Всего голосов 6: ↑6 и ↓0+6
Нейронка.
Всего голосов 2: ↑2 и ↓0+2
А все-таки, почему сведения о таком фундаментальном прорыве в теории алгоритмов сортировки вдруг публикуются не в каком-то уважаемом научном издании, а на Хабре, который вполне себе приличный сайт, но явно не то место, куда изначально отправляют такие разработки?)
Всего голосов 2: ↑2 и ↓0+2
А где здесь прорыв? Алгоритмы сортировки с O(N) известны и используются.
То, что radix sort лучше подходит для сортировки строк, чем сортировки сравнениями — тоже не новость. В особо секретных документах даже можно найти, почему так происходит ;)
Всего голосов 3: ↑3 и ↓0+3
Спасибо Бабушкину, что он подмышки бреет :-)
Всего голосов 4: ↑3 и ↓1+2

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


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


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

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

Всего голосов 9: ↑9 и ↓0+9
Прошу не забывать, что Владимир Рыбинкин (автор «сортировки воронкой») также был дважды приглашён по моим инвайтам.
Всего голосов 2: ↑2 и ↓0+2
У вас там какая-то секта?
Всего голосов 4: ↑4 и ↓0+4
Всё объясняется достаточно просто.

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

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

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


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

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

Это модифицированная сортировка слиянием. Используется 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. Сортировка воронкой подходит для очень узкого круга вариантов.

Всего голосов 5: ↑5 и ↓0+5

Спасибо.

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

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


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

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

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

Всего голосов 3: ↑3 и ↓0+3
Да, этой сортировкой можно, сортировать все. Там нет привязки, к чему-либо. Я об этом уже писал не единожды.
Всего голосов 8: ↑0 и ↓8-8
Да, этой сортировкой можно, сортировать все.

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

Всего голосов 5: ↑5 и ↓0+5
Не верим! Это примерно то же самое, что сказать что Вы придумали вечный двигатель. Если Вы несогласны, то продемонстрируйте пожалуйста результаты релевантных тестов, а не что-то левое, что вы показали в статье.
Всего голосов 3: ↑3 и ↓0+3
Что значит _релевантных_ тестов, и почему Вы решили, что данные тесты — это что-то левое.
Всего голосов 4: ↑0 и ↓4-4

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

Всего голосов 4: ↑4 и ↓0+4

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


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

Всего голосов 4: ↑4 и ↓0+4

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

Всего голосов 2: ↑2 и ↓0+2

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

Всего голосов 3: ↑3 и ↓0+3
Разъясните, пожалуйста, что Вы хотите, чтобы я сделал более подробно. Какие тесты я должен сделать.
Всего голосов 3: ↑0 и ↓3-3

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


  1. Клонировать git-репозиторий https://github.com/erthink/sort;
  2. Для проверки собрать проект посредством CMake и запустить runme;
  3. Добавить вашу реализацию сортировки по аналогии добавления radixsort;
  4. Запустить 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.

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

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

Всего голосов 3: ↑3 и ↓0+3

Никаким.

Всего голосов 4: ↑4 и ↓0+4
Данная сортировка не относится к классу сортировок посредством сравнений.
Всего голосов 3: ↑0 и ↓3-3

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

Всего голосов 4: ↑4 и ↓0+4
К чему вопрос? Как можно сортировать без сравнений? Разработан новый алгоритм, работающий по другим правилам. Можно сортировать текстовую информацию, целые и десятичные числа, положительные и отрицательные.
Всего голосов 5: ↑0 и ↓5-5
К чему вопрос?

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


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

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


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

Всего голосов 2: ↑2 и ↓0+2
Можно сортировать текстовую информацию

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


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

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

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


linea
lonja
llamar

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


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


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

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


Почему?

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


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

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

Всего голосов 2: ↑2 и ↓0+2
Можно и в русском языке пример найти: e (U+0435) → ё (U+0451) → ж (U+0436)
И в немецком: ss → ß → st
И, подозреваю, в любом другом языке, в котором используются грависы, акуты, циркумфлексы и прочие седильи и лигатуры.
Всего голосов 3: ↑3 и ↓0+3
Как можно сортировать без сравнений?
ну вот же, например: radix sort, pigeonhole sort, counting sort. Эти сортировки имеют сложность худшего случая O(N), но у них у всех есть существенные ограничения, как и у Вашей. Вы же сами сказали, что Ваша сортировка «не относится к классу сортировок посредством сравнений». Зачем тогда спрашиваете?
Всего голосов 3: ↑3 и ↓0+3
Функция std::sort является универсальной, ваша — специализированной для строк. Как ваш алгоритм ведет себя на сортировке чисел по сравнению с std::sort? Притом как целых, так и с плавающей запятой? Неизвестно.
Всего голосов 3: ↑3 и ↓0+3
Пожалуйста, прочитайте комментарии. Я писал, уже, что она универсальна, на ней можно, и в том числе, числа (как десятичные, так и отрицательные).
Всего голосов 4: ↑0 и ↓4-4
Э нет, так не пойдет, покажите результаты. Я не сомневаюсь в том, что это возможно, но я сомневаюсь, что вы сохраните 15% эффективности по сравнению с std::sort. Особенно в том, что касается чисел с плавающей запятой.
Всего голосов 3: ↑3 и ↓0+3
15% — это реальные значения для текстовой информации, без всякого подгона, мухлежа. Для плавающей запятой сортировка также работает, но я не тестировал настолько, чтобы дать такую же информацию, как по текстовой.
Всего голосов 5: ↑0 и ↓5-5
Это 15% по сравнению с относительно медленным алгоритмом, а потому неинтересно. А на плавающей запятой стоило бы потестировать.
Всего голосов 2: ↑2 и ↓0+2
> без всякого подгона, мухлежа
Сознательного подгона и мухлежа. Подгон и мухлеж очень часто возникает в результате незнания, потому в университетах долго и сложно учат методикам проведения и анализа экспериментов, и годами два раза в неделю тренируют студентов практикумами, что бы они набрались опыта в этом деле. Правильные тесты — это сложно.
Всего голосов 3: ↑3 и ↓0+3
для того, чтобы о чем-то рассуждать, надо знать, о чем рассуждаешь

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

Всего голосов 4: ↑4 и ↓0+4

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

Всего голосов 3: ↑3 и ↓0+3
фух, теперь понятно, что это мне напомнило.
Всего голосов 2: ↑2 и ↓0+2
-50 за 12 часов — хорошее достижение, не каждому дано, приглашенные прогрессируют.
Всего голосов 3: ↑3 и ↓0+3
Видимо, человек задался целью побить легендарные треды про BolgenOS
Всего голосов 3: ↑3 и ↓0+3
Непонятна цель написания этой статьи. Похвастаться тайным алгоритмом, который у вас есть?
Всего голосов 3: ↑3 и ↓0+3
Я проверил: ни одного комментария автора статьи без отрицательной оценки. Или флешмоб, или кому-то стоит подумать.
Всего голосов 2: ↑2 и ↓0+2
А с какими комментариями автора Вы согласны?
Всего голосов 2: ↑2 и ↓0+2
Откровенно говоря, я их даже не читал после второго. А имеет смысл?
Всего голосов 3: ↑3 и ↓0+3
НЛО прилетело и опубликовало эту надпись здесь
Всем большое спасибо за интерес, проявленный к данной статье.
А как Вы отнесетесь, если я сообщу следующую информацию.

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

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

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

Всего голосов 5: ↑2 и ↓3-1
  1. Вы так и не показали воспроизводимых результатов оценки вашей сортировки. Инструкции вам были предложены неделю назад.
  2. Закодируйте и покажите ваш "бенчмарк деления" на актуальной версии python (там внутри GMP) и посмешите порадуйте нас результатами.

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

Всего голосов 5: ↑5 и ↓0+5
А как Вы отнесетесь, если я сообщу следующую информацию.

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

Всего голосов 5: ↑5 и ↓0+5

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


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


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

Всего голосов 5: ↑5 и ↓0+5
Господа, не кажется ли вам что это школьник/школьники на информатике рандомно сделали прогу и под острыми впечатлениями решили писать сюда? Где судя по комментам были раздавлены в пух и прах)))
Всего голосов 2: ↑2 и ↓0+2
Я сравнил алгоритмы сортировки Visual Studio 2017 std::sort, CLion std::sort, notepad++ std::sort, GoLand sort.strings(string) и алгоритм сортировки на 1С со сложностью O(1). Самым быстрым оказался алгоритм сортировки из Vim со сложностью O(надо было сделать еще вчера).

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

Публикации

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

Истории

Ваш аккаунт

Разделы

Информация

Услуги

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