Pull to refresh

Comments 62

И отхватить много приятных минут на типах, отличных от целого из-за битовых операций.
Можно подробнее, чем помешают битовые операции? Либо я чего-то не понимаю, либо они используются только для вычисления параметра minrun.
Пользовательская реализация все равно будет проигрывать в скорости встроенным алгоритмам. Да и памяти предложенный вариант кушает…
Нужно добавить в sort, ksort krsort и т.п. параметр с дефолтным значением константа SM_QUICKSORT(SM типа Sort Method или чё нить другое) и будет возможность юзать например SM_TIMSORT
Думаю, эта статья могла бы стать русской версией страницы в википедии, если оформить ее по правилам.
Я вот неоднократно сталкивался с тем, что при публикации статьи в Википедию примерно 60% усилий уходит на написание статьи, а еще 40% — на ее оформление по правилам Википедии и доказательство всем окружающим её важности, значимости, достоверности и т.д. После нескольких провалов именно на последнем этапе я навсегда зарёкся писать статьи на Википедию. С Хабром проще — статья по делу будет принята хорошо и без всего этого занудства.
>> После нескольких провалов именно на последнем этапе я навсегда зарёкся писать статьи на Википедию.

Тяжко вам наверное :)
Да нет, нормально. Я ж не читать, я писать туда перестал.
UFO landed and left these words here
Я как бывший «старый пердун-админ» могу сказать, что если вы не про очередного покемона решили писать, то никаких проблем не будет.

Тут есть один нюанс: писать надо НЕ ИЗ ГОЛОВЫ. А по источникам.
посему сначала надо написать на хабре, а потом на Википедии сослаться на свою же статью как бы со стороны.
И уже авторитетно...! подкреплено ссылкой...!
Именно из-за такой херни у людей возникают проблемы. Хабр — вообще место для блогов. А блог — очевидно не авторитетный источник. Возьмите несколько умных книжек, напишите по ним, в чём проблема-то? Нет, норовят писать из головы, да ещё пытаются подобные нелепые конструкции изобретать.
Тут есть один ньюанс — если я крупный специалист в области, о которой пишу и сам себе источник — то облом.
А подкрепить любой безумный высер такими же высерамии дурналистов — раз плюнуть.
Публикация информации и википедическое преломление
Википедия на это отвечает, что мол, «Вики — не место для оригинальных исследований». Т.е. сначала опубликуйтесь где-то, пусть Вас там покритикуют, и, если решат что дело говорите — тогда уж пишите на Вики со ссылкой на публикацию. Они, может быть и правы. Только вот те, кто где-то там опубликуются, тем Вики уже и нафиг не нужна.
Угу. Более того, в силу очевидного конфликта интересов, считается неэтичным ссылаться на свои работы (даже рецензированные) при написании статей. То есть ты тристараз умный, а ссылаться можно только вот на то ничтожество, которое на диссертации подлые вопросы задавало, но никак не на себя умного и объективного.
Да, именно так. Публикация оригинальных исследований запрещена.

Причина — вы считаете себя крупным специалистом, а окружающие спецы считают вас некрупным прохиндеем, пилящим бюджет на серебрянных фильтрах для воды. Кто прав?

Википедия не место для публикации _НОВЫХ_ данных, это место для сбора хорошо проверенных и общеизвестных в профессиональных кругах фактов, а так же место для отражения наличия разногласий по вопросу при их наличии.

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

Если честно, я столько раз это говорил в википедии, что уже повторять лень.

Нет источников — написано из головы — проверить невозможно — кандидат на удаление. Точка.
Если кому-то хочется — может оформить и выложить. Правила Хабра это позволяют, да и я не против.
Немного не понял почему этот алгоритм лучше чем использование бинарного дерева.
И здесь, и там O(n) достигается при уже отсортированном массиве.
При уже отсортированном массиве — ничем не лучше. Даже обычной сортировки вставской не лучше. Лучше на массиве, содержащем, скажем, 20 упорядоченных подмассивов, которые, однако, не упорядочены между собой.

Т.е. проще говоря, идеальные случаи отличаются и, по мнению автора, хорошие для Timsort случаи встречается в реальной жизни чаще хороших случаев других алгоритмов.
А почему не брался в расчет smoothsort? Ведь там память O(1), а все остальные показатели такие же, кроме stable. Stable означает, что рядом стоящие элементы в правильном порядке не будут переставляться?
На больших массивах выделение памяти имеет значение и на очень маленьких тоже.
Никто и не спорит, что другие алгоритмы имеют право на жизнь, статья описывает только достоинства и недостатки данного алгоритма. А что и когда использовать — решать нужно в каждом конкретном случае. «Стабильность», к стати, означает еще и то, что если в сортируемом массиве встретятся подряд идущие одинаковые элементы — стабильный метод их переставлять не будет, а нестабильный волен хоть 100 раз их перетасовать.

Я так думаю, что лучшее применение этой штуки — например, слить в одну пару таблиц из базы или листов из экселевской книги. Частично отсортированные данные, величины порядка тысяч\миллионов записей — самое то.
Если уже некоторое количество элементов (в данной реализации алгоритма это число жестко равно 7) было взято из одного и того же массива — предполагаем, что и дальше нам придётся брать данные из него.

А нельзя, дополнительно перед слиянием, сравнить границы сливаемых массивов, чтобы в случае вашего примера сразу последовательно переписать массивы в результирующий?
UFO landed and left these words here
Замечательная статья! Не хватает только одного: сравнения Timsort и Binary tree sort, ведь у них равные параметры.
Почитайте статьи по ссылкам в конце статьи. Там есть результаты сравнения с некоторыми другими алгоритмами.
Небольшое замечание по поводу сравнения с другими алгоритмами — оно не совсем корректное: TimSort следует сравнивать по трудоемкости со стабильными алгоритмами сортировки сравнениями.

А в таблице каша получается: намешаны алгоритмы разного типа. Если уж перечислять, то добавьте и Bucket Sort, которая всегда O(n) по трудоемкости.

А вообще разных более или менее хороших алгоритмов гораздо больше, чем приведено здесь. И вообще не понятно, зачем сравнивать с заведомо проигрышным Bogosort, который нигде и не используется наверно )
Табличка просто взята с Википедии ввиду того, что таблички размером побольше нигде найдено не было. Ясное дело, что алгоритмов намного больше, и понятно, что Timsort не «предел мечтаний». Просто у него тоже есть своя ниша, а статья — всего лишь его описание.
ну я же вас не обвиняю ) просто сделал «небольшое замечание» по содержанию статьи. мб стоит тогда ее перенести в раздел Перевод, если непосредственно вашего текста там нет?
Это не перевод. Это компиляция примерно десятка статей, с собственными примерами и пояснениями. Собственно говоря, ни одного предложения просто «в лоб» переведённого в статье нет.
к слову о таблице «из википедии». как среднее может быть равно худшему, когда лучшее не равно ни тому ни другому?
пример в действительных числах осилите? хотя бы одну подборочку.
вы, видимо, не совсем правильно понимаете сложность алгоритма, здесь не говорится, что время работы алгоритма в среднем и в худшем случае равны, равна только их сложность, т.е. зависимость от размера входных данных
Отдалённо этот алгоритм похож на сортировку Шелла, которой тоже сливаются частично упорядоченные массивы.
А какой у них коэфициент? Дерево вроде тоже в апроксимации хорошо, но… затратно
Если Вы об использовании памяти, то Timsort в самом худшем случае требует 0.5*N памяти. Если о лучшем случае — то коэфициент чётко 1 (т.е. нужно будет ровно N операций сравнения).
нет. g(x) = O(f(x)) это «упрощенно» g(x) < C * f(x) на ассимптотике.

Так вот, не смотря на то, что quick имеет в худшем случае O(n^2), он при этом имеет C значительно меньше, чем сортировка деревом и работает обычно быстрее.
Вы знаете, серьёзных фундаментальных исследований на эту тему по Timsort я нигде не встречал. В оригинальной статье (ссылка в конце статьи) автор алгоритма сравнивает Timsort с samplesort, quicksort и mergesort и показывает (в основном, по факту тестов, а не теоретически) преимущество Timsort над ними в пределах от 1.5% скорости до вообще нереальных чисел.
чем этот хитрый алгоритм лучше бинарного дерева?
Если бы он был однозначно «лучше» — то дерева бинарного уже давно не существовало бы. Меньше памяти кушает, на определённых данных быстрее работает (а на других данных — лучше дерево).
Интересно было бы иметь какой-то (статистический?) метод, позволяющий в зависимости от контента переключаться между бинарным деревом и тимсортом
Что-то я не понял, это в асимптотике тимсорт в лучшем случае работает за O(n)?
Странно, лично мне показалось, что на лучшем наборе он работает за такое время только, когда используется сортировка вставками (ибо последовательность может быть уже отсортирована, тогда вставки работают за O(n)) значит она может работать с O(n) только до minrun, до дальше работает слияние, но слияния, в свою очередь, будут работать в лучшем случае O(nlogn) значит и весь алгоритм в асимптотике будет работать за O(nlogn). Так что я ставлю под сомнение вообще достоверность всей таблички в статье, и не правомерно сравнивать алгоритмы для которых асимптотики написаны не верно — «левые»…
К примеру, мне интересно, а зачем нужна память в быстрой сортировке? Я раньше думал, что не нужна, ибо сортировка идёт «на месте».
Затем, я думал, что в лучшем случае, для сортировки слиянием потребуется память O(n), конечно если не использовать Алгоритм Пратта (точно не помню как его зовут, может и не Пратт) или другие методы связанные с медианами (асимптотика которых написана на третьей строке таблицы), значит уже 3 ошибки в таблице. Причём одна из них связанна с повествуемым материалом, который сравнивается с методом сортировки бинарным деревом, у которого коэффициенты у сложности намного больше даже чем у сортировки слиянием (ибо приходится уравновешивать дерево, а иначе он будет работать не быстрее быстрой сортировки на плохом случае, т.е. за O(n^2))

«На таких данных Timsort рвёт в клочья все остальные алгоритмы. » — конечно конечно, если считать что он асимптотически на лучшем наборе работает за O(nlogn), коих результатов не может добиться ни один алгоритм (сарказм).
> К примеру, мне интересно, а зачем нужна память в быстрой сортировке?

Для хранения стека…
В статье говорят об алгоритмах, а не о реализации алгоритма на каком либо языке. К примеру, есть такая вещь как хвостовая рекурсия. Она реализована не во всех языках, но она существует и она не требует памяти для хранения точки возврата из функции в стеке, возврата не происходит.
Если какой-то язык не реализует что-то необходимое для реализации алгоритма, это ещё не значит что алгоритм работает медленно или использует больше места.
Извините, но быстрой сортировке в любой реализации нужен стек, то ли вы его сами делаете (итеративный вариант), то ли система его делает за вас (рекурсивный вариант). Можете почитать любую книгу по анализу алгоритмов (передо мной сейчас лежит Седжвик). Хвостовая рекурсия здесь вообще не причем, т. к. в быстрой сортировке два рекурсивных вызова…
Седжвик пишет про реализации алгоритмов на C/C++… Реализацию алгоритма на некотором языке.
Его анализ идёт в рамках данного языка, да, в C/C++ нет средств (хотя я не знаю) оптимизации к хвостовой рекурсии на уровне компилятора, поэтому для данных языков это верно.
ru.wikipedia.org/wiki/%D0%A5%D0%B2%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%B0%D1%8F_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F
См. раздел «описание». Примечание: причём возрат в функции это void.
Последний раз повторяю, для тех, кто в танке (:
1) Стек нужен в любой реализации быстрой сортировки — если вам не нравится Седжвик, то загляните в Кормена (там C/С++ нет).
2) Хвостовой рекурсии в быстрой сортировке нет, т. к. в ней имеется два рекурсивных вызова. В том же Кормене есть упражнение, в котором описывается как избавиться только от одного рекурсивного вызова (при этом размер стека все равно в лучшем случае будет равен log(n)…
Для тех кто не в танке :)) выложу скрины со страниц Кормена, вынудили, обращаю внимание на второй скрин в нём говорится о реализации Седжвика…
dl.dropbox.com/u/5753856/%D1%81%D0%BA%D1%80%D0%B8%D0%BD1.png

dl.dropbox.com/u/5753856/%D1%81%D0%BA%D1%80%D0%B8%D0%BD1.png

Первый скрин страница 198, второй скрин страница 219
Дополнительная память не нужна для хранения элементов массива, но она используется для организации вычислений… А насчет стека загляните на страницу 217, упражнение 7.4
Вообщем мелкие массивы он сортирует со скоростью вставками, т.е. за n операций, для больших массивов (больше 64), его асимптотика равна асимптотике сортировки слияние, т.е. за nlogn. А значит тут вообще говорить о том, что алгоритм работает с такой же скоростью в асимптотике, что и сортировка бинарного дерева, не корректно.
Ошибка в Ваших размышлениях вот тут:
>«значит она может работать с O(n) только до minrun»

minrun — это не константный и не максимальный, а минимальный размер отсортированного подмассива. В алгоритме шага №1 (пункты 2 и 3) написано, что ищется максимальный размер run, который в идеале будет равен N, а значит никаких сортировок вообще применено не будет.
Мой феил, согласен с этим. Действительно асимптотика сложности снизу равна P(n) для всех n.
Причём упорядоченный либо нестрого по возрастанию, либо строго по убыванию. Т.е или «a0 <= a1 <= a2 <= ...», либо «a0 > a1 > a2 > ...»


Почему либо строго по убыванию? Это ведь нужно для разделения на подмассивы?
блин, туплю. для сохранения стабильности при развороте массива=)
Only those users with full accounts are able to leave comments. Log in, please.

Information

Founded
1992
Location
Украина
Website
www.infopulse.com
Employees
1,001–5,000 employees
Registered