В Интернете не представлены трудные массивы для алгоритмов сортировки (мне, во всяком случае, их найти не удалось), а многочисленные «сравнительные анализы» алгоритмов на массивах в несколько сотен или тысяч элементов, просто смешны, а потому я решил прогнать «воронкой» те массивы, на которых проводились исследования с количеством элементов, по крайней мере, 10^5 и более.
Сначала небольшой обзор того, что пишут про алгоритмы сортировки с моими комментариями:
На собеседованиях часто спрашивают, какая сортировка самая быстрая. Вопрос с подвохом. В ответ вы должны спросить: «А для какого случая выбирается оптимальная по времени сортировка?» И лишь тогда, когда будут озвучены условия, можно смело перебирать имеющиеся варианты.
Моя версия очевидна: алгоритм «воронки» идеален для любых «условий», озвучивать которые совершенно не обязательно.
Подумайте, как будут вести себя эти и другие алгоритмы сортировки для таких случаев входных данных (иногда вырожденных) как:
1. уже отсортированный массив;
2. отсортированный в обратном порядке массив;
3. частично упорядоченный массив;
4. массив с повторяющимися элементами;
5. массив, все значения которого одинаковы.
Первый, второй и пятый случай, очевидно, имеют линейную сложность, два других зависят от того, насколько «частично упорядочен массив» и сколько там «повторяющихся элементов». Чем больше, тем быстрее пойдёт сортировка! Впрочем, у «воронки» нет «трудных» входных данных!
Основную цель конструирования новых алгоритмов можно определить следующим образом: уменьшение общего времени сортировки массива.
Именно! А не минимизация этого несчастного «количества сравнений»!
В качестве тестовых данных используются различные массивы целых четырехбайтовых чисел:
— псевдослучайные неупорядоченные числа;
— числа, расположенные по не возрастанию;
— числа, расположенные по не убыванию.
Два последних варианта, очевидно, линейные. Сортировка интов, очевидно, куда проще сортировки строк. Ну, так и быть: если попадутся тестовые массивы для интов, доработаю чуток алгоритмы чтения, записи и сравнения элементов.
Как показывает практика, между числом операций и временем выполнения программы не всегда есть линейная зависимость. Как показано далее, подобная ситуация складывается при оценке времени сортировки больших объёмов данных. Выяснение причин такого явления выходит за рамки рассматриваемых вопросов, однако его наличие — факт установленный и с ним следует считаться при построении эффективных последовательных и параллельных алгоритмов.
Аксиома! О чём я и писал в своей заметке и многочисленных комментариях к ней.
Использование стандартной процедуры «быстрой сортировки» qsort нецелесообразно по следующим причинам:
— алгоритм в наихудшем случае требуется порядка O(n^2) операций, что не позволяет выполнять сортировку произвольных массивов сколько-нибудь значительного размера за приемлемое время;
— время выполнения сортировки с помощью процедуры qsort больше, чем время работы других рассматриваемых алгоритмов, даже в среднем случае. Вероятно, это является платой за универсальность интерфейса (процедура qsort позволяет обрабатывать данные любого типа) и происходит за счет неэффективного доступа к элементам сортируемого массива.
Даже так? Как я уже писал, лично мне достаточно и первого пункта.
Непосредственное использование рекурсии в алгоритме сортировки слиянием требует значительных накладных расходов. Главным образом, они вызваны необходимостью применения дополнительных массивов при слиянии упорядоченных фрагментов.
Так уберите рекурсию! Как я уже писал, нормальные люди просто начинают сливать массивы, начиная с единичных элементов! И не нужно будет «на каждом шаге выполнить копирование результата, что значительно замедляет обработку».
При четырех процессорах, даже имеющих доступ к общей памяти (в этом случае затраты на передачу массивов от процессора к процессору можно считать равными нулю), ускорение не превысит 3.5. При использовании 32 процессоров на общей памяти ускорение не превысит 10.
Ну так и не мучайтесь! И одного процессора вполне достаточно! Алгоритм ведь достаточно быстрый — чай, не задача коммивояжёра! Тем более, что «заключительное слияние двух половин всего массива выполняется на одном процессоре».
Массив из 100 миллионов четырехбайтовых чисел отсортирован на 640 процессорах за 1.21 сек. Одному процессору этой системы для сортировки того же массива требуется 83.51сек.
Я и говорю: не мучайтесь! Займите лучше процессоры каким-нибудь другим полезным делом!
Теперь посмотрим на две статьи Хабра.
Первая статья: habr.com/ru/post/133996
Сравнивать я, разумеется, ничто ни с чем не собираюсь — просто прогоню «воронкой» те же массивы, если это окажется возможным.
Каждый алгоритм запускался на одних и тех же данных по три раза, брался в расчет лучший результат (чтобы кратковременные нагрузки системы не повлияли на наш честнейший эксперимент). Железо: ноутбук HP dv3510er, Intel Core 2 Duo 2Ггц, 2Гб RAM. ОС: Ubuntu 11.10
Ну, три так три. Железо у меня примерно такое -же (чуток получше): двухъядерник 2.8ГГц, 2Гб RAM. ОС WinXP.
Эксперимент 1: Работа на обычных данных
Было сгенерировано 10 наборов по 10^8 случайных натуральных чисел, для каждого алгоритма было замерено среднее время работы.
Ну, 10 так 10… что тут у нас… rand от WATCOM генерит инты в диапазоне 32К? Как-то маловато будет. Ладно, запишем дважды — в младшие и в старшие байты инта по рандому. Ну и, до кучи, объединим все 10 массивов в один — получим ещё данные и для массива в 10^9 элементов.
Эксперимент 2: Независимые отсортированные группы равного размера
Дано 10^8 различных натуральных чисел, отсортированных по возрастанию. Группируем их по k последовательных элементов и переставляем все группы в обратном порядке.
Господи, чего только ни придумают! :) Ну, для k=10^8, как я понимаю, это и будет тот самый «отсортированный массив». Для для k=10^0 — он же, но отсортированный в обратном порядке. А для остальных, соответственно… ну, вроде как сгенерил. Эти массивы мы тоже сольём в один — элементов там будет на 100 миллионов меньше, чем в первом «обобщённом» тесте.
Эксперимент 3: Отсортированные группы разных размеров, ограниченный диапазон значений
Дано 10^8 целых чисел из ограниченного диапазона (в нашем случае [0: 100000]) и они упорядочены группами произвольного размера от 1 до k.
Ну, и как это прикажете понимать? Я вот ВООБЩЕ не понял алгоритма генерации! Ладно, этот тест пропускаем.
Эксперимент 4: Произвольные перестановки
Сгенерируем частично упорядоченные данные другим способом: возьмем 10^8 произвольных натуральных чисел, отсортируем их и сделаем k произвольных перестановок двух элементов местами.
Этот тоже пропускаем — это вообще не тест: вначале идёт чисто отсортированный массив с ничножным количеством искажений, а в конце просто случайный массив. Ну да, так и есть: все алгоритмы выстроились в той же последовательности, что и в первом тесте, и даже время у них практически совпадает!
Вторая статья: habr.com/ru/post/335920
Описания алгоритмов, описания… описания… описания… а тесты-то где? Ага, вот они: Железо и система: Процессор: Intel Core i7-3770 CPU 3.40 GHz ОЗУ: 8 ГБ
Здесь железо чуть получше моего, но неважно.
Все тесты поделены на четыре группы. Первая группа — массив случайных чисел по разным модулям (10, 1000, 10^5, 10^7 и 10^9). Вторая группа — массив, разбивающийся на несколько отсортированных подмассивов. Фактически брался массив случайных чисел по модулю 10^9, а далее отсортировывались подмассивы размера, равного минимуму из длины оставшегося суффикса и случайного числа по модулю некоторой константы. Последовательность констант — 10, 100, 1000 и т.д. вплоть до размера массива. Третья группа — изначально отсортированный массив случайных чисел с некоторым числом «свопов» — перестановок двух случайных элементов. Последовательность количеств свопов такая же, как и в предыдущей группе. Наконец, последняя группа состоит из нескольких тестов с полностью отсортированным массивом (в прямом и обратном порядке), нескольких тестов с исходным массивом натуральных чисел от 1 до n, в котором несколько чисел заменены на случайное, и тестов с большим количеством повторений одного элемента (10%, 25%, 50%, 75% и 90%).
А здесь, собственно, и проверять нечего! Либо то, что уже было, либо ещё более привлекательное для воронки «большое количество повторений». Ну, и что тут гонять «по 20 запусков»? В общем, даю результаты по тестам из первой статьи:
Тесты первой группы:
0: N=2602009514 T=195 sec
1: N=2602148436 T=193 sec
2: N=2601943056 T=191 sec
3: N=2602055129 T=194 sec
4: N=2601888286 T=195 sec
5: N=2602105643 T=191 sec
6: N=2601928733 T=191 sec
7: N=2601947256 T=196 sec
8: N=2601891575 T=193 sec
9: N=2602105643 T=196 sec
0-9: N=29495155841 T=3210 sec (8 tmp-файлов)
Как-то очень уж ровненько и по времени, и по числу сравнений.
Тесты второй группы:
0: N=199999998 T=18 sec
1: N=1923669691 T=57 sec
2: N=1683854900 T=46 sec
3: N=1480233649 T=42 sec
4: N=1249780062 T=39 sec
5: N=996602000 T=33 sec
6: N=666000198 T=26 sec
7: N=340000016 T=21 sec
8: N=99999999 T=16 sec
0-8: N=11462881951 T=968 sec (7 tmp-файлов)
Во всех случаях время приведено «грязное», то есть туда входит время загрузки исходного массива в ОЗУ, собственно сортировка и время записи результатов в файл (для крупных массивов ещё и время слияния временных файлов). Результаты говорят сами за себя (причём во время сортировки «миллиардера» я и написал эту заметку). Программа сортировки практически та же, что и для сортировки строк: чтение и запись элементов производится побайтно (просто длина строки всегда 4 байта), и только в процедуре сравнения элементов сравниваются не строки, а инты (как UI32). Так что выбрасывайте, господа, все алгоритмы на помойку — алгоритм сортировки «воронкой» ИДЕАЛЕН! :)
Комментарии (202)
TheKnight
26.05.2019 21:24+8Не могли бы вы приложить ссылку на референсную имплементацию вашего алгоритма?
Разумеется, в виде исходного кода.
sadon
26.05.2019 21:26+7Ознакомьтесь для начала с теорией сложности алгоритмов,
затем посмотрите какие бывает основные алгоритмы сортивки, их не так уж и много.
Узнайте какая у каждого сложность.
После этого необходимость в экспериментах на ноутбуке пропадет.
FDA847
26.05.2019 21:30-4Так автор как раз пытается показать что «Как показывает практика, между числом операций и временем выполнения программы не всегда есть линейная зависимость».
lair
27.05.2019 00:58+9Зато между классом сложности алгоритма и порядком времени выполнения программы — есть достаточная корреляция, чтобы это можно было применять на практике.
А главное: автор же пишет "лучший алгоритм", а не "лучшая программа". Есть принятые формальные правила сравнения алгоритмов, почему бы ими не пользоваться? Или, если чужие не устраивают, озвучить свои явно хотя бы, и написать "лучший алгоритм по моей версии".
Hardcoin
28.05.2019 20:35+1есть достаточная корреляция, чтобы это можно было применять на практике
Применять можно, но есть хорошее исключение для примера, когда Big O не работает. Для перемножения матриц есть метод Копперсмита — Винограда, со сложностью О(n^2.4).
Однако на практике в большинстве реализаций BLAS (библиотеке матричных операций) используют модификацию наивного O(n^3), потому что он быстрее (хорошо ложится на кэш процессора).
panteleymonov
26.05.2019 22:42+3Недавно на собеседовании мне, человаку с 25 летним опытом практического программирования, академические зубрилы пытались впихнуть, что поиск симметрии быстрее будет на хеш-мапе O(1*n*2) чем на сортировке O(log(n)*n+n). И наибольший выигрыш хеш-мапа на больших массивах, но не тут то было.
Ну и тут немного интересного для любителей STL.
saipr
26.05.2019 21:32+4Сортировка слиянием.
Как много напомнили эти два слова. В далеком 1976 году я начинал службу в Прибалтике в г. Вентспилс. Из вычислительной техники у нас была ЭВМ М-220. А это 4К ОЗУ, 28К магнитный барабан и штук восемь лентопротяжек. Информации обрабатывалась немерино (сравните с характеристиками приводимыми автором статьи). Машинисток было много и они трудились без отдыха. И я только что закончивший Академию Ф.Э. Дзержинского, решил автоматизировать процесс формирования отчетов. За прототив был взят генератор отчетов от IBM — RPG. Так родился отечественный генератор (чем не импортозамещение) РПГ-М 220. За него я получил самую большую денежную премию 50 рублей. Что было примечательного?
Это сортировка информации, хранящейся на лентах. Сначала информация готовилась на перфокартах, затем она переносилась на ленту в ручную отсортированном порядке. За тем в лентопротяжки ставились три бабины: одна с новыми данными, вторая с данными, подготовленными ранее и чистая на которую переносилась информация получаемая слиянием.
Вы скажете какая древность. Но как были благодарны машинистки за эту автоматизация и сортировки и печати документов.
rybvv Автор
26.05.2019 21:42-13Поскольку у меня по-прежнему 1 коммент в час, и стадо ломанулось снова молча гадить в карму (причём по всем веткам, а когда я был в режиме read only, здесь стояла мёртвая тишина), отвечаю в том же режиме:
TheKnight
Нет, не мог бы. И вообще, прочтите предыдущую ветку на эту тему — у меня нет ни малейшего желания повторять всё по дцатому кругу.
sadon
Советчиков развелось как собак нерезаных! Я САМ решаю, что и как мне делать! У Вас «для начала» ПО ТЕМЕ ветки есть что сказать, г-н «учитель»?
FDA847
Нет, автор уже давно ничего не пытается показать. По крайней мере, «учителям». :)
saipr
Насколько я знаю, вообще самая первая программа, написанная для ЭВМ, была именно программой сортировки.
Кстати, занятно: у этой ветки сейчас оценка всё-таки +2 при 10 лайках (+6 — 4). Но это явно ненадолго — к карме за это же время я получил уже -2. :)Chuvi
26.05.2019 21:59+3мне тоже хотелось бы взглянуть на исходники чудесного алгоритма, но нет желания перечитывать тонны комментариев в поиске нужного.
TheKnight
26.05.2019 22:15+3habr.com/ru/post/448542
Их там нет.
UPD: habr.com/ru/post/448542/#comment_20050784 Кто то попробовал реализовать по описанию.
TheKnight
26.05.2019 22:23+2Я бы вам предложил бы добавить ссылку на статью с описанием алгоритма в дисклеймер к этой статье. Было бы проще бы понять, с чего все началось.
rybvv Автор
26.05.2019 22:45-18Их там нет.
И не было. И не будет. Я придумал алгоритм и написал программу где-то за неделю. Местное же стадо баранов более месяца ПО ГОТОВОМУ ОПИСАНИЮ неспособно прорубить алгоритм! Да и алгоритм-то ПРОСТЕЙШИЙ! Я же говорю: программисты ВЫМЕРЛИ! А остальным на исходники вообще смотреть противопоказано. Тем более, кому даже читать лень. Люмпены — что с них взять?
Я бы вам предложил бы добавить ссылку на статью с описанием алгоритма в дисклеймер к этой статье. Было бы проще бы понять, с чего все началось.
Да и так все знают: началось с вони и поучений, закончилось обильным наваливанием говна в карму. Но хорошо уже то, что истерически визжавшие давно уже молчат в тряпочку. Но очередной «учитель» уже припёрся. А здесь не описание алгоритма — здесь определение лучшего. И это именно «воронка»! :)
FDA847
Ого! Мне карму до -1 опустили уже
Быдло-с… Как я писал много лет назад: «Пуще огня они боятся любой свежей мысли — даже не из своей „профессиональной“ зоны — ибо каждая такая мысль есть риск вскрытия факта полного отсутствия оных в их собственных головах. На такие мысли они дружно набрасываются всей толпой».
FDA847
Но вот про исходники я реально не понял. В чём такая секретность? В прошлой статье сотня комментариев была про них. Было бы проще сравнивать сравнимое.
Да нет никакой «секретности» — алгоритм же описан! Но быдлу визжащему на кой исходники давать? Я вот сегодня писал в личку:
Алгоритм там реально сложный — в миллион раз сложнее этого несчастного «сортира»! Вот несколько фрагментов кода, для иллюстрации:
if (_TPSP.Tag == FASTSEARCH) // закончена быстрая итерация
{ // проверяем необходимость выхода
_TPSP.NSolAll += _TPSP.NSol; // количество решений на группе итераций
if (_TPSP.CountMAX >= _TPSP.NN)
goto LTypeFastSearch; // больше каскадов не предвидится
if (_TPSP.AttentionLevel < 21)// если уровень внимания недостаточно большой
_TPSP.AttentionLevel += 2; // увеличиваем его с ростом губины
if (_TPSP.CountMAX >= _TPSP.CountMIN)
{ // на последней итерации
_TPSP.AttentionLevel = 21; // по глубине смотрим всерьёз
if (_TPSP.NSol <= (_TPSP.NN >> 5))
goto LTypeFastSearch; // слишком мало решений, скоростной закончен
if (_TPSP.NSolAll <= (_TPSP.NN >> 3))
_TPSP.CountMIN = 16; // почистим напоследок на малую глубину
if (_TPSP.NSolAll > (_TPSP.NN >> 2))
_TPSP.CountMIN <<= 1; // увеличиваем минимальную глубину
if (_TPSP.CountMIN > _TPSP.NN)
_TPSP.CountMIN = _TPSP.NN; // рёбер у графа совсем мало
} // конец условия "максимальная глубина"
else // не достигли максимума
{ // повторяем всё с нуля
_TPSP.CountMAX <<= 1; // решений мало, глубина не предельная
if (_TPSP.NSol <= (_TPSP.NN >> 3))
if (_TPSP.CountMAX < _TPSP.CountMIN)
_TPSP.CountMAX <<= 1; // решений совсем мало, увеличиваем ещё раз
...
_TPSP.Tag = MEDIUMSEARCH; // переходим на средний поиск
_TPSP.CountDB = 0; // счётчик кандидатов на opt-3
_TPSP.NSolAll = 0; // число решений на нескольких итерациях
_TPSP.NMN = _TPSP.NN; // число мультиузлов (свободных рёбер)
_TPSP.MaxTime = 1; // максимальное время на расчёт ребра
for (_l = _TPSP.NN >> (EDGE_TIME + 3); _l != 0; _l >>= 2)
_TPSP.MaxTime <<= 1; // зависит от числа рёбер графа
_TPSP.AttentionLevel = 22; // признак ухода на средний алгоритм
#if GRMODE // подключена графика
...
_TPSP.CMAX = _TPSP.CountMAX << 2;
_f = _TPSP.LTour / _TPSP.NN * 0.7;
for (_c = 1; _c < _TPSP.AttentionLevel; _c++)
{ // определяем уровень внимания
if (_TPSP.L0001 <= _f) // по отношению к средней длине ребра тура
break; // попали в интервал, поиск окончен
if (!(_TPSP.CalcLenMode == PIFAGOR_FLOAT))
_f++; // коррекция погрешностей округления
_f *= ((F8)_c / 16 + 1); // на каждое приращение длины ребра
_TPSP.CMAX <<= 1; // удваиваем интервал поиска
} // конец цикла определения уровня внимания
if (_TPSP.L0001 < _TPSP.LTour / _TPSP.NN * 1.7)
_TPSP.CMAX >>= 1; // базовая глубина не затрагивает мелких рёбер
...
_TPSP.iN10 = _TPSP.iN00; // начальный узел мультиузла
_TPSP.N10 = _TPSP.N00; // и его паспорт
_TPSP.Dir1011 = _ReverseIndex[_TPSP.Dir0001];
_TPSP.Count2 = 0; // счетчик размера мультиузлов
_TPSP.Status = FREE_EDGE; // по умолчанию продолжаем перебор
LDefBoardMN: // определяем границы мультиузла
GetNode (_TPSP.iN11 = _TPSP.N10.Tour[_TPSP.Dir1011], (TDP)&_TPSP.N11);
_TPSP.Dir1110 = GetDirection ((TDP)&_TPSP.N11, _TPSP.iN10);
if (_TPSP.Count2 > (_TPSP.NN >> 1))
goto LNoSetTags; // мультиузел слишком крупный
switch (_TPSP.N10.Tag[_TPSP.Dir1011] & (UI8)EDGE_MASK)
{ // тег ребра текущего узла мультиузла
case FREE_EDGE: // найдена граница мультиузла
_TPSP.L1011 = GetVectorLen ((TDP)&_TPSP.N10, (TDP)&_TPSP.N11);
goto LQDefBoardMN; // поиск границы мультиузла завершён
case OLD_EDGE: // мультиузел продолжается дальше
_TPSP.Dir1011 = _ReverseIndex[_TPSP.Dir1110];
_TPSP.iN10 = _TPSP.iN11; // новый текущий узел мультиузла
_TPSP.N10 = _TPSP.N11; // и его паспорт
goto LDefBoardMN; // продолжаем поиск границы мультизула
case NEW_EDGE: // с этой стороны мультиузла может встретиться
case BREAK_EDGE: // лишь два валидных значения статуса рёбер
default:; // файл испорчен - считать больше нечего
SetFatalError (BadData); // о чём и сообщаем пользователю
} // конец переключателя по тегу ребра
Неужели эти придурки всерьёз считают, что они способны чем-то «помочь» и, тем более, «указать ошибки»? Вряд ли — иначе бы так не визжали и рот не затыкали! :)
TheKnight
Кстати, код на каких языках вы умеете читать?
Ни на каких. Чукча не читатель — чукча писатель.(с)
Я вам предлагал всего лишь сделать отсылку к ней, как сделаны ссылки на предыдущие статьи в цикле про задачу коммивояжера или цикле про искусственный интеллект.
Там заметки связаны, а здесь нет. С сортиром я пришёл на Хабр — как мне тогда казалось, в сообщество разработчиков. А эта заметка уже ни малейшего отношения к разработчикам не имеет.FDA847
26.05.2019 22:53+2Но вот про исходники я реально не понял. В чём такая секретность? В прошлой статье сотня комментариев была про них. Было бы проще сравнивать сравнимое. Желающие попробовали бы отсортировать у себя большие массивы, сравнили бы просто с той же быстрой сортировкой, и половина вопросов наверное отпала бы.
Chuvi
27.05.2019 08:45+1goto в си-шном коде? Дяденька, на дворе 2019 год, а не 1989. Ловите минус, авось про существование календаря вспомните.
TheKnight
27.05.2019 13:43+2В чем проблема goto в сишном коде? Вполне себе применимая в определенных случаях конструкция.
Вот в условной Java использование goto иногда таки вызывает вопросы.
PsyHaSTe
28.05.2019 18:59+1Мне кажется, Дейкстра активно объянял goto задолго до появления Java, и вопросы у него и с сишным кодом возникали.
playermet
28.05.2019 19:43+1Суть в полной истории.
Давным давно, в 60х годах, Дейкстра определил что код построеный на последовательностях, условиях и циклах, и без неграниченных безусловных переходов, может быть рекурсивно разложен и формально доказан. После чего и написал письмо в один журнал, чем объявил войну против goto, и где-то через десять лет эпического холивара, можно сказать, победил в ней.
Правда, задуманного ПО для доказательства так и не было написано по сей день. Но некоторые не разобравшись продолжают хейтить goto просто по инерции. А вишенкой на торте является тот факт, что goto в современных ЯП имеют ограниченную возможность передачи управления, и не особо-то мешали бы подобному анализу.PsyHaSTe
28.05.2019 19:47+1Основная претензия к goto в том, что человеческий мозг хорошо приспособлен к последовательному чтению сверху-вниз, и очень плохо переживает переключение контекста и прыжки в случайные места в программе. Вопрос верификации тут ортогонален, тем более что теорема Бома-Якопини наоборот раскладывает программу на гигантский свитч с кучей goto.
playermet
28.05.2019 20:50+1Основная претензия к goto в том, что человеческий мозг хорошо приспособлен к последовательному чтению сверху-вниз
Основная претензия кого? В письме Дейкстры в журнал об этом нет ни слова, мы ведь о нем говорим.
прыжки в случайные места в программе
Современные ЯП c goto не позволяют делать прыжки в случайные места программы.
Вопрос верификации тут ортогонален
Странно, тут какой-то Роберт Мартин в Clean Architecture утверждает обратное.PsyHaSTe
29.05.2019 02:11+1Основная претензия кого? В письме Дейкстры в журнал об этом нет ни слова, мы ведь о нем говорим.
Он обратил внимание на проблему. Goto не любят не из-за анализаторов и верификаторов
Современные ЯП c goto не позволяют делать прыжки в случайные места программы.
Они запрещают прыгать разве что внутрь другой функции. Прыжки вверх, вниз, вбок, куда угодно — пожалуйста.
Странно, тут какой-то Роберт Мартин в Clean Architecture утверждает обратное.
Ну раз Мартин сказал, тогда конечно.
playermet
29.05.2019 10:22+1Goto не любят не из-за анализаторов и верификаторов
Значительная часть программистов, если не большинство, не любят goto просто потому что им так сказали в институте или в интернете. При этом их основной аргумент — спагетти-код, уходит корнями как раз в эпоху до структурного программирования, где это действительно было большой проблемой.
Они запрещают прыгать разве что внутрь другой функции. Прыжки вверх, вниз, вбок, куда угодно — пожалуйста.
Если функция помещается в небольшой экран, метки имеют осмысленные имена, а goto не использован вместо существующих управляющих инструкций, то никаких проблем с ним обычно нет. А попытка например устранить goto для выхода из вложенных циклов может даже ухудшить понимание кода, нарушив его целостность при делении на подфункции или засоряя его кучей проверок.PsyHaSTe
29.05.2019 10:25+1Значительная часть программистов, если не большинство, не любят goto просто потому что им так сказали в институте или в интернете. При этом их основной аргумент — спагетти-код, уходит корнями как раз в эпоху до структурного программирования, где это действительно было большой проблемой.
Моя первая программа на паскале состояла из 5 goto на 40 строчек. Даа, это все потому, что мне сказали что это плохо, а не потому что разобраться в этом коде было мучительно сложно.
Если функция помещается в небольшой экран, метки имеют осмысленные имена, а goto не использован вместо существующих управляющих инструкций, то никаких проблем с ним обычно нет.
goto всегда используется вместо существующих конструкций, потому что его всегда можно отрефакторить на функцию/break/continue/..
Zenitchik
29.05.2019 15:20+1goto всегда используется вместо существующих конструкций
Ага, например, вместо вызова процедуры с оптимизацией хвостовой рекурсии.
В Паскале есть оптимизация хвостовой рекурсии?PsyHaSTe
29.05.2019 15:21+1Не факт, но зато там есть циклы.
Zenitchik
29.05.2019 15:25+1Ну да, на циклах конечный автомат писать — то ещё удовольствие.
Уж лучше goto — код изящнее получается.mayorovp
29.05.2019 15:36+1Для оптимизации хвостовой рекурсии конечного автомата не требуется.
Zenitchik
29.05.2019 15:50+1Разумеется. Зато для написания конечного автомата — чертовски удобно, если хвостовая рекурсия оптимизируется компилятором.
Тогда можно и костылей с циклами не городить, и без goto обойтись, и код для каждого состояния обособить.mayorovp
29.05.2019 15:56+2Любая хвостовая рекурсия может быть достаточно просто заменена на цикл, независимо от того, была ли она ранее конченым автоматом или нет.
Если вы свели конечный автомат к хвостовой рекурсии — вам уже не нужен goto!
Zenitchik
29.05.2019 16:31+1Любая хвостовая рекурсия может быть достаточно просто заменена на цикл
Это понятно, сам так делал неоднократно. Но это некрасиво.
С goto — получается граф, где каждая вершина — это метка, за которой следует код, а рёбра — переходы по goto.
То же самое, и даже ещё лучше было бы, если бы метки заменить на объявления функций, код заключить в этих функциях, а goto заменить на return q2(), где q2 — функция, введённая вместо одноимённой метки.
А с циклом… Возвращать из каждой функции ссылку на следующую функцию и крутить их в цикле… Можно. Приходится.PsyHaSTe
29.05.2019 20:09+1Покажите пример, где goto красивее цикла, пожалуйста.
Zenitchik
29.05.2019 21:23+1Простите, мне лень искать свои старые упражнения на Паскале, а в JavaScript — goto нет.
Хотите, напишу на абстрактный пример на условном «JavaScript с goto»?
GCU
30.05.2019 09:46Zenitchik В JavaScript есть аналог goto
developer.mozilla.org/ru/docs/Web/JavaScript/Reference/Statements/label и даже пример с циклами :)Zenitchik
30.05.2019 14:37+1Это не аналог «goto» даже близко. Почитайте повнимательнее, как это работает.
Там и метки служат совсем для другого. Сходство сугубо внешнее.
Akon32
30.05.2019 10:37+1Ну, я как-то с помощью goto эмулировал питоновский yield в коде итераторов на других языках. Получалось неплохо по сравнению с сооружением автомата.
playermet
29.05.2019 19:51+1Моя первая программа на паскале состояла из 5 goto на 40 строчек. Даа, это все потому, что мне сказали что это плохо, а не потому что разобраться в этом коде было мучительно сложно.
Ваш пример не опровергает мое утверждение. То что вы когда-то давно написали плохой код с goto не означает что нельзя написать нормальный. Но как можно видеть по началу ветки, некоторые триггерятся от одного только упоминания. Мой поинт в том, что ругать нужно не goto, а метод которым его готовят.
goto всегда используется вместо существующих конструкций, потому что его всегда можно отрефакторить на функцию/break/continue/
Я имел ввиду реализацию условий и циклов через goto.PsyHaSTe
29.05.2019 20:11+1Ваш пример не опровергает мое утверждение. То что вы когда-то давно написали плохой код с goto не означает что нельзя написать нормальный. Но как можно видеть по началу ветки, некоторые триггерятся от одного только упоминания. Мой поинт в том, что ругать нужно не goto, а метод которым его готовят.
Хороший код с goto это как код на Си без проблем с памятью. Чисто в теории может и бывает, но на практике не встерчал. Не могли бы дать ссылочку на исходник какой-нибудь тулзы/библиотеки (openssl там или еще что), где на goto красивый код, а он же на циклах был бы плохим? Пока что единственным кодом на goto который я видел и который нельзя было нормально переписать ни циклы был миллион
if something_bad { goto cleanup }в одной функции.picul
29.05.2019 21:07+1Ну в самом деле, давайте найдем индекс первого вхождения элемента в трехмерном массиве (код на C++, с чистым не особо знаком):
Вот Вы серьезно предлагаете пользоваться булевыми флагами или создавать функции вроде findElementMiddleLoop и findElementInnerLoop?constexpr size_t N = 16; int data[N][N][N]; size_t i, j, k; for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) for (k = 0; k < N; ++k) if (data[i][j][k] == desired_value) goto _end; _end:;lair
29.05.2019 21:31+1Ну, лично я за то, чтобы создавать отдельные функции вида "findFirstElement", потому что они повышают читаемость (и заодно стимулируют повторное использование).
picul
29.05.2019 21:44То есть логика поиска элемента в массиве становится более читаемой, если ее разбить на 3 функции? Тут 7 строчек тривиального кода, неужели они недостаточно читабельны?
lair
29.05.2019 21:47+1А почему три-то функции, когда ровно одна:
constexpr size_t N = 16; int data[N][N][N]; size_t i, j, k; for (i = 0; i < N; ++i) for (j = 0; j < N; ++j) for (k = 0; k < N; ++k) if (data[i][j][k] == desired_value) return (i, j, k);picul
29.05.2019 21:49+1Хм, согласен, что-то туплю к вечеру.
PsyHaSTe
30.05.2019 00:18+2Да, об этом я и говорю. Всегда можно либо сделать цикл, либо вынести в функцию. Во втором случае еще и читаемость вырастает, и переиспользовать можно.
А еще можно написать всё функционально
fn main() { const N: usize = 10; let desired_value = 0; let data = [[[0u8; N]; N]; N]; let result = (0..N) .flat_map(move |i| (0..N).flat_map(move |j| (0..N).map(move |k| (i, j, k)))) .filter(|&(i, j, k)| data[i][j][k] == desired_value) .next(); println!("{:?}", result); }
Как по мне, выглядит довольно опрятно, и линейные преобразования данных намного понятнее, чем циклы в которых может любая дичь происходить :)
С do-нотацией вообще было бы еще лучше
var n = 10; var desiredValue = 0; var arr = new int[n,n,n]; var result = from i in Enumerable.Range(0, n) from j in Enumerable.Range(0, n) from k in Enumerable.Range(0, n) where arr[i, j, k] == desiredValue select (i, j, k); Console.WriteLine(result.First());playermet
30.05.2019 10:31+1Преобразовать можно всегда, но не всегда это сделает код лучше.
Представьте что алгоритм с вложенными циклами требует последующей очистки данных, используемых в циклах. Просто return'ом уже не обойтись, придется делать две функции, и пробрасывать между ними часть данных. И читать их будет не проще, чем один единственный прыжок вниз, скорее даже сложнее.
Зачем ставить избегание goto самоцелью?PsyHaSTe
30.05.2019 11:32+2Зачем ставить избегание goto самоцелью?
Вот как раз поэтому
Представьте что алгоритм с вложенными циклами требует последующей очистки данных, используемых в циклах.
Когда цикл и швец и жнец, то разобраться в таком коде сложно. God-object не зря считается антипаттерном, god-method в котором все происходит и происходит goto к очистке сюда точно так же попадает.
Чтобы очистка работала, например, нужно выделить отдельную структуру данных, которая автоматически освободит данные при разрушении. И тогда все работать будет само.
Писать код, который знает, что там есть ресурсы с очисткой, сколько итераций сделать и какие действия над этими ресурсами делать, да еще и помнить что их нужно правильно очистить никому не пожелаю. SRP тоже хорошая аббревиатура.
Преобразовать можно всегда, но не всегда это сделает код лучше.
Покажите пример, когда это не так.
На том же примере выше метод с do-нотацией мне читается раза в 2 проще. А если добавить чуть-чуть логики между циклами то и во все 10.
mayorovp
29.05.2019 21:48+1Нет. Логика поиска элемента в массиве становится более читаемой, если её вынести в отдельную функцию целиком.
В одну функцию, а не в три разных.
playermet
27.05.2019 17:21+4Я придумал алгоритм и написал программу где-то за неделю. Местное же стадо баранов более месяца ПО ГОТОВОМУ ОПИСАНИЮ неспособно прорубить алгоритм! Да и алгоритм-то ПРОСТЕЙШИЙ!
Эмм, вы целую неделю писали реализацию простейшего™ алгоритма сортировки, который знали вдоль и поперек (ибо сами его изобрели), и подаете это как что-то позитивное? Ни в коем случае не сочтите это за хвастовство, но если даже если я выберу сложнейший из общеизвестных алгоритмов сортировки и предварительно разберусь в нем, то на написание реализации у меня уйдет максимум часы, а на действительно простейшие хватит и десяти минут. И само время на разбор будет примерно аналогичным. Какая может идти речь о простоте или понятности когда сам автор алгоритма пишет его неделю? За неделю можно в одного простенькую игру/сайт/приложение написать, но никак не сортировку.
А что касается людей которые вы «вежливо» обозначили стадом, так никому не впало тратить неизвестное количество времени на понимание мутного алгоритма, после чего еще неделю своей жизни забесплатно тратить на его реализацию, и тем более делать это ради доказательства кому-то неизвестному чего-то там в интернете.
TheKnight
26.05.2019 23:04+2И не было. И не будет.
Комментарий про отсутствие исходников адресован был не вам. Кстати, код на каких языках вы умеете читать?
Да и так все знают
К сожалению, по списку ваших публикаций не сразу понятно, какая из них относится к алгоритму сортировки воронкой. Я вам предлагал всего лишь сделать отсылку к ней, как сделаны ссылки на предыдущие статьи в цикле про задачу коммивояжера или цикле про искусственный интеллект.
valemak
26.05.2019 23:20А насколько эффективна сортировка воронкой при обработке малых массивов? Слово «малый» пусть не сбивает с толку, это тоже может быть задача из области big data.
Если понадобится отсортировать миллиард массивов, каждый из которых содержит всего несколько элементов — общее время на их обработку у «воронки» тоже будет самое лучшее?
Igor_ku
26.05.2019 23:29+6Мы в университете как раз проходим алгоритмы и структуры данных. Наш профессор говорит, что скорость алгоритмов принято измерять через анализ и выражать в виде О-нотации(ну или ещё пару нотаций). И ещё говорит, что никто не меняет в информатики скорость алгоритмов на конкретных компьютерах/машинах. У мене возник логичный вопрос, почему в статье меряют алгоритмы на конкретных примерах, а не через анализ? Зачем тогда мы учим как анализировать алгоритмы? Нельзя взять алгоритм и прикинуть его для 10^5, ибо это не значит, что ваш алгоритм не скатиться в какой-то О(n^3) начиная от 10^5+1. Буду рад, если поправят меня
FDA847
26.05.2019 23:42-4Как я понял, автору больше интересны практические результаты с «живыми» данными. Он ведь неоднократно заявлял, что он практик. Поэтому автор и сравнивает работу различных реализаций алгоритмов на реальных больших массивах данных. Вполне возможно, что при бОльших объёмах значений его алгоритм станет на несколько порядков медленнее. Поэтому было бы интересно посмотреть его программу.
Igor_ku
27.05.2019 00:12+2Да, но это ведь делает не возможным разговор об алгоритме? Кто знает, от чего может алгоритм может дать сбой. Может просто подбор файлов такой?
Хотя почитав комменты в прошлой статье и оценив карму, я теперь уверен что автор, мягко говоря, кхм, перестарался
FDA847
27.05.2019 00:16+1Ниже Dim0v пишет что примерная оценка алгоритма O(n * log n). Конечно, хотелось бы реализацию посмотреть. Если она реально так быстра, то потом можно будет и оценкой теоретической сложности заняться.
lair
27.05.2019 01:06+5Ниже Dim0v пишет что примерная оценка алгоритма O(n * log n).
То есть типовая для современных алгоритмов сортировки (например, у сортировки слиянием, которая даже и не современная, O(n log n)). Возникает разумный вопрос: так почему "лучший алгоритм"-то?
DocJester
27.05.2019 07:34+2Потому что в статье:
1) Нет формального описания алгоритма.
2) Оценивается не алгоритм, а некая его мистическая реализация (кстати, вот и причина, почему алгоритмы не оцениваются на конкретных машинах: на конкретном компьютере Вы получаете реализацию, на время работы которой влияют также факторы, не имеющие отношения к алгоритму).
К слову, а каким ещё нотациям кроме О-нотации и Тета-нотации учат? Первая повсеместная (оценка сверху), вторую тоже встречал (сверху и снизу). А какие ещё есть?Igor_ku
27.05.2019 10:13+3Всего мы учили 5 видов — маленькая «о», большая «О», тета, ну и соответственно маленькая и большая омега. Но дальше в лекция мы тоже использовали только большую О-нотацию и тету.
Словил себя на мысли, что если после лекций я могу учавствовать в обсуждении на хабре, то это показатель хороших лекций :)mayorovp
27.05.2019 10:24+1А как же теорема о том, что любая основанная на сравнениях сортировка делает ?(N log N) сравнений? Какую букву вы там использовали?
Hardcoin
28.05.2019 20:53+1никто не меняет в информатики скорость алгоритмов на конкретных компьютерах/машинах
А реальной практической деятельности иногда меряют. Потому что кэш и структуры данных могут заметно влиять на результат. Но в большинстве случаев более разумно оценить именно в О-нотации. Потому что измерение скорости на практике связано со своими сложностями, просто измерение времени на своей машине может дать ложную уверенность.
Я выше приводил пример, когда Big O даёт неверный ответ — перемножение матриц. Лучший (по оценке) алгоритм — Копперсмита — Винограда, но его не используют, потому что, внезапно, медленный (на практике, на существующих процессорах).
Если вы озвучите этот пример преподавателю, расскажите, какая была реакция :)
Но в большинстве обычных ситуаций Big O — это хороший способ оценки.
nklyuchnikovspb2
26.05.2019 23:39+3судя по всему весь алгоритм только в воображении автора имеется
FDA847
26.05.2019 23:48+1Так вот здесь ведь есть пример реализации (выше ссылку уже приводили):
habr.com/ru/post/448542/#comment_20050784
Правда там сравнивается реализация на JavaScript со встроенной функцией сортировки, которая, как я понимаю, находится в ядре браузере и поэтому может работать быстрее.
То есть не совсем корректное сравнение.
Но автор свою реализацию прячет, поэтому сложно сказать, что реально быстрее.nklyuchnikovspb2
27.05.2019 00:01+4автор пишет что это не оно, как я понял по комментариям (а их сложно понять, ведь стиль изложения характерен)
Politura
27.05.2019 05:56+2Правда там сравнивается реализация на JavaScript со встроенной функцией сортировки
По вашей ссылке реализация на Java.
Вот habr.com/ru/post/448542/#comment_20050834 комментарий от michael_vostrikov с реализацией на JavaScript, где сравнение идет с самописной-же реализацией QuickSort на том-же самом JavaScript.
После жарких дискуссий (где rybvv ведет себя, на мой взгляд, крайне некорректно, грубит всем подряд) michael_vostrikov сделал реализацию на C++, сравнил ее с QuickSort, TrimSort и MergeSort: habr.com/ru/post/448542/#comment_20084444
Его выводы: воронка где-то на 30% быстрее, чем QuickSort, но проигрывает современным TrimSort и MergeSort.
Ссылка на код с реализациями всех алгоритмов и с программой тестирования есть в комментарии.
rybvv Автор
26.05.2019 23:57-12Если сравнить ваши числа с числами из первой статьи
Вы с ума сошли?
Вы сами пишете, что железо у вас лучше, чем было использовано автором той статьи. То есть получается, что цифры воронки будут еще хуже.
Угу. Особенно, если учесть, что у воронки ГРЯЗНОЕ время. ;) Так что поделите на три, а то и на четыре. На второй группе тестов даже не знаю, на сколько делить нужно. :)
В отличие от той статьи, у вас помимо времени собственно сортировки зачем-то замерялось еще время ввода-вывода.
Затем, что я ПРАКТИК! Нет у меня никакой «истерики», а люмпены уже отписались не только в той заметке (дам сотни комментов), но даже в этой.
Скажите пожалуйста сами, как стоит назвать человека, считающего, что «двухъядерник 2.8ГГц» — это исчерпывающее описание характеристик процессора.
Да как хотите, так и называйте! Меня эта хрень вообще не интересует.
Все содержание заметки сводится к тому, что воронка сортирует непонятно какие данные на непонятно каком железе за 195 секунд. А какие-то другие — за 57. А третьи — за 3210.
Что Вам, блин, «непонятно»? За 195 секунд сортирует массивы ПЕРВОЙ группы, за 57 — ВТОРОЙ группы, за 3210 — ВСЕ массивы первой группы, вместе взятые (миллиард элементов), за 968 — все массивы второй (900 миллионов). Мне НАСРАТЬ, «как на этом железе работают другие алгоритмы» — я открытым текстом в заметке об этом написал.
Единственное, что можно вынести из статьи — это то, что поведение воронки и правда похоже на O(n * log n).
Да неужели? Счётчики сравнений во второй группе посмотрите! По крайней мере, первый и последний. ;)
самым производительным у вас оказался вариант с воронкой глубиной 1, который практически не отличается от обычной сортировки слиянием.
Вы бредите? У меня НА ВСЕХ тестах воронка глубиной 1! Кстати, это практически НИКАК не влияет на время сортировки — я проверял и 2, и 4, и так до глубины 64, о чём всё описано в первой заметке.
nklyuchnikovspb2
Господи, ну нет — и нет! Тыщу раз писал, что информация полностью определяется приёмником!
А, БЛИН! Предыдущие ответы затёр! И куда более важные! А всё потому, что в карму насрали, так что только раз в час могу комментировать! Тьфу!nklyuchnikovspb2
27.05.2019 00:08+5чтобы понять что такое ваша воронка нужно проникнуть в ваше воображение, а раз это не возможно, то в объективной реальности нет никакого алгоритма
lair
27.05.2019 01:07+4информация полностью определяется приёмником!
Если информация полностью определяется приемником, то вы по определению не можете никому ничего сообщить.
Dim0v
27.05.2019 01:18+7Вы с ума сошли?
Нет. А вы?
Так что поделите на три, а то и на четыре.
А чего так скромно-то? Давайте сразу на сто. А лучше на тысячу. Главное продолжайте всеми силами избегать замеров времени работы своего сортира и других сортировок в равных условиях. А там уж для "уравнивания" условий можно брать любой коэффициент. Хоть 3, хоть 4, хоть 100500. Предел — лишь ваше воображение!
Меня эта хрень вообще не интересует.
…
Мне НАСРАТЬ… я открытым текстом в заметке об этом написал.Это уже все поняли :)
Да неужели? Счётчики сравнений во второй группе посмотрите! По крайней мере, первый и последний. ;)
Вторая группа в плане оценки асимптотики среднего случая совершенно бесполезна и не показательна. Но вам (как практику) это понимать не обязательно, так что не берите в голову.
Вы бредите?
Нет. А вы?
У меня НА ВСЕХ тестах воронка глубиной 1!… о чём всё описано в первой заметке.
Да, именно это я и написал. В первой заметке вы поняли, что на практике ваша концепция воронок оказалась бесполезной и потому остановились на банальном разбиении входного потока на отсортированные подпоследовательности и дальнейшем слиянии этих подпоследовательностей как в merge sort.
И полученный вариант в плане асимптотики абсолютно аналогичен сортировке слиянием. Такие дела. На практике — да, может быть немного быстрее MergeSort-а для "реальных" данных. На некоторых очень специфичных данных (полностью отсортированный массив) — заметно быстрее. Но в целом по-прежнему хуже общепринятых алгоритмов сортировки, вроде того-же TimSort.
Chuvi
27.05.2019 08:37+5Чтобы вы не истирили на тему «Быдло анонимно ставит минус» — прочитал херню, поставил минус.
Dim0v
27.05.2019 00:02+9Доказать, что воронка идеальна, уж простите, у вас не получилась. Если сравнить ваши числа с числами из первой статьи (хоть их и нельзя сравнивать, об этом дальше), то окажется, что на случайных данных воронка мощно всасывает по сравнению со всеми алгоритмами из первой статьи, за исключением SmoothSort. На частично отсортированных данных дела получше, но воронка по-прежнему и близко не подходит к тому-же TimSort-у на всех без исключения "степенях" частичной отсортированности. А в отдельных случаях работает медленнее шелла.
Но на самом деле, даже этих выводов сделать из статьи нельзя. Причин много, выбирайте любую:
- Вы сами пишете, что железо у вас лучше, чем было использовано автором той статьи. То есть получается, что цифры воронки будут еще хуже.
- В отличие от той статьи, у вас помимо времени собственно сортировки зачем-то замерялось еще время ввода-вывода. Выяснить, в какой степени проведенные манипуляции являются бенчмарком алгоритма, а в какой — бенчмарком вашего накопителя, не представляется возможным.
- Мало того, что у вас в принципе очень отличается и железо и программная среда от использованной в первой статье, так вы еще и внятно не описали, какое вообще у вас железо. Вы тут во все стороны в истерике развешиваете ярлыки "люмпенов" и "не-программистов". Скажите пожалуйста сами, как стоит назвать человека, считающего, что "двухъядерник 2.8ГГц" — это исчерпывающее описание характеристик процессора. Или по-вашему, Atom C2550 и Core i5 7400T — это одинаковые "четырехъядерники 2.4ГГц"? Автор исходной статьи оставил конкретную модель своего ноутбука, а не абстрактный набор букв, не говорящий вообще ни о чем.
Все содержание заметки сводится к тому, что воронка сортирует непонятно какие данные на непонятно каком железе за 195 секунд. А какие-то другие — за 57. А третьи — за 3210.
Как на этом железе работают другие алгоритмы? Неизвестно — автор не удосужился измерить. Как воронка работает на другом железе? Тоже неизвестно — автор не удосужился предоставить референсную реализацию алгоритма или хотя-бы вменяемый исполнительный файл, который можно запустить на какой-либо современной платформе, а не только на музейном экспонате.
Единственное, что можно вынести из статьи — это то, что поведение воронки и правда похоже на O(n * log n). Ну круто, че. Только вот ни разу не удивительно, учитывая, что самым производительным у вас оказался вариант с воронкой глубины 1, который от обычной сортировки слиянием отличается деталями, не влияющими на асимптотику.
picul
27.05.2019 00:23+12Здравствуйте. Реализовал сортировку «воронкой» и сравнил с сортировкой слиянием, и результаты полностью противоположны Вашим — сортировка слиянием стабильно быстрее. Так что Вы определенно где-то ошиблись в тестировании.
P. S. Заранее предупреждаю — реализацией не поделюсь.
Sirion
27.05.2019 01:18+6Я придумал алгоритм, который превосходит оба перечисленных. Но пруфов не будет.
Pand5461
27.05.2019 00:23+2del
N — это не число элементов, а число сравнений?
Я вот ВООБЩЕ не понял
Pand5461
27.05.2019 08:16+4Статья — мусор и получает от меня минус.
Автор — тоже получает минус за откровенную ложь, попытки манипуляции и оскорбления в комментариях.
Кто-то что-то хочет сказать про неравные условия? Ничего подобного, я на хабре больше одного комментария в час ничего не пишу, так что в неравные условия С СОБОЙ никого не ставлю.
RussDragon
27.05.2019 02:25+2Тщетно пытаюсь разгадать тайну, почему автор всячески избегает демонстрации исходников. Страх того, что украдут и выдадут за свои? Страх опровержения изложенных результатов? Отсутствие оных как факт?
Столько вопросов и ни одного ответа…robert_ayrapetyan
27.05.2019 07:58+2А для меня тайна почему после всего сюра выше все настойчиво пытаются увидеть какие-то исходники…
Hardcoin
28.05.2019 21:06+1Внутренний психологический блок, скорее всего. Он считает, что прав и хочет это показать остальным. Любые мысли о постановке корректного эксперимента блокируются внутренним дискомфортом.
Gerrero
27.05.2019 07:14-3А что все так накинулись то? Вроде мысля то заслуживает внимания.
FDA847
27.05.2019 07:45-1В прошлый раз я задал аналогичный вопрос:
habr.com/ru/post/451550/#comment_20188340
И в результате теперь могу писать раз в 5 минут :-)Gerrero
28.05.2019 08:33-7Может ну их, этих неадевкатов? как-то насрать на карму и, в принципе, возможность писать комменты. Если всё быдло имеет право заминусить в хлам любую мысль, отличную от большинства, то и нет смысла вообще что-то писать )) А представьте что творится на уровне выборов во власть? На фоне этого, идея убрать выборы кажется более рациональной, чем игра в демократию.
Mikluho
28.05.2019 10:14+2Фокус в том, что неадекваты довольно быстро лишаются возможности минусовать. Я тут не мало срачей наблюдал, и случаев яростного отхабривания только из-за мнения исчезающе мало. Чаще всего наказывается форма коммуникации и настойчивость на откровенном идиотизме.
FDA847
28.05.2019 10:56-1Так поэтому давно и не пишу :-) После объединения гиктаймса и мегамозга с хабром все неадекваты лезут во все подряд статьи и гадят всем подряд. Нормального обсуждения, где есть различные точки зрения, я тут давно не видел. Тем кто пытается свою мысль донести, быдло рот затыкает тут же. Даже сегодня уже успели в карму нагадить :-)
Sirion
28.05.2019 10:59Такое случается, если излишне настойчиво пытаться донести точку зрения, которую при этом не можешь аргументировать.
FDA847
28.05.2019 11:04Ранее мне тут писали, что тут никто никому не должен! Быдло противоречит самому себе? :-)
Sirion
28.05.2019 11:06+4«Никому не должность» работает в обе стороны. Вы не должны никому ничего доказывать, но никто и не должен вас слушать.
Беда, которая вас постигла, чаще всего (хотя и не всегда) настигает людей, чья проблема — не инаковость точки зрения сама по себе, а специфический стиль общения.FDA847
28.05.2019 11:59-2Придираться Вы можете только к тилю автора. Мой стиль совершенно спокойный. Беда, сударь, у Вас в первую очередь в голове! Наведите там порядок, тогда, возможно, будете терпимее к чужому мнению! :-)
Во, уже снизу накинулись! Доводов нет никаких, пытаются чушь всякую нести!Sirion
28.05.2019 12:48+4Конечно, до автора поста вам ещё нужно долго расти вниз, но я бы не сказал, что ваш стиль нейтрален)
lair
27.05.2019 11:45+1А что все так накинулись то?
В комментарии выше есть ссылка на подробное обсуждение, почему.
Вроде мысля то заслуживает внимания.
Ну давайте попробуем разобраться. Какая конкретно мысль в этом посте "заслуживает внимания", и почему?
Gerrero
28.05.2019 09:03-6А в топку разборы. Я вообше не программист. Просто наблюдаю как «типа_программисты» срут в комментах. По большому счету, тут программистов процентов 20. Остальные тупо кодеры с раздутым ЧСВ.
lair
28.05.2019 11:08+5Вот, собственно, и наглядный пример за что. Сначала вы приходите с мнением, но когда вас просят это мнение аргументировать, вы немедленно отказываетесь это делать, и попутно еще и пытаетесь наехать на всех остальных. Собственно, автор поста ровно то же самое и устроил.
FDA847
28.05.2019 12:08-4Причём эти 20% как раз пишут по делу, а остальные 80% пытаются как-то потешить своё самолюбие, доказать самому себе, что они что-то стоят. Правильно ведь, если не получается реально самому чего-то достичь в жизни, надо других в говно втоптать! :-)
Аргументация никого не интересует. Наоборот, быдло пытается как можно быстрее заткнуть рот, что нормальные люди вообще писать не могли. Но так как у них по одному голосу за карму, то приходится провоцировать людей, чтобы других быдлогопов привлечь для затыкания рта.
Я ж говорю, тут давно помойка уже стала! Я уже год почти не ввязывался во всякие дискуссии, потому что реально обсудить вопрос никогда не удаётся. Но после того, как увидел, как откровенно травят автора, просто не удержался. Скоро перейду в режим read only, может оно и к лучшему.Mikluho
28.05.2019 13:01+6Вы, как и автор, довольно настойчивы в переваливании вины с себя на некое анонимное быдло, что есть весьма удобная позиция, сходная небезызвестному д'артаньянству :)
Для сравнения, по моим наблюдениям, в обсуждениях этой и ещё нескольких последних статей автора, большая часть комментаторов как раз программисты. Эти программисты как раз пытаются понять, что за идею пытается донести автор, но после очередного ведра помоев, изливаемых автором, начинает пробивать «раздражение» «идеальным стилем» автора.
Отдельно выделяются комментаторы типа вас или Gerrero, которые выражают сочувствие источнику помоев, а не тем, на кого они изливаются. В таком раскладе странно ожидать массового одобрения.
Hardcoin
28.05.2019 21:16+3На самом деле нет, не заслуживает. Для практиков существует общепринятый стандарт воспроизводимости экспериментов. Автор отказывается ему следовать потому что потому, без причин.
Либо это какое-то необычное когнитивное искажение (тогда нет смысла верить ему на слово), либо он пытается ввести в заблуждение. Я думаю, тут скорее первый вариант.
rybvv Автор
27.05.2019 08:07-7Ого! Мне карму до -1 опустили уже
Нет, уже до -4, и это не предел. Это обыкновенная травля охреневшим от безнаказанности анонимным быдлом, которое прекрасно знает, что оно именно быдло. За время моего бана в моих ветках появилось ТРИ коммента, сейчас их только в этой ветке 43! Ой, уже 44. Ой, уже 45! 46! И карма Ваша уже -5! После обнуления моей кармы мне за сутки накидали -16, после выхода из бана за треть суток нагадили до -27, так что ещё четыре плевка в карму, и я ВООБЩЕ буду лишён возможности сюда что-либо писать — даже в Песочницу! Вон, стадо визжит про «пруфы» — разве им пруфы нужны? Например, тому быдлу, кто здесь заявляло, что «гениям можно всё простить, даже если они будут плевать в рожу»? Нет, им КОММЕНТЫ нужны, чтобы срать туда антилайками, ибо они ТОЖЕ понижают карму. ЛЮБЫЕ комменты, вне зависимости от содержания. Их тема интересует? ЩАЗ! Как только мне окончательно заткнут хлебало, вся эта свора МГНОВЕННО умолкнет!
Но вот про исходники я реально не понял.
Ну и как ТЕПЕРЬ? :) По исходникам, я полагаю, должно бы быть немало вопросов! :)
valemak
Не знаю, видели ли Вы мой вчерашний ответ (я случайно затёр его при правке коммента), так что повторю:
А насколько эффективна сортировка воронкой при обработке малых массивов?
Я на это отвечал ещё в прошлой ветке: на малых массивах «пузырёк» выдерет ЛЮБОЙ алгоритм сортировки — именно потому, что он простой до неприличия и программируется в пять секунд. Мне же требовалось частая сортировка именно БОЛЬШИХ массивов — в десятки и сотни миллионов элементов, иногда в миллиарды. Потому и появилась «воронка».
Igor_ku
Зачем тогда мы учим как анализировать алгоритмы?
Понятия не имею! Виимо, затем, что из вас готовят не программистов, а быдлокодеров. :) Ибо вся эта дурацкая «сложность» для решения практических задач НАФИГ НЕ НУЖНА! Зато можно долго рассуждать про всякие идиотские «пределы Бреммермана», изображая из себя «умных людей».
Да, но это ведь делает не возможным разговор об алгоритме? Кто знает, от чего может алгоритм может дать сбой. Может просто подбор файлов такой?
А что о нём разговаривать? Там всё просто до неприличия! Воронка ловит любые восходящие или нисходящие подпоследовательности, и ловит предельно быстро, ибо сравнивает текущий элемент входного потока лишь с головой и хвостом списка, независимо от его размера, сокращая тем самым число необходимых последующих слияние MergeSort. Если повезёт — вообще до нуля. ВСЁ, БЛИН! ВЕСЬ АЛГОРИТМ! О ЧЁМ тут ещё разговаривать? Нет, нюансов реализации немало, но алгоритм-то здесь при чём? Он ведь ПРОСТЕЙШИЙ!
Так, я смотрю, тут опять уже стадо резвиться стало — осмысленных вопросов больше навскидку не вижу, так что остальное прокомментирую как-нить на досуге, в фоновом режиме.
Ну, всё — карма уже -28, и до перехода в режим «1 коммент в сутки» осталось совсем чуть-чуть. Собственно, я бы уже давно там был, если бы не 13 лайков за статью (в данный момент +13 -23). Быдло, вонючее быдло! И меня ещё кто-то спрашивал, почему я исходники сюда не выкладываю? :)Sirion
27.05.2019 08:51+6А вы не могли бы прислать фото своего лица в момент, когда пишете комментарии? Мне интересно, с каким выражением вы это делаете.
M00nL1ght
27.05.2019 11:17+3Понятия не имею! Виимо, затем, что из вас готовят не программистов, а быдлокодеров. :) Ибо вся эта дурацкая «сложность» для решения практических задач НАФИГ НЕ НУЖНА! Зато можно долго рассуждать про всякие идиотские «пределы Бреммермана», изображая из себя «умных людей».
Это просто 5+. Действительно нафига все это нужно?) формулы там какие то, доказательства пфф. Из серии все вокруг дураки один я умный
lair
27.05.2019 11:47+3Нет, им КОММЕНТЫ нужны, чтобы срать туда антилайками, ибо они ТОЖЕ понижают карму
Вот классический пример ложного утверждения. Нет, на хабре рейтинг комментария никак, вообще никак не влияет на карму.
selotec
27.05.2019 09:06+7Махровый Данинг-Крюгер и позиция жертвы.
Сначала долго ломался, чтоб показать исходники, а теперь "ну и как мне что-то выкладывать и обсуждать с одним комментарием в сутки". Хочется верить, что тролль или очередной социальный экспериментатор.M00nL1ght
27.05.2019 11:22как вы думаете в какой точке на кривой Даннинга — Крюгера находится автор? Пик глупости или долина отчаяния?)
Chuvi
27.05.2019 12:55+1автор на своем сайте активно хвалится банами на многих технических форумах. Недооцененный гений, не иначе.
selotec
27.05.2019 13:34+1На самом деле вся история напоминает относительно недавнюю тут статью про чувака, который свою операционку писал. Вероятно, примерно так же все начиналось.
ktotaika
27.05.2019 11:56+4Статья — мусор, минус поставить, увы, не могу, кармой не вышла. Но стрелочку вниз курсором погладила.
shapovalex
27.05.2019 13:06+3Небольшое исследование
Вот тут есть картиночка как работает сортир
sint.wc.lt/sortir.htm
Если коротко, то получается один проход по списку, сравнение с существующими бакетами, вставка в начало или конец бакета. Потом отсортированные бакеты сливаются.
Ну так вот, для такого алгоритма легко построить «худший случай».
Типа такого
1 100 2 99 3 98 4 97 5 96 6 95 7 94 8 93 9 92 10 91
Ну и так далее
То есть на выходе мы получим n/2 бакетов
Мерж этих бакетов O(n), каждый мерж — тоже O(n) — итого худший случай О(n^2)
То есть воронка не лучше, чем quicksort.
Вдобавок ко всему воронка требует для работы связанных списков, что дает большой оверхед по памяти.
И в этом случае воронка хуже quicksort.Pand5461
27.05.2019 13:50+2То есть на выходе мы получим n/2 бакетов
Мерж этих бакетов O(n), каждый мерж — тоже O(n) — итого худший случай О(n^2)Нет. Слить их можно так же, как и в обычной сортировке слияниями — попарно за время O(n logn).
shapovalex
27.05.2019 14:17-1Количество слияний в сортировке слиянием: 1 + 2 + 4 + log2(n). Итого растет со скоростью O(log n)
Количество слияний тут: n/4 + n/8 + n/16. Итого растет со скоростью O(n)
Кстати, предобработка и распихивание по бакетам тоже имеет квадратичную сложность.
Проход по списку O(n). Количество сравнений от 1 до n/2 — 1. Итого на выходе имеет выхлоп O(n^2).Dim0v
27.05.2019 15:01Слияние тут работает аналогично слиянию в MergeSort. С аналогичной асимптотикой.
Посмотрите предпоследний абзац здесь #comment_20205630
Pand5461
27.05.2019 15:07Количество слияний в сортировке слиянием: 1 + 2 + 4 + log2(n).
Вы логарифм с экспонентой точно не перепутали?
Количество слияний тут: n/4 + n/8 + n/16. Итого растет со скоростью O(n)
Да
Проход по списку O(n). Количество сравнений от 1 до n/2-1
Нет, сливаются же списки по 2 элемента, потом по 4, потом по 8 и т.д. На каждом проходе слияние O(n/2k) списков по O(2k) элементов, как и в "классике". Всего "удвоений" списков O(logn). Итого O(nlogn) сравнений.
shapovalex
27.05.2019 15:30+1А, ну да. n слияний, лесенка log n уровней.
Все равно я не понимаю откуда взялась сложность n log n, если мы на каждом шаге не можем найти бакет «куда пристроить» элемент (напомню я рассматриваю худший случай вида 1 100 2 99 3 98 4 97 5 96 6 95 7 94 8 93 9 92 10 91)
То есть каждый новый элемент нельзя пристроить ни в начало, ни в конец существующего бакета.
И надо или создавать новый бакет или делать слияние.
И тогда получится или n линейных слияний, или n сравнений для каждого элемента.Dim0v
27.05.2019 15:35И надо или создавать новый бакет или делать слияние.
Создаем новый бакет. Это за константу делается.
И тогда получится или n линейных слияний
Не получится, потому что см. пункт 1. Мы не сливаем, мы просто создаем новый бакет
или n сравнений для каждого элемента.
Не n. Мы сравниваем только с одним текущим бакетом. Т.е. по 1-2 сравнения на элемент выходит.
Для худшего случая в конце у нас будет n/2 бакета по 2 элемента.
shapovalex
27.05.2019 15:41Для худшего случая в конце у нас будет n/2 бакета по 2 элемента.
Вот именно.
По-моему это противоречит
Мы сравниваем только с одним текущим бакетом
Сравниваем то мы со всеми предыдущими (ничего не придумываю — картинка с его сайта об этом говорит). А вдруг среди них найдется такой куда пристроить элемент можно.
P/S/ Хотя в Вашей интерпретации там действительно n log n. Не уверен, что автор это понимает и имел ввиду)Dim0v
27.05.2019 16:03+1Картинка с его сайта не соответствует его текущей реализации. Сейчас у него глубина воронки 1. Т.е. пристроить текущий элемент пробуем только к одному списку. Если не получилось, то этот список отправляем в буфер и больше не трогаем. А элемент заносим в новый пустой список и работаем дальше с ним.
От воронок осталось одно название. На деле входной поток просто разбивается на отсортированные подпоследовательности, которые потом сливаются мердж-сортом.
Pand5461
27.05.2019 16:29Сравниваем то мы со всеми предыдущими
Нет, сравниваем только с двумя последними. Списки воронки вводятся так, что в каждом следующем голова меньше головы предыдущего, "хвост" (последний элемент) больше хвоста предыдущего. Название "воронка" отсюда и идёт.
Pand5461
27.05.2019 21:42+1Раз уж всё равно прочитал авторское мнение по этому вопросу, поправлюсь.
Пристраивать предлагается, действительно, в любой список воронки, а не только в последний. Но, т.к. головы и хвосты списков отсортированы, со всеми предыдущими можно и не сравнивать, двоичным поиском пристроить можно за O(logm) операций, где m — "глубина" воронки (число списков). Так что встраивание нового элемента даже в "n/2 бакета по 2 элемента", если не тупить, в квадратичную асимптотику не скатывается.
Но там глубину ещё и предлагается ограничить сверху (в конечном счёте, до единицы), поэтому даже со всеми сравнивать — будет O(1).
Dim0v
27.05.2019 14:51+3сравнение с существующими бакетами
Не совсем. Сравнение только с одним текущим бакетом, а не со всеми. Если к нему пристроить не получается, то текущий отправляется в "буфер", а очередной элемент добавляется в новый пустой бакет.
Изначально — да, гениальная задумка автора была похожей — завести несколько бакетов (не динамически добавлять новые, а статически задавать "глубину воронки") и по ходу чтения пристраивать очередной элемент к концу одного из бакетов. Если ни к одному пристроить не получилось — сливаем 2 самых маленьких и пихаем наш элемент в образовавшийся пустой бакет.
Но в итоге он осознал, что это работает плохо, поэтому в своем сортире реализовал вариант с одним бакетом. Читаем данные, по ходу пристраиваем их к бакету. Если пристроить не вышло — откладываем текущий бакет в "буфер", как он это назвал и продолжаем читать дальше в новый бакет. В конце в "буфере" будет набор отсортированных бакетов, которые он сливает MergeSort-ом.
В конечном варианте, асимптотика аналогична асимптотике MergeSort-а.
Чтение за O(N) т.к. всего у нас N элементов и каждый из них пристраивается за O(1): пристройка к существующему бакету — очевидно, константа (если бакет реализован связным списком как у него). Перенос бакета в "буфер" — тоже константа.
А после этого мы просто оказываемся в ситуации "MergeSort посреди выполнения". Для хороших данных — ближе к концу выполнения. Для плохих — ближе к началу. Но в общем случае для завершения сортировки MergeSort-у потребуется O(N * Log N) времени. Не О(n^2).
Изначально у нас К бакетов. Мы можем их попарно слить друг с другом за О(n). После этого шага у нас количество бакетов уменьшится в 2 раза. Соответственно, всего на слияние всех бакетов в один потребуется Log2 K шагов. Т.е. общая асимптотика слияния будет O(N * Log К), а учитывая, что в худшем случае К = O(N), получаем асимптотику O(N * Log N)
В общем, алгоритм не ужасен. Он правда работает. Местами как MergeSort, местами даже лучше. Ужасен автор) Ну и сам алгоритм, хоть и не ужасен, но и явно не дотягивает до общепринятых на сегодняшний день. А потому применение его не оправдано практически нигде.
Sanovskiy
27.05.2019 15:24+1Вся проблема в том, что автор несколько… токсичен. За что и огреб.
shapovalex
27.05.2019 15:38Да ну, даже не в этом беда. Проблема в непонимании темы.
Я знаю нескольких людей, которые умеют общаться только матом и во время спора с ними ты будешь чувствовать себя гавном. Но они умеют донести хорошие идеи в том числе и матерными аллегориями.
И когда сталкиваешься со сложными задачами или имеешь неоднозначные решения все равно идешь к ним.
А тут сплошные оскорбления и ни слова по делу.
GCU
27.05.2019 15:38Один лишь этот комментарий более информативен, чем несколько статей автора.
Если я правильно понял — то это модификация сортировки слиянием, которая более рационально использует уже упорядоченные последовательности (в том числе и в обратном порядке)
P.S. Использование связного списка обычно приводит к промахам кэшаRussDragon
27.05.2019 16:02А на самом деле автор в своей песочнице так и пишет:
Сортировка воронкой является существенно улучшенным вариантом алгоритма сортировки слиянием.
sint.wc.lt/sortir.htmGCU
27.05.2019 16:23Спасибо за ссылку. Судя по анимированной картинке там — я ничего не понял и алгоритм непонятно как работает :(
Igor_ku
27.05.2019 19:46+2Вот, за такое объяснение мой профессор поставил бы зачёт. Сразу понятно, что имеется ввиду и что вы разбираетесь в теме.
А автор получил бы кол на экзамене и отправилася б повторять алгоритмы ещё разок :)
Sanovskiy
28.05.2019 01:09Знаете, самый ужасный способ сортировки, который я видел, это сортировка через таймауты в JS. После него меня уже ничего не может поколебать. После того «кода» я слово «сортировка» воспринимаю с содроганием.
playermet
27.05.2019 16:37+1Автор, смотри, я изобрел свой алгоритм сортировки, в сравнении с ним твой алгоритм — ничто. У него O(n) для всех случаев, и на том же проце что и в твоих тестах с теми же данными отрабатывает в 7 раз быстрее. Деталей не расскажу, восхищайся мной.<//sarcasm>
GCU
27.05.2019 17:45Тесты первой группы:
0: N=2602009514 T=26 sec
1: N=2602148436 T=26 sec
2: N=2601943056 T=26 sec
3: N=2602055129 T=26 sec
4: N=2601888286 T=26 sec
5: N=2602105643 T=26 sec
6: N=2601928733 T=26 sec
7: N=2601947256 T=26 sec
8: N=2601891575 T=23 sec
9: N=2602105643 T=26 sec
0-9: N=29495155841 T= 294 sec
Как-то очень уж ровненько и по времени, и по числу сравнений (их вообще нет, на самом деле).
Тесты второй группы:
0: N=199999998 T=20 sec
1: N=1923669691 T=19 sec
2: N=1683854900 T=16 sec
3: N=1480233649 T= 14 sec
4: N=1249780062 T=12 sec
5: N=996602000 T= 9 sec
6: N=666000198 T= 6 sec
7: N=340000016 T=3 sec
8: N=99999999 T=1 sec
0-8: N=11462881951 T= 114 sec <//sarcasm>
P.S. А ещё он потребляет 16ГБ ОЗУ, но то мелочи :)RussDragon
27.05.2019 18:12+2Лапуль, вы пишите ЕРЕСЬ! Я только что доработал алгоритм АВТОРА и убрал оттуда ГЛУПЕЙШИЕ ошибки! Проверял на процессоре Intel.
Тесты первой группы:
0: N=2602009514 T=13 sec
1: N=2602148436 T=13 sec
2: N=2601943056 T=13 sec
3: N=2602055129 T=13 sec
4: N=2601888286 T=13 sec
5: N=2602105643 T=13 sec
6: N=2601928733 T=13 sec
7: N=2601947256 T=13 sec
8: N=2601891575 T=13 sec
9: N=2602105643 T=13 sec
0-9: N=29495155841 T= 147 sec
Прям совсем ровненько по числу сравнений (их почти нет) и по времени
Тесты второй группы:
0: N=199999998 T=10 sec
1: N=1923669691 T=9 sec
2: N=1683854900 T=8 sec
3: N=1480233649 T=7 sec
4: N=1249780062 T=6 sec
5: N=996602000 T=4 sec
6: N=666000198 T=3 sec
7: N=340000016 T=1 sec
8: N=99999999 T=0 sec
0-8: N=11462881951 T= 57 sec <//sarcasm>
P.S. Потребляет всего 128 МБ оперативной памяти (у меня на компьютере больше нет).
Так что можете ВЫКИДЫВАТЬ TimSort и воронки! МОЙ метод снисходящего водопада ПОКАЗЫВАЕТ результаты в 1,5-2 раза лучше!GCU
27.05.2019 18:25Почему вы называете SSD диск процессором? :)
RussDragon
27.05.2019 18:26Вы видимо в жизни НИЧЕГО СЛОЖНЕЕ a=b+c не писали!
GCU
27.05.2019 18:32Ибо вся эта дурацкая «сложность» для решения практических задач НАФИГ НЕ НУЖНА!
:)
oam2oam
27.05.2019 22:09Очень интересное обсуждение… во всех смыслах. Мне стало интересно и я почитал с чего все началось. И вот какой момент возник — хотя именно в этой статье идет сортировка чисел, но изначально была, как я понял сортировка строк. И вот тут такое вспомнилось — оказывается со строками не все так просто — приходится в оценке сложности учитывать длину строк! И все приведенные оценки это не делают — там идет только оценка числа сравнений. А если строки длинные? Так вот для таких-то случаем есть алгоритм на практике линейной сложности относительно числа… входных символов, а не числа строк и их длин!
К сожалению, доказательство этого мне не известно, но на практике его реализация действительно работала именно так, причем использовалась она при построении словарей — ну то есть добавлении, удалении, поиске. И все операции, еще раз подчеркну, линейные по числу входящих символов! Вот так-то, а тут O(n log n)…lair
27.05.2019 22:27+1приходится в оценке сложности учитывать длину строк!
Зависит от того, что именно вы оцениваете по сложности. Автор утверждает, что у него универсальный алгоритм, их принято оценивать, считая сравнения двух элементов за константу.
Так вот для таких-то случаем есть алгоритм на практике линейной сложности относительно числа… входных символов, а не числа строк и их длин!
Но вообще я не понимаю, в чем отличие сложности "относительно числа входных символов", а не "числа строк и их длин".
при построении словарей — ну то есть добавлении, удалении, поиске
Что такое "словарь"? Обычно в таких случаях речь идет уже не об алгоритме, а об эффективной структуре данных, и в зависимости от требований могут быть более эффективными разные структуры. Например, для самого простого "словаря", ака хэштаблицы, ожидаемое время на операцию (амортизированное) — O(1).
oam2oam
28.05.2019 06:57+1Да, автор так пишет, но из прочтения первой статьи и, особенно, комментарий, у меня сложилось мнение, что это специализированный случай именно со строками. И да, это был вариант burstsort, но только это был 1993 год… Что же до словаря — это было применено для словарей в некоей системе, в которой были очень большие строки, так что в оценках приходилось учитывать длину строк, поэтому никакие O(1) не могли быть (строку тоже надо просканировать)…
Вот сочетание указания автора на большие строки и заявление что у него лучший алгоритм и напомнило мне, что бывает и не так…lair
28.05.2019 11:05+1у меня сложилось мнение, что это специализированный случай именно со строками
Но нет. Автор алгоритма еще раз это подчеркнул.
И да, это был вариант burstsort, но только это был 1993 год… Что же до словаря — это было применено для словарей в некоей системе
Я же говорю, если речь идет о словаре, значит, речь идет о структуре данных (и становится не понятно, а зачем вам вообще процесс сортировки). Вам нужен просто случайный доступ? Возьмите хэштаблицу, у нее доступ к элементу за O(1) + O(n), где n — длина строки. Вам нужен доступ к сортированным последовательностям? Возьмите trie, у которых доступ к элементу за O(n), где n — та же длина строки. И если что, trie известны с конца пятидесятых.
rybvv Автор
28.05.2019 08:09-2После бурных вчерашних визгов ветка практически затихла. Карма тоже приостановилась на -45 (когда я её обнулял, было -42, так что это рекорд), рейтинг тоже достиг рекордных -89.8, но вот энтузазизьм у стада явно пропал. Мало того: появились какие-то признаки попыток обсуждения алгоритма! Не тупого пинания ногами, не идиотских отсылок ко всяким там Кнутам, а реального обсуждения! Паломничество на мой сайт продолжается (особенно на страничку Хабра), хотя и не такое активное. Ну, что же — «для закрепления успеха» даю сюда обзор вчерашних комментов (в сокращении):
lair
Ну так что, rybvv, раз вы снова не в read-only, соблаговолите, может быть, объяснить разницу между вашим утверждением и, гм, общепринятой терминологией?
Так и быть, разок соблаговолю:
а) Термин «общепринятая терминология» вовсе не означает правильная". Тем более, что он даже не уточняет, КЕМ «общепринятая». Долгое время стада баранов считали, что Земля плоская, и вообще покоится на трёх китах. Огромнейшие стада баранов УЖЕ НАШЕГО времени веруют в клинические религиозные бредни, причём РАЗНЫЕ, так что у каждого из этих стад «общеприняты» несколько разные «терминологии».
б) Теперь по поводу маразма с «брутом»: я полагаю, что у НОРМАЛЬНЫХ людей такая «терминология» не может быть «общепринятой». Тем не менее, как оказалось, в определённых кругах она распространена довольно широко — банда тупорылых идиотов «обучила» даже Google, и он теперь действительно переводит «полный перебор» как «brute force». Но вот занятно: обратный перевод У ЭТОГО ЖЕ ПРИДУРКА звучит уже как «грубая сила, насилие»! Яндекс же переводит «полный перебор» как «exhaustive search» или «full search», Bing вообще как «full bust», что тот же Google считает «полным бюстом». Мало того: НИ ОДНА СВОЛОЧЬ из ЭТИХ ЖЕ САМЫХ переводчиков не переводит «полный поиск» или «исчерпывающий поиск» как «brute force»! Нет, здесь уже предлагается исключительно «exhaustive search» или «complete search»! Вопрос: У КАКОГО СТАДА БАРАНОВ это «общепринято»?
Politura
michael_vostrikov сделал реализацию на C++, сравнил ее с QuickSort, TrimSort и MergeSort
Востриков сделал ГОВНО, а не «реализацию»! По которому я его долго возил носом прежде, чем он заткнулся (надеюсь, окончательно).
Dim0v
А чего так скромно-то? Давайте сразу на сто. А лучше на тысячу.
А того, что я писал в прошлой ветке, что время чисто сортировки САМОЕ маленькое из трёх этапов: чтение, сортировка и запись результатов. А для второй группы «тестов» смело можно делить как раз и на сто, и на тысячу, и больше — особенно для первого и последнего из них.
Sirion
А вы не могли бы прислать фото своего лица в момент, когда пишете комментарии? Мне интересно, с каким выражением вы это делаете.
Да что же ещё может быть интересно быдлу, которое готово жопу лизать любому титулованному гению, даже если тот будет «плевать в рожу»? Ну, посмотрите у меня на морде моего сайта. Вот с тем самым выражением и делаю! ;)
Chuvi
goto в си-шном коде? Дяденька, на дворе 2019 год, а не 1989. Ловите минус, авось про существование календаря вспомните.
Совершенно верно, лапуль: «goto в си-шном коде»! Я уже много лет гоняю снобов импотентных, которые рожу воротят от goto, которые для даже для тупого выхода из вложенных циклов заводят какие-то дурацкие переменные и как-то их анализируют. Лапуль, а как ВОЙТИ во вложенный цикл без goto — не подскажете? Вот, скажем, задача коммивояжёра многодневная, и может быть отложена в любой момент. Как ПРОДОЛЖАТЬ расчёт будете после откладывания, «программист» хренов? Вот именно, что «на дворе 2019 год, а не 1989» — тогда на планете Земля ещё водились программисты!
lair
Вот классический пример ложного утверждения. Нет, на хабре рейтинг комментария никак, вообще никак не влияет на карму.
Вы что, создатель софта Хабра, лапуль? Тогда поясните, почему у многих пользователей карма имеет ДРОБНОЕ значение? Вы утверждаете, что карму можно изменить лишь так, как это написано в описании? А я вот утверждаю, что это есть БРЕХНЯ! Сам факт дробной кармы ДОКАЗЫВАЕТ это! Ну, хорошо, ПОВЕРИМ Вам! На сто процентов. На двести. На триста. Тогда вопрос: ЗА ЧТО быдло анонимное нагадило в карму пользователю FDA847? Не мне — это понятно любому дебилу — а ему? Если я правильно помню, вчера у него была карма +7, сегодня уже -6. То есть ТРИНАДЦАТЬ анонимных гондонов насрали ему в карму! Ненамного меньше, чем мне! Так ЗА ЧТО, лапуль? Моя версия: за то, что он НЕ быдло, и ТОЛЬКО за это! Ваша версия? ;)
shapovalex
То есть на выходе мы получим n/2 бакетов. Мерж этих бакетов O(n), каждый мерж — тоже O(n) — итого худший случай О(n^2). То есть воронка не лучше, чем quicksort.
Ну вот ЧТО тут сказать? Только повторить вслед за Лавровым его знаменитую фразу.
Dim0v
Изначально — да, гениальная задумка автора была похожей — завести несколько бакетов (не динамически добавлять новые, а статически задавать «глубину воронки») и по ходу чтения пристраивать очередной элемент к концу одного из бакетов. Если ни к одному пристроить не получилось — сливаем 2 самых маленьких и пихаем наш элемент в образовавшийся пустой бакет.
Не было у автора никогда столь идиотской «задумки» — это он просто алгоритм описывал, не перегружая его лишними подробностями, оставив их для раздела «реализация». И то некоторые придурки соплями исходили: откуда буфер взялся! А «вариант с одним бакетом» был реализован по совершенно другой причине, также описанной в статье.
В конечном варианте, асимптотика аналогична асимптотике MergeSort-а.
Да, но с одним нюансиком: у MergeSort она такая ВСЕГДА, а у «воронки» вероятность нарваться на подобный входной поток исчезающе мала!
А после этого мы просто оказываемся в ситуации «MergeSort посреди выполнения».
Ну да, я так и писал: слияние работает как бы «по прерываниям» — чтение входного потока просто приостанавливается.
В общем, алгоритм не ужасен.
Мало того: ИДЕАЛЕН! Это же не какое-то там говно по кличке TimSort! :)
Ужасен автор
Для визжащего трусливого быдла — несомненно! А вообще он белый и пушистый. :)
Ну и сам алгоритм, хоть и не ужасен, но и явно не дотягивает до общепринятых на сегодняшний день. А потому применение его не оправдано практически нигде.
Да неужели?! И ДО КАКОГО ЖЕ ИМЕННО он «недотягивает» и ПОЧЕМУ? Даже Востриков сказал, что он лучше Квика! А Вы сказали, что лучше MergeSort. Так ДО ЧЕГО ЖЕ он «не дотягивает»? До этого поганого «тимсорта»? Или, прости Господи, «богосорта»? У кого там опять что «общепринято»? Огласите весь список, пжалста!(с) ;)
Картинка с его сайта не соответствует его текущей реализации. Сейчас у него глубина воронки 1.
Картинка СООТВЕТСТВУЕТ его текущей реализации! Воронка размером в один список — это ТОЖЕ воронка! Автор исследовал РАЗНЫЕ размеры и пришёл к выводу, что на скорость это практически не влияет. А раз так, воронка в один список проще реализуется — только и всего! Всё это, кстати, ТОЖЕ описано в заметке, С САМОГО НАЧАЛА! И что при воронках размером в 4, 8, 16, 64 или любом другом входной поток ТОЖЕ «просто разбивается на отсортированные подпоследовательности, которые потом сливаются мердж-сортом».
GCU
Если я правильно понял — то это модификация сортировки слиянием, которая более рационально использует уже упорядоченные последовательности (в том числе и в обратном порядке)
Господи! Кто-то сдох? Не прошло и полгода! Да, да, да, всё именно так! И, насколько я помню, это написано В ПЕРВЫХ ЖЕ СТРОЧКАХ моей заметки!
P.S. Использование связного списка обычно приводит к промахам кэша
Это разве что у тупорылых и криворуких «реализаторов»! ;)
Судя по анимированной картинке там — я ничего не понял и алгоритм непонятно как работает.
Так, может, СНАЧАЛА нужно понять, а уж ПОТОМ вонять про всякие «промахи»? ;)
Pand5461
Нет, сравниваем только с двумя последними.
С какими ещё «двумя последними»? Со всеми списками воронки, пока не пристроим элемент или пока воронка не кончится.
playermet
Эмм, вы целую неделю писали реализацию простейшего алгоритма сортировки, который знали вдоль и поперек (ибо сами его изобрели), и подаете это как что-то позитивное? Ни в коем случае не сочтите это за хвастовство, но если даже если я выберу сложнейший из общеизвестных алгоритмов сортировки и предварительно разберусь в нем, то на написание реализации у меня уйдет максимум часы, а на действительно простейшие хватит и десяти минут.
Да, милок, «целую неделю». Но, во-первых, это не значит, что я сидел и писал эту программу ВСЮ неделю — я писал в свободном режиме, когда есть настроение, ибо я писал ДЛЯ СЕБЯ. Во-вторых, эти Ваши слова — какое же это «хвастовство»? Это дурость обыкновенная — чуть ли не самооговор! За эти «максимум часы» Вы напишете разве что говно, аналогичное этим двум «реализаторам», один из которых умудрился изуродовать алгоритм (как он говорил, «строго по описанию») до квадратичной сложности! Потому как там МАССА нюансов реализации, о которых эти два придурка вообще не задумывались, даже в плане постановки задачи! И Вы наверняка не задумывались — Вы даже не передставляете. насколько медленно, насколько въедливо пишет программы НАСТОЯЩИЙ профессионал, какие неожиданные особенности их поведения он там обнаруживает! Мне не раз доводилось любоваться их работой, и мне до такого уровня не дорасти НИКОГДА — просто по складу характера. А Вы даже и не пытаетесь — у Вас технология «тяп-ляп, спихнул и забыл». Кстати, почему-то так и нет вопросов ко мне по коду, не считая одного, совсем уж мелкого. С чего бы это?
А что касается людей которые вы «вежливо» обозначили стадом, так никому не впало тратить неизвестное количество времени на понимание мутного алгоритма, после чего еще неделю своей жизни забесплатно тратить на его реализацию, и тем более делать это ради доказательства кому-то неизвестному чего-то там в интернете.
Совершенно верно! И поэтому они тратили время на то, чтобы срать комментами в ветках и антилайками в карму — правильно? Весьма достойное занятие для «сообщества разработчиков»! ;) А сейчас это стадо ломанулось ко мне на сайт, и я много лет знаю, что быдло ведёт себя в подобных ситуациях ИМЕННО ТАК!
Сортировка подсчетом? Ну это совсем чит уже.
ФИГОТОМ! Какой-то козёл какую-то бредятину проблеял — и Вы тут же радостно оперируете ею как фактом? ;)
GCU
А ещё он потребляет 16ГБ ОЗУ, но то мелочи
Не надо БРЕХАТЬ, лапуль! ;) Тем более, что я русским языком говорил, что у меня ФИЗИЧЕСКИ 2 гига ОЗУ!
robert_ayrapetyan
Т.е. он вас помнит, чтоб у вас от безнаказанности крышу не снесло, ясно? Вообще персонаж интересный (с медицинской точки зрения). От писем Марку Цукербергу на русском языке, до плагиата на Маяковского.
Ну да, все головожопые одинаковы: опять роются в моём сайте, опять что-то вынюхивают. Ещё 27.08.2009 10:24 я писал: «Основное внимание они обращают не на тему, а на автора (одно время мне было забавно наблюдать за всплесками интереса к нашему сайту). У автора выискиваются разные „козюлины“ с тем, чтобы сказать: как может этот идиот, который даже [содержимое найденной козюлины] вообще что-то говорить о [название темы]». Один в один! И по-прежнему у визжащих лишь две версии: «ржача» и «медицинская».
И в качестве компенсации начинается яростный наброс на оппонентов.
Да какие вы, в задницу, «оппоненты»? У оппонентов АРГУМЕНТЫ имеются в наличии! ;) И какие «яростные набросы»? Вытравливание всегда идёт на полном автопилоте, это даже думать не мешает!
Bhudh
Резонёрство
Да-да, и об этом писал: мне не раз доводилось видеть Полиграфов Полиграфовичей, цитирующих Булгакова и Амвросиев Амбруазовичей, цитирующих Стругацких.
Pand5461
со всеми предыдущими можно и не сравнивать, двоичным поиском пристроить можно за O(logm) операций, где m — «глубина» воронки (число списков).
Да, были такие предложения ещё на Фейсбуке, где я первый раз опубликовал алгоритм — ещё там я сказал, что не вижу никакого смысла: какой двоичный поиск при ничтожном размере воронки? Что там блох ловить? Кто знает, в какой именно список элемент пристроится? Никто! Тем более, что воронка даже в 64 списка (это я только для исследования, какой размер оптимальный — реально я полагал, что оптимум лежит где-то в районе 4-16 списков) слишком мала, чтобы заниматься двоичным поиском. А оказалось, что всё это, по большому счёту, вообще онанизм, и на производительность практически не влияет, и потому оставил в воронке всего один список, как самый простой вариант.
oam2oam
Да, «изначально была сортировка строк». И про длинные строки говорилось не раз. По большому счёту, длина не имеет значения: даже для длинных строк вероятность проверки длинной последовательности символов совсем невелика. У меня стоит ограничение на длину строки 16К или даже 64К, но даже если исходный массив будет состоять из большого числа длинyых одинаковых строк, подтормаживание почти незаметно (моделировал).
Нет, это не «специализированный случай именно со строками». Автор, как правило, сортирует СТРУКТУРЫ данных, которые можно рассматривать как строки. Кстати, а что такое «очень большие строки»? Я уже всласть поиздевался над одним Инетовским предложением сортировки, где говорилось про «невероятно длинные строки размером в 3000 символов». :) И у автора действительно «лучший алгоритм» — ещё и потому, что на размер строк ему столь же наплевать, как и на остальные нюансы — ему НЕ ТРЕБУЕТСЯ «выбирать опорный элемент» или заниматься аналогичными глупостями.
oam2oam
под длинными понимались строки в среднем 1 млн знаков, причем вероятность совпадения половины строки более 0.01.
Многовато. :) Но всё равно непринципиально — я ведь и сравниваю строки именно посимвольно. И любой другой алгоритм, основанный на сравнениях, будет сравнивать точно так же. В моём коде для таких строк нужно поменять
MAXELEMENTSIZE = 1024 * 32, // максимальный размер элемента данных
на что-то типа
MAXELEMENTSIZE = 1024 * 1024 * 32,
Хотя здесь уже лучше использовать 64-разрядную арифметику. Или, скорее всего, просто поменять структуры данных — у меня длина строки более 16К — это почти всегда ошибка в данных. Думаю, нечто подобное можно сделать и в Вашем случае.oam2oam
28.05.2019 08:21+1под длинными понимались строки в среднем 1 млн знаков, причем вероятность совпадения половины строки более 0.01. Так что для целей анализа длина строки имела все же значение — не очень понимаю, как можно сравнить строки быстрее чем по-символьно, а если так, то при указанных выше значениях надо выполнить примерно 500_000 * 0.01 = 5000 операций сравнения на строку, чем уже нельзя пренебрегать.
Sirion
28.05.2019 09:00как можно сравнить строки быстрее чем по-символьно
заранее посчитать хеши, напримерoam2oam
28.05.2019 09:01речь идет о времени всей сортировки, включая предобработку… А то бы можно всегда было за 1 операцию делать :) У вас подсчет хэша заранее приводит к полному просмотру всех строк, что излишне…
Dim0v
28.05.2019 10:24+1Вот я посчитал заранее хеши двух строк. Как теперь мне определить, какая из них лексикографически меньше?
47bce5c74f589f4867dbd57e9ca9f808
08f8e0260c64418510cefb2b06eee5cdSirion
28.05.2019 10:44Да, я что-то психанул. Спросонок прочитал «сравнить» как «определить равенство», не вдумываясь в контекст.
malkovsky
28.05.2019 15:14Вообще-то можно: но нужно посчитать не один хеш, а хеши всех префиксов. Для полиномиального хеша это можно сделать за линейное время от длины строки. Дальше бинарным поиском найти позицию, где хеши перестают совпадать, если коллизий хеша не произошло, то это означает, что мы нашли позицию, что до нее все символы совпадают, а символы в этой позиции различаются — по нему и надо сревнивать. Итого — предподсчет за линейное время с линейной доп. памятью дают возможность делать сравнение за логарифм от длины меньшей из строк. Ну и не стоит забывать, что могут произойти коллизии, не совсем понятно, что делать в этом случае
GCU
28.05.2019 16:05+2И чем это лучше префиксного дерева (trie) — тем, что используются хеши? :)
malkovsky
28.05.2019 19:32+1Я лишь указал на возможность использования хешей в случае, если нам нужно сравнивать строки много раз, понятно, что trie в подавляющем большинстве случаев предпочтительней.
Допустим мы сортируем n строк длины L над алфавитом размера A.
1) Использование обычный сортировки со сравнением хешами требует от нас предподсчета за O(nL) и последующей сортировкой за O(n log(n)log(L))
2) При использовании trie построение происходит за O(nL * f(A)), где f(m) — сложность добавление в словарь размера, который сопоставляет некоторым буквам алфавита переходы в дереве. Наверно здесь можно считать, что это O(1) за счет хеш-таблиц. Дальше нужно отсортировать переходы в каждом узле O(T*log(d)), где T — итоговое число узлов в trie, а d — максимальная степень (учитываем, что суммарное количество сортируемых элементов — это Т), в худшем случае O(nL log(A)), вывод будет тривиальным за O(T). Можно обойтись без хеш-таблиц и сортировать сразу на месте с помощью бинарных деревьев или кучи, оценка худшего случая от этого не изменится, т.е. все еще O(nLlog(A)), но скорее всего будет лучше, так как trie эффективно во многом благодаря тому, что T сильно меньше nL.
В итоге получаем O(n log(n)log(L)) против O(nL log(A)), поправьте меня, если я где-то обсчитался. Вторая оценка более грубая (T заметно меньше nL, «средняя степень» заметно меньше А), но даже при всем при этом совершенно не очевидно, что trie будет эффективней например при сортировке слов, составленных из иероглифов, т.е. когда размер словаря заметно больше длины слова.GCU
28.05.2019 22:04+1Размер алфавита можно сократить заменив его на несколько букв из алфавита по-меньше. Например вместо 256 «букв» использовать пары по 16 «полубукв» и т.д. сводя к поразрядной (даже к побитовой) сортировке с линейной сложностью.
P.S. Автор — тут ещё один алгоритм — претендент на звание ИДЕАЛЬНЫЙ, трон под «воронкой» шатается :)malkovsky
28.05.2019 22:49+1Вы совершенно правы, действительно так можно делать, но стоит учитывать, что снизив размер словаря с 256 до 16 указанным образом, длина каждого слова увеличится в два раза. Соответственно, чтобы снизить размер словаря до 2 нужно увеличить размер каждой строки в log_2(«размер словаря») раз, что не улучшает асимптотику. Более того, поразрядная сортировка — это тоже самое, что сортировать числа как строки с помощью префиксного дерева. Сортировка подсчетам действительно линейна по количеству сортируемых чисел, но в ней проходит несколько стадий, количество которых зависит от количества цифр в числах, т.е. зависит от самих сортируемых чисел.
P. S. Я же вроде бы не пытался принизить значимость trie, наоборот я как раз в работе использую очень много структур, завязанных на trie, и почти не использую хеши помимо стандартных хеш-таблиц. Мой посыл был в том, что такой экзотический способ сортировки может действительно быть эффективен в отдельных ситуациях.
Думаю, за красочным примером того, что может произойти, если слишком привязываться к любимым методам и алгоритмам, далеко идти не придется.GCU
29.05.2019 10:59+1Извиняюсь, я не намеревался упрекать, просто подход с хешами префиксов вызвал аналогии. Использования хешей для сортировки на мой взгляд довольно оригинально, а подбор подходящей для сортировки хеш-функции вообще отдельная тема, требующая анализа исходных данных.
Но эзотерику лучше оставить автору статьи :)
Pand5461
28.05.2019 09:41А чем вся эта муть с воронкой из 64 списков вообще выглядела привлекательней построения кучи из входящего потока до исчерпания памяти и слива отсортированной кучи в файл?
lair
28.05.2019 11:25+3Термин «общепринятая терминология» вовсе не означает правильная"
Окей, а какая же терминология тогда правильная? Что важнее, как (формально) определить неправильную терминологию?
Тем более, что он даже не уточняет, КЕМ «общепринятая».
Соответствующим профессиональным сообществом. В нашем случае — математика и computer science.
я полагаю, что у НОРМАЛЬНЫХ людей такая «терминология» не может быть «общепринятой»
Да полагайте что угодно, это ваше личное дело. Это не дает вам оснований утверждать, что все остальные, кто делают не так, как вы полагаете, делают неправильно.
Вопрос: У КАКОГО СТАДА БАРАНОВ это «общепринято»?
Да я вроде сразу дал ссылку на википедию, могу и повторить: "Полный перебор (или метод «грубой силы», англ. brute force)".
Вот, скажем, задача коммивояжёра многодневная, и может быть отложена в любой момент. Как ПРОДОЛЖАТЬ расчёт будете после откладывания, «программист» хренов?
Как-как, через сохранение релевантного состояния, понятное дело.
Кстати, почему-то так и нет вопросов ко мне по коду, не считая одного, совсем уж мелкого. С чего бы это?
С того, что кода так и нет, к чему вопросы-то писать?
Вы что, создатель софта Хабра, лапуль? Тогда поясните, почему у многих пользователей карма имеет ДРОБНОЕ значение?
Откуда берутся половины и четверти пунктов кармы, а также и более редкие дробные числа?.
А я вот утверждаю, что это есть БРЕХНЯ!
Это далеко не первый раз, когда вы что-то утверждаете.
Сам факт дробной кармы ДОКАЗЫВАЕТ это!
Нет, не доказывает. Он доказывает только то, что утверждение "карма меняется (и всегда менялась) только от нажатий стрелочек, и только на целые числа" — неверно.
ЗА ЧТО быдло анонимное нагадило в карму пользователю FDA847?
Спросите у анонимного быдла, я понятия не имею о его мотивациях. За что лично я поставил минус — я уже писал (хотя, похоже, в том посте прошлось НЛО, потому что ни моего комментария с этим объяснением, ни его комментария, на который я отвечал, там больше нет; хорошо хоть, в почте пока есть. Занятное, кстати, поведение НЛО — с одной стороны, я его прекрасно понимаю, здесь не помойка, а с другой стороны, это неудобно для последующих объяснений).
Не мне — это понятно любому дебилу
Знаете, я вот видел как минимум двух хабраюзеров, которым не было понятно, за что вы получали минусы в карму...
Моя версия: за то, что он НЕ быдло, и ТОЛЬКО за это! Ваша версия?
А моя версия — за неумение адекватно себя вести, в частности, не переходя на оскорбления.
GCU
28.05.2019 11:32+4Там если что — был явно указан SARCASM кроме того это данные теоретические и не вашего алгоритма.
При сортировке 2 миллиардов 32-Битных чисел сортировка подсчётом, как предположил playermet довольно проста и элегантна, вы не находите?
При сортировке уже 4 миллиардов 32-Битных чисел при достаточном объёме памяти она гораздо быстрее «воронки», и это очевидно. И это делает «воронку» ниразу не ИДЕАЛЬНОЙ :)Akon32
28.05.2019 18:12+12 миллиардов 32-Битных чисел сортировка подсчётом
4 миллиардов 32-Битных чиселА ведь тоже нетривиальная задача, если необходимых для наивной реализации sizeof(uint32)*2^32 байт ОЗУ нет. Свопинг на диск, вероятно, подтормаживать будет при случайном порядке чисел. Латентность у SSD порядка 25мкс (вроде бы), получается время работы сортировки порядка нескольких суток в плохом случае.
Но наверно можно ужать потребление памяти, вводя 1х,2х,4х-битные и т.д. числа по мере необходимости. Или, может быть, что-то вроде кодов Грея.playermet
28.05.2019 18:28+1Можно переторговать память на скорость если заюзать префиксное дерево для ключей. Но в худшем случае, если каждое из всех возможных значений uint встретится по разу, станет еще хуже.
GCU
28.05.2019 18:43+1Как достаточно тупой вариант — можно несколько раз пройтись по данным, считая только часть диапазона значений. Например 2 ГБ ОЗУ — это 8 проходов по 1/8 от диапазона.
8 раз линейная сложность всё равно линейная :)
SmallSnowball
28.05.2019 18:44+1можно сортировать по окнам, скажем 4 раза, сначала подсчитать все числа меньше 2^30, вторым проходом с 2^30 по 2^31 и так далее. Требования по памяти снизятся в 4 раза, скорость упадет тоже в 4 раза
playermet
28.05.2019 18:42+6Вы даже не передставляете. насколько медленно, насколько въедливо пишет программы НАСТОЯЩИЙ профессионал, какие неожиданные особенности их поведения он там обнаруживает!
Действительно. Если настоящий™ профессионал это тот, кто считает пседокод, блоксхемы, UML, теории алгоритмов, точные бенчмарки и многое другое вами указанное непрактичным бредом, то не удивительно что он пишет как раненый слоупок и часто обнаруживает у себя неожиданные особенности. Он небось еще и пишет в каком-нибудь допотопном IDE без подстветки синтаксиса и автоподстановок, и весь код у него в одном файле или даже функции, ибо судя по описанию, максимальный хардкор — это его самоцель. Ну или как вариант он просто не осилил перечисленное, и теперь страдает, но пытается не подавать виду.
GarryC
28.05.2019 13:00+2Позволю себе еще раз известную цитату «Мыши плакали, кололись, но продолжали жрать кактус», больше добавить нечего.
Scf
29.05.2019 12:21+1Пусть автор пишет на сях как на ассемблере, с именами переменных не шибко информативнее eax/ebx/ecx/edx
Пусть его стиль кодирования настолько стар (суперстар), что требует наличия текстовых комментариев на каждую строчку
Пусть он отказывается опнсорсить свои наработки
Пусть он называет свой алгоритм идеальным (идеальных алгоритмов не бывает, для любого алгоритма можно придумать условия, когда он будет неоптимальным)
Но идеи-то он излагает интересные!
И местами он прав, и меня это тоже печалит — практически религиозная вера в непогрешимость best practices, в O-большое (это все-таки достаточно грубая оценка времени выполнения алгоритма), в то, что технические решения называют хорошими или плохими вне зависимости от контекста их применения.
lair
29.05.2019 12:55Но идеи-то он излагает интересные!
Что конкретно?
технические решения называют хорошими или плохими вне зависимости от контекста их применения.
Хм. "алгоритм «воронки» идеален для любых «условий»", да?
Ну а главное, это же работает как раз наоборот: пусть даже (предположим!) идеи интересные, но когда для того, чтобы до них добраться, нужно руками разрыть сортир в практически буквальном смысле этого слова, то зачем?
Sirion
29.05.2019 13:56+1Вопреки ожиданиям фантастов, в 21 веке космические корабли не бороздят просторы вселенной. Зато петабайты информации бороздят просторы интернета. У нас нет недостатка в текстах, где можно поискать интересные мысли. Сейчас интересны не просто тексты, а тексты с наилучшим соотношением «сигнал/шум». У автора с этим очень, очень плохо. Четыре раза «очень», если учесть комменты (а на хабре они должны быть информативны).
Scf
29.05.2019 14:33+2Вообще-то недостаток в текстах есть. Разжеванное и в рот положенное в виде видео на ютубе или развлекательной статьи вполне можеть быть создано с коммерческой целью — пиара какого-то продукта, компании или себя лично и не страдать излишней объективностью. Много текстов, много мусора.
К примеру, для поиска инженерных знаний интернет уже не подходит, приходится идти ногами в библиотеку — любой, кто делал ремонт в своей квартире, меня поймет.
Новому поколению программистов тоже желательно помнить, что лучший способ стать хорошим программистом — изучение чужих программ.
lair
29.05.2019 14:48+4лучший способ стать хорошим программистом — изучение чужих программ
Особенно этот способ хорошо работает, когда автор программы отказывается показывать ее код.
Sirion
29.05.2019 15:02+1О да, вместо ютубов лучше почитать этот пост, невыносимо страдающий от излишней объективности и полностью лишённый пиара. Про изучение чужих программ уже написали выше.
Pand5461
29.05.2019 12:49Пусть автор пишет на сях как на ассемблере
Пусть его стиль кодирования настолько стар
Пусть он отказывается опнсорсить свои наработки
Пусть он называет свой алгоритм идеальнымВсё равно заминусовали его совершенно за другое.
Scf
29.05.2019 16:57О, только что выяснил на себе, что общаться с автором положительно невозможно. Так что читаем текст, киваем интересным мыслям, пропускаем непонятное, идем к следующей статье.
lair
29.05.2019 18:13+2О, только что выяснил на себе, что общаться с автором положительно невозможно.
Интересно, каким образом.
nrgian
Д. Кнута «Искусство программирования» не читали?
rybvv Автор
Лет 30 назад. Но точно знаю, что «воронки» там не было. :)
FDA847
Напишу тут, чтобы комментарий просто повыше был. Карма автора уже писать сюда не позволяет, поэтому он попросил меня просто выложить вот эту ссылку:
sint.wc.lt/habr.htm
lair
В своей песочнице автор может поговорить с голосами в своей голове совершенно без нашего участия.
FDA847
Там режим read-only, как я понимаю. Но про Вас там отдельные заметки у него есть.
lair
Это неудивительно.
Dim0v
Ну не read-only, а 1 коммент в день. Даже с кармой -100 он сможет писать. Но лишь раз в неделю.
Но в любом случае, оно и к лучшему. Кроме агрессивного невежества комментарии автора ничего не содержали (и его заметка на сайте — не исключение). По существу с ним общаться невозможно.
П.С. А кодом он с вами поделился с условием неразглашения? Если нет, то может вы его опубликуете, чтобы была возможность у желающих все таки провести адекватные бенчмарки?
FDA847
Под read-only я подразумевал его сайт :-) Там вроде нельзя комментарии оставлять.
Кодом поделился. На счёт представление на всеобщее обозрение лучше у него уточню.
M00nL1ght
Уточните пожалуйста и если получится все таки выложите его в открытый доступ, интересно было бы провести нормальные тесты.
FDA847
Сейчас написал ему, жду ответ. Пока проверил сортировку на 10 млн. значений. Около 10 сек у меня она заняла. Фик знает, много это или мало. Пока времени нет со стандартной сортировкой сравнить, успел пока только файлик сгенерить на 10 млн. случайных значений.
lair
Вот именно поэтому есть формальные способы оценки сложности алгоритмов.
infund
Надеюсь, он обретёт там своё счастье.
Sirion
Очень забавно, что этот титан мысли, слон среди мосек, весьма детально помнит своих оппонентов и кто ему что писал. Я бы давно забыл про свой комментарий, если бы автор не напоминал мне о нём каждый раз с присущим ему остроумием и упорством. Возможно, где-то в конце вселенной, в её омега-точке, автор, успевший в далёком двадцать первом веке сменить свой мягкий живой мозг на холодный кибернетический, всё ещё будет вспоминать о том, насколько я мелок и ничтожен. Эта мысль успокаивает меня.
ktotaika
Никто не забыт доблестным гасконцем!
FDA847
Ну кто-то комментарии не забывает, а кто-то гадить в карму! :-)
Sirion
Лайфхак: частота разговоров о карме сильно и отрицательно коррелирует с её производной по времени.
M00nL1ght
Что вы с этой кармой носитесь? Автора ж вполне нормально попросили пример кода для тестов, нормально попросили объяснить как он считает сложность своего алгоритма и тд. И если бы он нормально отвечал то никто «гадить в карму» не стал бы.
FDA847
Я вообще-то про свою карму говорил :-)
mayorovp
А со своей тоже лучше не носиться, будет полезнее для нее же. Ничто так не отбивает желание поставить комментатору плюс в карму, как вступление вида "хоть меня на этом вашем хабре и заминусовало стадо, я все же снизойду до вас и напишу, что...".
robert_ayrapetyan
Т.е. он вас помнит, чтоб у вас от безнаказанности крышу не снесло, ясно? Вообще персонаж интересный (с медицинской точки зрения). От писем Марку Цукербергу на русском языке, до плагиата на Маяковского.
Я не смог вспомнить как называется состояние, когда у человека изливается поток сознания на много много страниц, а четко сформуриловать и обосновать что-либо он не в состоянии. И в качестве компенсации начинается яростный наброс на оппонентов. По-моему, тот самый случай.
Bhudh
В отличие от графомании, это именно попытки текстом доказать какую-то «навязчивую» (психиатры выражаются иначе: сверхценную) идею.