в нём же баг нашли

(Reply to this) (Thread)

и вот так и совали в какойто линупс, а потом выкинули и вернули qsort

(Reply to this) (Parent)

о котором ты знаешь… ты знаешь… а вот: о котором ты знаешь нихуя.

(Reply to this) (Parent) (Thread)

так и есть, нихуя не знаю
а доказательство корректности работы тимсорта существует?

(Reply to this) (Parent) (Thread)

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

(Reply to this) (Parent)

не в алгоритме же баг а в реализации алгоритма на сраном ведроиде и в сраной жабе

(Reply to this) (Parent) (Thread)

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

(Reply to this) (Parent) (Thread)

то есть одни пидарасы не могут написать нормальную реализацию, а у других пидарасов от этого бомбит

все скопом нахуй

>все уже давно починили

а также нахуй

(Replies frozen) (Parent) (Thread)

и один ты у нас пишешь всегда без ошибок. гений уровня кнута, а может быть даже и выше. ну, неси свой алгоритм, мы охуеем, а тим утрётся.

(Replies frozen) (Parent) (Thread)

какая буква в слове "нахуй" непонятна?

(Replies frozen) (Parent) (Thread)

и то правда. иди нахуй, и никогда не возвращайся, уёбок.

(Replies frozen) (Parent)

ничего круче sleep sort не придумали

> таскайте свои реализации с собой

C/C++ одной строчкой
хули тебе не нравится?

Legacy же
Диды квиксортили и правнуки будут

(Reply to this) (Thread)

Ну вот не надо.
В JDK, например, mergesort используется, на основе которого сделан timsort. Просто timsort заточен на типа real world задачи, в которых равномерно случайно распледеленные данные - скорее исключение.

(Reply to this) (Parent) (Thread)

Бля, начиная с OpenJDK 7 timsort штоле? Пиздец, а народ то и не в курсе.

(Reply to this) (Parent)

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

(Reply to this) (Parent) (Thread)

Так что с тестами? Люди волнутся же, сколько можно саспенс этот держать?

(Reply to this) (Parent) (Thread)

да воьзми любую из реализаций и проверь. мне лень.

(Reply to this) (Parent) (Thread)

Хз, на полностью рандомизированных (на каждой итерации) данных квик все таки пизже, как и ожидалось:

# Warmup: 10 iterations, 1 s each
# Measurement: 10 iterations, 1 s each
# Benchmark mode: Average time, time/op

Benchmark            Mode  Cnt  Score   Error  Units
SortBench.mergeSort  avgt   20  0.436 ? 0.006  ms/op
SortBench.quickSort  avgt   20  0.206 ? 0.003  ms/op

(Reply to this) (Parent)

Бля, ты же там с хипсортом сравнивал. Плюс я в тесте проебался чучуть. Новые результаты:

Benchmark            Mode  Cnt  Score   Error  Units
SortBench.heapSort   avgt   20  1.503 ? 0.032  ms/op
SortBench.mergeSort  avgt   20  1.175 ? 0.026  ms/op
SortBench.quickSort  avgt   20  0.886 ? 0.010  ms/op

Сортировка написана одним и тем же человеком, соответственно радиус кривизны рук должен быть плюс-минус одинаков.

(Reply to this) (Parent)

О, а вот кстати jre-шный timsort. Как и было обещано, он не хуже mergesort'а на случайных данных:

SortBench.jreSort    avgt   20  1.048 ? 0.007  ms/op

(Reply to this) (Parent)

А как ты учился языку? По книгам?

(Reply to this) (Thread)

какому из тех языков, которые я думаю, что знаю?

(Reply to this) (Parent) (Thread)

Вопрос был насчет крестов. Но и всё остальное опиши, если не трудно.

(Reply to this) (Parent) (Thread)

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

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

лисп — по книжке про r-list для автокада, и sicp.

forth — по великолепнейшей «starting forth» от лео броуди.

а потом уже по чём попало и как попало. после накопления критической массы базовых знаний оно всё уже выглядит как: «ага. ясно. это XYZ. понимаю. посмотрим, как тут реализовали.»

(Reply to this) (Parent)

Потому что worst-case space complexity: O(n).

Quicksort хорош именно тем, что памяти жрет O(log n). Это две разные категории алгоритмов: одни стабильные (как mergesort), другие к памяти нетребовательные (у heapsort, кстати, худшее время лучше, чем у quicksort - но в среднем он медленнее). Для разных, соответственно, задач. Предложение заменить одно другим так же странно, как предложение заменить jpeg на mp3.

Вот придумал бы кто стабильный in-place алгоритм, да с худшим временем O(log n), да еще и с нормальной константой - вот тогда зажили бы. Но не придумывают же ни хуя. Чаи гоняют в своих институах, по конференциям анекдотики-хуетики рассказывают, а мы блядь ебись а алгоритмами сороковых годов. Думают, что если они PhD в Computer Sience, то можно говном на нас срать. Нейронные блядь сети вместо нормальных алгоритмов выдумывают, а как пахать - так мы. А я на фортране прграммировал, и я не позволю над собой так издеваться. Квантовые алгоритмы, а я их гадов ебал.

(Reply to this) (Thread)

да ладно, тимсорт требует где-то чуть больше килобайта дополнительной памяти под стек этих… как их… runs. совершенно не то, на что стоит обращать внимание во всяких там libc. а если начать улучшать квиксорт на предмет толерантности к «плохим данным», то он тоже начинает или памяти требовать, или замедляется «в общем случае». с тимсортом получаем не медленней, зато мегавин на partially sorted, да ещё и stable. не вижу никакой причины не заменить реализацию qsort на тим.

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

(Reply to this) (Parent) (Thread)

Стек, если я правильно понимаю, там нужен только на три run'а - перед тем, как сунуть туда следующий, какие-то два объединяются. Это, действительно, байты.

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

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

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

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

(Reply to this) (Parent) (Thread)

>А вот для того, чтобы смержить два массива, может понадобиться дополнительная
>память размером с один из них
ну, там размеры run-ов ограничены (макс. 64, вроде бы), так что если не сортировать массивы, где элементы размерами в мегабайты, то тоже слёзки. алсо, по-моему, есть вариант почти-in-place mergesort. который, конечно, медленней, но если у тебя огромного размера элементы — то вполне вариант переключиться на него. как раз в духе адаптивности тимсорта будет.

>Частично упорядоченные массивы - это какой-то фантастический случай, честно
>говоря
да влёт. в спелунке, например, каждый спрайт имеет depth, по которой спрайты и сортируются перед рендером. и большинство спрайтов вообще одинаковый depth имеют, а у остальных часто встречается ситуация упорядоченности, когда несколько объектов друг на дружке. реально, быстрее их сложить в массив и потом отсортировать, чем двигать куски массива туда-сюда, вставляя в нужное место.

и подобные ситуации встречаются нередко. ирл большинство «рандомных» данных имеют достаточно большие отсортированые куски (потому что данные на самом деле нифига не рандомные жы).

в итоге тимсорт немного жертвует памятью (но нефатально, особенно на современной технике), зато амортизирует весьма часто встречающиеся ирл случаи. плюс — я таки могу и не думать ни о том, что у меня есть вариант, когда программа ВНИЗАПНА просядет нафиг, и делать сортировки по нескольким ключам в несколько же проходов без боязни всё поломать (stable жы). второе не так глупо, как кажется: весьма полезно в UI, где данные можно сортировать/фильтровать по нескольким разным критериям.

(Reply to this) (Parent) (Thread)

Не-не-не, размеры run'ов ограничены СНИЗУ - куски, меньшие 64 элементов сортируются вставками. А сверху предела нет - run'ы объединяются друг с другом, их размер растет. Если все хорошо, то мы все время к большому куску прибавляем маленький (и нам нужна дополнительная память размером с маленький кусок). Но если что-то пойдет не так, то в конце мы будем иметь два здоровых куска в половину массива каждый. То есть обязательно внезапно просядет, хотя и не по времени. В некоторых задачах это не критично (то есть заранее известно, что объем свободной памяти больше сортируемых массивов), но как универсальное решение это не годится.

In-place merge либо не in-place, либо не O(n).

Mergesort ничем не лучше timsort, те же проблемы с памятью, только без плюшек на особых случаях. Собственно, timsort - это и есть mergesort, заоптимизированный под особые случаи.

Что касается примера со спрайтами - Если я правильно понял, там есть статические элементы (более-менее упорядоченные) и динамические, которые из-за своей динамичности не упорядочены? Тогда тоже лучше всю статику упорядочить один раз на всю жизнь, а динамику сортировать отдельно после каждого изменения, затем мержить за O(n).

Ну и вообще - если данные не рандомны, то лучше понять, в чем там закономерность и эксплуатировать ее сознательно. Быстрее будет. А сама идея сделать алгоритм, который с одной стороны универсальный, а с другой - оптимизирован под некие "часто встречающиеся случаи" отдает ебучими нейронными сетями, которые дают правильный ответ, но не всегда, а только с большой вероятностью.

Сортировки в несколько проходов по разным ключам - да, это нормально, особенно если порядок сортировки известен только на рантайме, и захардкодить сравнение по составному ключу нельзя. Но если сортируются сами объекты, а не индексы, то, возможно, лучше иметь очень сложную (и медленную) функцию сравнения, чем двигать объекты по памяти в несколько раз чаще.

(Reply to this) (Parent) (Thread)

>А сверху предела нет - run'ы объединяются друг с другом, их размер растет.
ок, может быть. я не очень вникал — взял готовое и всё откладываю подробно разобраться.

>In-place merge либо не in-place, либо не O(n).
да, он не совсем O(n). но для огромных кусков вполне есть смысл — там всё равно движение памяти уже слопает порядочно скорости, так что особого смысла пытаться выиграть за счёт strict time нет. мне так кажется.

>Тогда тоже лучше всю статику упорядочить один раз на всю жизнь, а динамику
>сортировать отдельно после каждого изменения, затем мержить за O(n).
там в принципе нет «статики» — там любой объект потенциально динамический. это во-первых. во-вторых, обработка всех объектов одинаковым кодом упрощает этот самый код. в третьих, динамику же всё равно надо в середину статики вставлять: что-то прячется за определённые виды тайлов, что-то нет. в итоге всё равно надо сливать массивы — так зачем изобретать спецалгоритмы (и потом захардкоживать этот отдельный случай в универсальную исполнялку), если можно тупо отсортировать. тут баланс между усложнением кода путём вписывания спецслучаев, и: «да похеру, пусть сортирует, зато код простой как полено.»

изначально в спелунке примерно так и было: несколько гридов даже для разных объектов. а потом я заебался и слил всё в кучу. проебал где-то один процент CPU в итоге, зато выкинул кучу хрупких условий.

опять же, уровень в спелунке разрушаемый и изменяемый, так что проще считать тайлы просто такими же объектами, как и всё остальное.

>если данные не рандомны, то лучше понять, в чем там закономерность и
>эксплуатировать ее сознательно. Быстрее будет.
иногда да. а иногда проще воткнуть алгоритм, который «более-менее справляется» и забить. но беда в том, что в стдлибе такого алгоритма нет — поэтому приходится таскать с собой копипасту.

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

я, пожалуй, погорячился с требованием замены. а вот добавить тимсорт в libc, например — это было бы вполне в тему. хоть и раздувание и без того дурных размеров библиотеки, но иметь выбор между «быстрым, но не очень толерантным к сортированым данным» и «не таким быстрым, но хорошо жующим сортированое, да ещё и стабильным» — было бы очень неплохо. хотя бы для того, чтобы люди не таскали с собой разные реализации не самого тривиального алгоритма.

(Reply to this) (Parent)

p.s.: понятно, что описаные в последнем абзаце случаи можно заворкэраундить разными методами, но нафига, если есть сортировщик, который нормально справляется без хаков?

(Reply to this) (Parent)

p.s.: но если мне надо вдруг зачем-то написать сортировку без стдлиба, то я обычно таки хипсорт сую. потому что «херовые данные» таки встречаются намного чаще, чем кажется, и ну его — пусть лучше в среднем чуть медленней, чем ВНИЗАПНО просядет.

(Reply to this) (Parent) (Thread)

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

(Reply to this) (Parent)

> привет, glibc!

Не знаю, у меня на фряхе в стандартной библиотеке три функции (у них даже man page общая): qsort для рисковых парней, heapsort для тех, кто ценит надежность, и mergesort для тех, кто готов платить памятью за стабильность сортировки. Ничего лишнего, зато есть все необходимое. При этом никто не обещает, что mergesort - это именно mergesort по рецепту фон Наймана. Может быть, в реализации там тот же timsort или еще что-нибудь. И qsort наверняка не совсем qsort.

(Reply to this) (Thread)

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

а qsort обычно таки qsort, но с каким-нибудь median (или double median) pivot, чтобы амортизировать плохие случаи.

(Reply to this) (Parent)