How to become an author
Search
Write a publication
Pull to refresh

Comments 63

надо будет заимплементить под php
Total votes 9: ↑6 and ↓3+3
И отхватить много приятных минут на типах, отличных от целого из-за битовых операций.
Total votes 17: ↑11 and ↓6+5
Можно подробнее, чем помешают битовые операции? Либо я чего-то не понимаю, либо они используются только для вычисления параметра minrun.
Total votes 3: ↑3 and ↓0+3
Пользовательская реализация все равно будет проигрывать в скорости встроенным алгоритмам. Да и памяти предложенный вариант кушает…
Total votes 2: ↑1 and ↓10
Нужно добавить в sort, ksort krsort и т.п. параметр с дефолтным значением константа SM_QUICKSORT(SM типа Sort Method или чё нить другое) и будет возможность юзать например SM_TIMSORT
Total votes 3: ↑3 and ↓0+3
Думаю, эта статья могла бы стать русской версией страницы в википедии, если оформить ее по правилам.
Total votes 65: ↑62 and ↓3+59
Я вот неоднократно сталкивался с тем, что при публикации статьи в Википедию примерно 60% усилий уходит на написание статьи, а еще 40% — на ее оформление по правилам Википедии и доказательство всем окружающим её важности, значимости, достоверности и т.д. После нескольких провалов именно на последнем этапе я навсегда зарёкся писать статьи на Википедию. С Хабром проще — статья по делу будет принята хорошо и без всего этого занудства.
Total votes 44: ↑40 and ↓4+36
>> После нескольких провалов именно на последнем этапе я навсегда зарёкся писать статьи на Википедию.

Тяжко вам наверное :)
Total votes 26: ↑4 and ↓22-18
Да нет, нормально. Я ж не читать, я писать туда перестал.
Total votes 16: ↑14 and ↓2+12
UFO just landed and posted this here
Я как бывший «старый пердун-админ» могу сказать, что если вы не про очередного покемона решили писать, то никаких проблем не будет.

Тут есть один нюанс: писать надо НЕ ИЗ ГОЛОВЫ. А по источникам.
Total votes 8: ↑7 and ↓1+6
посему сначала надо написать на хабре, а потом на Википедии сослаться на свою же статью как бы со стороны.
И уже авторитетно...! подкреплено ссылкой...!
Total votes 9: ↑9 and ↓0+9
Именно из-за такой херни у людей возникают проблемы. Хабр — вообще место для блогов. А блог — очевидно не авторитетный источник. Возьмите несколько умных книжек, напишите по ним, в чём проблема-то? Нет, норовят писать из головы, да ещё пытаются подобные нелепые конструкции изобретать.
Total votes 3: ↑1 and ↓2-1
Тут есть один ньюанс — если я крупный специалист в области, о которой пишу и сам себе источник — то облом.
А подкрепить любой безумный высер такими же высерамии дурналистов — раз плюнуть.
Публикация информации и википедическое преломление
Total votes 2: ↑2 and ↓0+2
Википедия на это отвечает, что мол, «Вики — не место для оригинальных исследований». Т.е. сначала опубликуйтесь где-то, пусть Вас там покритикуют, и, если решат что дело говорите — тогда уж пишите на Вики со ссылкой на публикацию. Они, может быть и правы. Только вот те, кто где-то там опубликуются, тем Вики уже и нафиг не нужна.
Total votes 1: ↑1 and ↓0+1
Угу. Более того, в силу очевидного конфликта интересов, считается неэтичным ссылаться на свои работы (даже рецензированные) при написании статей. То есть ты тристараз умный, а ссылаться можно только вот на то ничтожество, которое на диссертации подлые вопросы задавало, но никак не на себя умного и объективного.
This comment wasn’t rated yet0
Да, именно так. Публикация оригинальных исследований запрещена.

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

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

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

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

Нет источников — написано из головы — проверить невозможно — кандидат на удаление. Точка.
Total votes 2: ↑2 and ↓0+2
Если кому-то хочется — может оформить и выложить. Правила Хабра это позволяют, да и я не против.
Total votes 21: ↑20 and ↓1+19
Немного не понял почему этот алгоритм лучше чем использование бинарного дерева.
И здесь, и там O(n) достигается при уже отсортированном массиве.
Total votes 6: ↑3 and ↓30
При уже отсортированном массиве — ничем не лучше. Даже обычной сортировки вставской не лучше. Лучше на массиве, содержащем, скажем, 20 упорядоченных подмассивов, которые, однако, не упорядочены между собой.

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

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

А нельзя, дополнительно перед слиянием, сравнить границы сливаемых массивов, чтобы в случае вашего примера сразу последовательно переписать массивы в результирующий?
This comment wasn’t rated yet0
UFO just landed and posted this here
Замечательная статья! Не хватает только одного: сравнения Timsort и Binary tree sort, ведь у них равные параметры.
Total votes 10: ↑9 and ↓1+8
Почитайте статьи по ссылкам в конце статьи. Там есть результаты сравнения с некоторыми другими алгоритмами.
Total votes 3: ↑3 and ↓0+3
Небольшое замечание по поводу сравнения с другими алгоритмами — оно не совсем корректное: TimSort следует сравнивать по трудоемкости со стабильными алгоритмами сортировки сравнениями.

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

А вообще разных более или менее хороших алгоритмов гораздо больше, чем приведено здесь. И вообще не понятно, зачем сравнивать с заведомо проигрышным Bogosort, который нигде и не используется наверно )
Total votes 5: ↑5 and ↓0+5
Табличка просто взята с Википедии ввиду того, что таблички размером побольше нигде найдено не было. Ясное дело, что алгоритмов намного больше, и понятно, что Timsort не «предел мечтаний». Просто у него тоже есть своя ниша, а статья — всего лишь его описание.
Total votes 7: ↑5 and ↓2+3
ну я же вас не обвиняю ) просто сделал «небольшое замечание» по содержанию статьи. мб стоит тогда ее перенести в раздел Перевод, если непосредственно вашего текста там нет?
Total votes 2: ↑1 and ↓10
Это не перевод. Это компиляция примерно десятка статей, с собственными примерами и пояснениями. Собственно говоря, ни одного предложения просто «в лоб» переведённого в статье нет.
Total votes 6: ↑5 and ↓1+4
к слову о таблице «из википедии». как среднее может быть равно худшему, когда лучшее не равно ни тому ни другому?
This comment wasn’t rated yet0
А где противоречие?
This comment wasn’t rated yet0
пример в действительных числах осилите? хотя бы одну подборочку.
This comment wasn’t rated yet0
вы, видимо, не совсем правильно понимаете сложность алгоритма, здесь не говорится, что время работы алгоритма в среднем и в худшем случае равны, равна только их сложность, т.е. зависимость от размера входных данных
Total votes 3: ↑3 and ↓0+3
Отдалённо этот алгоритм похож на сортировку Шелла, которой тоже сливаются частично упорядоченные массивы.
Total votes 1: ↑1 and ↓0+1
А какой у них коэфициент? Дерево вроде тоже в апроксимации хорошо, но… затратно
This comment wasn’t rated yet0
Если Вы об использовании памяти, то Timsort в самом худшем случае требует 0.5*N памяти. Если о лучшем случае — то коэфициент чётко 1 (т.е. нужно будет ровно N операций сравнения).
Total votes 1: ↑1 and ↓0+1
нет. g(x) = O(f(x)) это «упрощенно» g(x) < C * f(x) на ассимптотике.

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

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

Для хранения стека…
Total votes 3: ↑2 and ↓1+1
В статье говорят об алгоритмах, а не о реализации алгоритма на каком либо языке. К примеру, есть такая вещь как хвостовая рекурсия. Она реализована не во всех языках, но она существует и она не требует памяти для хранения точки возврата из функции в стеке, возврата не происходит.
Если какой-то язык не реализует что-то необходимое для реализации алгоритма, это ещё не значит что алгоритм работает медленно или использует больше места.
This comment wasn’t rated yet0
Извините, но быстрой сортировке в любой реализации нужен стек, то ли вы его сами делаете (итеративный вариант), то ли система его делает за вас (рекурсивный вариант). Можете почитать любую книгу по анализу алгоритмов (передо мной сейчас лежит Седжвик). Хвостовая рекурсия здесь вообще не причем, т. к. в быстрой сортировке два рекурсивных вызова…
Total votes 1: ↑1 and ↓0+1
Седжвик пишет про реализации алгоритмов на 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.
Total votes 3: ↑1 and ↓2-1
Последний раз повторяю, для тех, кто в танке (:
1) Стек нужен в любой реализации быстрой сортировки — если вам не нравится Седжвик, то загляните в Кормена (там C/С++ нет).
2) Хвостовой рекурсии в быстрой сортировке нет, т. к. в ней имеется два рекурсивных вызова. В том же Кормене есть упражнение, в котором описывается как избавиться только от одного рекурсивного вызова (при этом размер стека все равно в лучшем случае будет равен log(n)…
Total votes 3: ↑3 and ↓0+3
Для тех кто не в танке :)) выложу скрины со страниц Кормена, вынудили, обращаю внимание на второй скрин в нём говорится о реализации Седжвика…
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
Total votes 2: ↑1 and ↓10
Дополнительная память не нужна для хранения элементов массива, но она используется для организации вычислений… А насчет стека загляните на страницу 217, упражнение 7.4
Total votes 3: ↑2 and ↓1+1
Вообщем мелкие массивы он сортирует со скоростью вставками, т.е. за n операций, для больших массивов (больше 64), его асимптотика равна асимптотике сортировки слияние, т.е. за nlogn. А значит тут вообще говорить о том, что алгоритм работает с такой же скоростью в асимптотике, что и сортировка бинарного дерева, не корректно.
This comment wasn’t rated yet0
Ошибка в Ваших размышлениях вот тут:
>«значит она может работать с O(n) только до minrun»

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


Почему либо строго по убыванию? Это ведь нужно для разделения на подмассивы?
This comment wasn’t rated yet0
блин, туплю. для сохранения стабильности при развороте массива=)
This comment wasn’t rated yet0

A = {1, 2, 3,..., 9999, 10000}B = { 20000, 20001, ...., 29999, 30000}

немножко некропостинга.

пример неудачный, так как достаточно проверки крайних значений, очевидно что 10000 меньше 20000, а значит можно их просто склеить без галопа. Галоп нужен на примерно таких данных:

A = {1,2,3,4,5,6,7,100,1209,3000,5000,10000}

B = {98,113,118,119,120,1345,1346,4000,12000,13000,20000}

Тут после нескольких копирований из A, например 1-2-3, мы прыгаем вперед и например попадаем на 1209. Теперь интервал между 4 и 1209 нам нужно бинарным поиском разделить так, чтобы найти 7, после этого будет копирование с 5 по 7 и т.д.

This comment wasn’t rated yet0
Sign up to leave a comment.

Your account

Sections

Information

Services

Support
© 2006–2024, Habr