Comments 59
/fannkuchredux ну там как-то ускоряют всё зависит от опыта, но в итоге вопрос тогда, где в той скорости нлогн, получается скорость толи квантуется толи дискретизируется
Вы это к чему?
нотация говорит н лог н, но скорость 2 секунды это н лог н получается, и н лог н у питона с реализацией 40 минут того же алгоритма, типо 2 реализации обе н лог н получается или как?
Не совсем понимаю, в чем вопрос, попытаюсь догадаться
Если Вы сравниваете реализации на Python и C одного и того же алгоритма на предмет времени работы, то стоит ожидать тотального проигрыша первого. Python -- это язык, который минимизирует время разработчика, C -- это язык который минимизирует runtime. В этой статье у меня не было цели сделать полноценные бенчмарки, мне важно было понятней объяснить концепцию, поэтому примеры на Python, для бенчмаркинга они не предназначены
Нотация
асимптотического времени работы алгоритма означает, что есть какая-то глобальная константа C, что для любой последовательности размера n время работы будет не больше 
. К сожалению константа С может быть как очень маленькой, так и очень большой. Есть даже специальная категория алгоритмов, которые имеют хорошую асимптотическую сложность, но на практике бесполезны, потому что С там неприлично огромноеЗачем вообще тогда нужна асимптотика? Очень просто -- это первичный способ отсеивания плохих алгоритмов. Можно бенчмаркать всё подряд, а можно сначала отсеять совсем плохие по асимптотике и не переводить углеводороды просто так.
не ну кубы на питоне в тот же момент работают исправно с ускорением загрузки вначале при включении jit, тоесть она посчитала за 40 минут по входным данным фанкуч, а кубики в чанках с текстурами рисует успешно, ладно, посмотрел еще викиВычислительная_сложность, но тема конечно интересная
так на питон в фанкуч бенче действует иные замедления, не совсем понятно что значит логарифмическая зависимость алгоритма от количества входных данных получается это просто идеализированная ситуация
Не воспринимайте серъезно, это очень странный персонаж, он постоянно возвникает из ниоткуда и оставляет бессмысленные, несвязные комментарии, никак не относящиеся к теме. Чаще всего про векторизацию SIMD.
Подозреваю, что человек просто не в состоянии выразить свои мысли.
Грубо, в этом не было нужды -- мне это было понятно и без Вашего комментария. В диалог я вступил осознанно.
Я сам бываю грубым, только в ответ на вопиющее неуважение, и даже в таком случае представляю претензии по существу и вступаю в диалог.
Вы лучше скажите, получилось ли у меня Вас удивить?)
Нет, эти теоремы я все знал и до этого.
Не задумывался раньше, что можно вот так сравнить сортировку вставкой и пузырьком и посмотреть, что там достигает теоретического минимума, а что нет. Но приведенные факты кажутся очевидными.
А есть референс на т.3 вне taocp?
Никогда не видел это в виде теоремы. Просто широко известный прием для решения задач. Кажется, первый раз до этого я вообще сам додумался, к тому моменту уже множество раз решив задачи на перестановки, где надо было работать с циклами.
Вот про перетановки я как раз понимал и догадался до "сортируем ссылки хорошей сортировкой, свопаем оъекты по циклам" (и по хорошему на практике только так и надо делать), но то, что сортировка выбором делает вторую часть -- это я упустил. Но ничего, получил бурю эмоций и урок на всю жизнь.
Для меня до сих не очевидно как быть если есть повторяющиеся элементы.
Не решал раньше эту задачу, но вот мои рассуждения.
Надо одинаковым элементам назначить уникальные идетификаторы так, чтобы в получившейся перестановке было максимальное количество циклов. Иными словами, числа у нас уникальные, и мы выбираем, куда в ответ встанут дубли, не нарушая порядок.
Сначала построим граф перестановки: для каждого различного элемента есть вершина. Направленное ребро в вершину для числа, которое стоит на его месте. В случае одинаковых элементов мы знаем, какие места они займут в остортированном массиве. И во все числа на этих местах проведем ребра из заданного.
В этом графе уже не простые циклы, в какую-то вершину может входить множество ребер, могут быть парные ребра. Но входящая и исходящие степени будут одинаковы.
Что происходит, если мы возьмем повторяющееся число и один экземпляр сделаем уникальным? Появится новая вершина и она заберет одно входящее ребро и одно исходящее ребро. Надо чуть порисовать, но ясно, что она может забрать любое входящее и исходящее ребро. Вообще, если у нас k дублей, у нас есть k! вариантов их порядка в отсортированном массиве. И ровно k! варинтов назначить каждому входящему ребру одно исходящее.
Итак, мы в каждой вершине должны назначить каждому входящему ребру одно уникальное исходящее так, чтобы в графе было как можно больше циклов. Иными словами, покрыть граф максимальным количеством циклов.
Ясно, что эйлоров обход вкаждой компоненте даст нам худший ответ - минимальное количество циклов. Нам нужно что-то диаметрально противоположное.
Похоже, можно взять эйлеров обход и жадно откусывать циклы. Т.е. в каждой вершине первое входящее ребро в порядке эйлерового обхода назначается к последнему исходящему ребру. Второе - к предпоследнему и т.д. Но у меня пока нет четкого доказательства этому.
Нет, нашел контрпример: 2, 3, 1, 3, 1, 2
Если тут составить граф, то получится тругольник, где по каждой стороне два ребра навстречу. Его можно разбить на циклы несколькими способами. Лучший - каждая сторона свой цикл из двух ребер. Но можно и получить 2 треугольника в разные стороны.
В общем, задача сводится к покрытию всех ребер графа, где входящие степени вершин равны исходящим, максимальным количеством циклов. Кажется, это можно как-то свести к максимальному потоку.
Интересный поворот событий. Если хотите, могу добавить к обсуждению в тг чате питерского CS клуба -- как будто мнения разошлись.
После некоторого обсуждения пришли вот к чему:
Задача нахождения минимального количества свопов в общем случае эквивалентна покрытию эйлерова графа максимальным количеством циклов.
Согласно статье Amir A. et al. On the cost of interchange rearrangement in strings она NP-трудна.
Не существует универсального алгоритма
....
находил бы перестановку элементов p такую, что
....
используя меньше, чем O(n log n)
попарных сравнений, т.е. сравнений двух конкретных элементов.
Что значит "универсального алгоритма"? O(n log n) это верхняя, нижняя или средняя оценка? Если предположить, что массив уже изначально сортирован, количество попарных сравнений для проверки этой гипотезы будет n-1.
Универсильный -- в худшем случае для всех возможных n-элементых последовательностей [различных элементов].
Подразумевается нижняя оценка, Вы имеете в виду, что мне стоило там написать 
? Формально Вы правы, я просто зарекся не перегружать математическими терминами на хабре.
Нижняя оценка для сортировки будет Ω(n). У пузырьковой она как раз такая, если на вход подать изначально сортированный массив. Он просто пробежится по всему массиву, попарно сравнивая соседние элементы.
Это лучший случай, а не худший
Что-то я вообще запутался. Сначала вы пишете "в худшем случае", потом нижняя оценка. Big-omega это же про лучший случай. И "нижняя оценка" это тоже означает лучший случай. Т.е. такой случай, когда алгоритм выполняется быстрее всего.
https://www.bigocheatsheet.com/ - тут у bubble sort в столбце Time Complexity указано Ω(n) для Time Complexity - Best
Смотрите, тут есть два независимых друг от друга множества, по которому можно брать минимум/среднее/максимум
Множество возможных алгоритмов
Множество возможных входных данных
Когда говорят про лучший/худший/в среднем случаи конкретного алгоритма, то имеют в виду, что на лучшем/в среднем/худшем наборе данных будет вот как-то так.
В теореме утверждается, что лучший алгоритм сортировки по худшему набору данных будет делать 
, омега в данным случае относится к алгоритму, а не к данным
Да, теперь понятно.
А делались ли медианные оценки временной сложности разных алгоритмов сортировки? Ну т.е. для размера массива n для всего множества входных данных, какой будет медианное значение сравнений (в половине случаев алгоритм будет делать меньше, в половине случаев больше сравнений)? И какая наименьшая медианная оценка из множества всех возможных алгоритмов?
Приведенный в статье код имеет познавателтно-развлекательный характер и используется для верификации теорем, про которые я писал. Этот код не претендует на оптимальность, поэтому и проводить детальный анализ и тем более бенчмаркать его нет никакого смысла.
Рекомендую прочитать эту статью
https://habr.com/ru/articles/662181/
Там на большинство ваших вопросов ответы есть
На вопрос про медианную сложность я там ответа не нашел. Или может я невнимательно читал?
Временная сложность алгоритмов оценивается обычно по лучшему, среднему и худшему случаю. Лучший случай - число неких операций при самом лучшем случае входных данных. Средний - когда рассматриваем среднее арифметическое числа операций для всех возможных входных данных длины n. Худший - для худшего случая. А оцениваются ли алгоритмы по медианному критерию, т.е. когда есть такое число x, что в половине случаев алгоритм решает задачу за меньше чем x операций, в половине случаев решает задачу за более чем x операций? Или такая оценка не имеет смысла?
Имеет, только обычно не медиана, а 99% процентиль или типа того (что 99% запросов выполнятся за указанное время). Но не припомню, чтоб его алгоритмически считали, обычно смотрят асимптотическую сложность для худшего и среднего случаев, а для задач, где выполняем много операций над структурой – ещё амортизированную сложность. А процентили оцениваются уже экспериментально по готовому коду.
в статье объясню почему пузырёк -- это бесполезная фигня, но внезапно практически также работающая сортировка вставками -- это супер важная сортировка
Неясно, почему в качестве метрики для "бесполезной фигни" вы используете именно количество сравнений, и делаете из этого генеральное обобщение. Довольно легко представить себе такие условия доступа к памяти, когда количество сравнений вообще не будет ничего решать. Пузырёк обладает максимально достижимой локальностью перестановок, что может в каких-то приложениях оказаться важным.
Одна из проблем традиционной оценки сложности сортировок заключается в том, что они предполагают одинаковую стоимость операций доступа к любым элементам в любой последовательности, а на практике это далеко не так.
Собственно, об этом вы упоминаете в третьем пункте.
Неясно, почему в качестве метрики для "бесполезной фигни" вы используете именно количество сравнений, и делаете из этого генеральное обобщение
Не совсем, "бесполезная фигня" она ровно в том плане, что по количеству свопов она такая же как сортировка вставками, а по количеству сравнений всегда ей проигрывает. Именно для этого во всех примерах происходит подсчет и того и другого, и выбраны они именно для наглядности.
UPD. По-хорошему наверно стоит сравнивать пузырек с оптимизацией "если за целый проход по внутреннему циклу ничего не произошло, то остановиться" -- это при желании можно сделать самостоятельно
Ну да. Я просто хотел обратить внимание, что метрики "количество свопов" и "количество сравнений" сами по себе выбраны достаточно произвольно. А в других метриках может получиться другая эффективность.
Когда титаны мысли придумывали классические сортировки в памяти, то основным фактором, влияющим на скорость выполнения программы, несомненно было количество (скалярных) операций процессора, но сейчас это так только в грубом приближении. И, в частности, старый добрый mergesort воскресает из ленточных приводов в параллельные ядра.
старый добрый mergesort воскресает
Почему это воскресает, живее всех живых! std::sort неприменим к std::list, он рассчитан на RandomAccessIterator, для которого работает Inplace. А вот mergesort inplace для std::list и собственно std::list::sort -- это вариации mergesort. Тимсорт -- продвинутый mergesort
Да, но и для массивов mergesort эффективнее quicksort при использовании значительного количества ядер.
Вполне допускаю. Если хотите предметного обсуждения -- нужны конкретные реализации и бенчмарки
Никогда не думал о алгоритмах поиска/сортировки в разрезе многопоточности, спасибо за комментарий, почитаю на досуге
https://habr.com/ru/companies/ruvds/articles/892306/
Буквально недавно была хорошая статья, её еще можно заапвоутить. Там много ссылок на реализации сортировка на CUDA
Так он и по другой причине никогда не умрёт. Насколько я помню, это самая быстрая стабильная сортировка в общем случае.
Пузырёк обладает максимально достижимой локальностью перестановок, что может в каких-то приложениях оказаться важным.
Сложно сказать, в каких (и чтобы были реальны), я такого не соображу.
Условию не драться с "ленточностью" современной RAM -- qsort удовлетворяет не хуже, при любом из вариантов партиционирования, когда указатели ползут по отрезку. Зато там перестановки дальние, что уводит от квадратичности.
Давно пора заняться сортировкой. Спасибо, что напомнили.
А вот. что будет, если рассматривать не отдельные элементы, а некоторые фрагменты или, даже, подпоследовательности? Что значит, переставить местами подпоследовательности? Может быть, здесь может возникнуть какая-то теория?
И что случится со всеми этими алгоритмами, если. скажем, появится трёх-мерная память, где один и тот же массив можно будет топологически расположить весьма различным образом, а операция сравнения двух массивов будет однотактной операцией?
Как узнаете -- напишите статью)
там врятли будет 1 такт, подпоследовательности это разбиение основной последовательности (regexp или split) нужен будет счет, даже безопасный язык давая функции ().().() - ("s.split(" ")[5].toString().charAt(0)") таких последовательностей имеет внутри себя такты, тоесть просто прячет реализации это равно вызову функции всё равно
переставить местами подпоследовательности по старому способу если не запутаетесь просто потасовать адресами тоесть указателями на начала последовательностей в пределе общей последовательности, но внутри каждой последовательности придётся, если реч о сортировках делать тасовки всё равно поидее
да теории есть Permutation
Давно пора заняться сортировкой.
Хм, зачем? Она для 90+% программистов полезна только при обучении, как великолепное методологическое средство, но дальше на практике ценность на порядки меньше каких-нибудь хэш-мап. Просто частный метод где-то глубоко "внутрях".
За все уже почти 30 лет практики в самых разных областях сортировку в явном виде применял дважды, один раз простую и один раз твёрдо потребовалась устойчивая (чтобы исходные пакеты протокола оказались гарантированно перед повторами при сортировке по seqnum). Вызовы типа "apt-cache search зюка | sort" не в счёт.
А вот. что будет, если рассматривать не отдельные элементы, а некоторые фрагменты или, даже, подпоследовательности? Что значит, переставить местами подпоследовательности? Может быть, здесь может возникнуть какая-то теория?
Уже. Timsort собирает подпоследовательности и дальше их объединяет. Причём раньше (1960-70-е) вариантов сортировки слиянием использовалось столько, что сейчас никто толком и не помнит. В третьем томе TAoCP они занимают значительную часть. Но TAoCP уже можно считать безнадёжно устарелым.
И что случится со всеми этими алгоритмами, если. скажем, появится трёх-мерная память, где один и тот же массив можно будет топологически расположить весьма различным образом, а операция сравнения двух массивов будет однотактной операцией?
Что-нибудь придумаем. Можете для начала посмотреть в TAoCP "обменную сортировку со слиянием" имени Бэтчера.
В защиту пузырька )
На почти отсортированных массивах он бывает даже быстрее других алгоритмов.
Как-то надо было отсортировать почту по времени отправления (она лежала по времени получения). Понятно, что письма лежали и так в почти отсортированном порядке, только изредка вперед какого-то загулявшего неведомо где письма успевало проскочить письмо отправленное позже. Так вот на таком массиве пузырек работал быстрее.
Вообще да, я немного поленился, по идее в реализацию пузырька надо добавить "если во внутреннем цикле ничего не произошло, то завершить процесс". Но вроде как и в этом случае нет ситуации, когда он сделает меньше сравнений, чем сортировка вставками, поэтому везде где можно применить пузырёк вставки сработают лучше
поэтому везде где можно применить пузырёк вставки сработают лучше
Попробуйте вставками отсортировать односвязный список.
Ну да, такое себе, только с O(n) доп памятью
Скрытый текст
class ListNode:
def __init__(self, next, val):
self.next = next
self.val = val
def init_from_array(array):
head = None
for val in reversed(array):
head = ListNode(head, val)
return ListNode(head, None)
def sort(self):
if self.next is None:
return
self.next.sort()
self.push()
def push(self):
pushed = self.next
if pushed is None:
return
tmp = pushed
while tmp.next is not None and pushed.val > tmp.next.val:
tmp = tmp.next
if tmp != pushed:
self.next = pushed.next
tmp_next = tmp.next
tmp.next = pushed
pushed.next = tmp_next
def __str__(self):
result = []
tmp = self.next
while tmp is not None:
result.append(tmp.val)
tmp = tmp.next
return "[ " + ", ".join(map(str, result)) + " ]"
single_linked_list = ListNode.init_from_array([5, 2, 3, 9, 6])
single_linked_list.sort()
print(single_linked_list)Вы тут сначала конец сортируете, а не надо это делать. У вас будет один список из уже остортированной части, вы while-ом проходитесь по изначальному списку и каждый новый добавляете в этот осортированный вашим же push.
Да, тут при вставке итерация идет сначала отсортированной части, а не с конца. На ассимптотику это никак не влияет. Ну, будет сравнений не количество инверсий, а n(n-1)/2 - количество инверсий. Никаких swap-ов тут все-равно нет, так что считать количества инверсий не обязательно вообще.
Видимо вот так
def sort(self):
result = ListNode(None, None)
while self.next is not None:
self_next = self.next.next
self.next.next = result.next
result.next = self.next
self.next = self_next
result.push()
self.next = result.nextНу, будет сравнений не количество инверсий, а n(n-1)/2 - количество инверсий. Никаких swap-ов тут все-равно нет, так что считать количества инверсий не обязательно вообще.
Так смысл анализа инверсий в "адаптивности", чтобы на "почти отсортированной последовательности" было "почти O(n)" и исходный посыл от @vadimr был о том, что пузырёк на адаптивный, но в отличие от вставок его проще применять к спискам
Зато тут будет "обратная адаптивность". На почти полностью отсортированной по убыванию последовательности будет O(n) операций. Вообще, можно вернуть изначальное свойство - просто разверните список перед сортировкой и будет такая же адаптивность.
Развернуть список, не разрушая его – сама по себе неудобная и дорогая операция.
В терминах O от количества сравнений она ничего не добавляет к асимптоте, но в прагматике это проблемная вещь:
– нужно ещё столько же памяти;
– нужно время на прохождение списка при построении и потом ещё время на сборку мусора или ручное освобождение памяти;
– ячейки построенного списка будут размещены в памяти в обратном порядке адресов и далеко от исходного списка и связанных с ним данных, что вероятно ухудшит время выборки при использовании этого списка.
Нет же, это easy на литкоде. Один проход с двумя указателями: текущий и предыдущий элементы. А что касается разрушения - мы же его сортируем, он итак будет разрушен.
Один проход с двумя указателями: текущий и предыдущий элементы
Один дополнительный проход.
что касается разрушения
Второй дополнительный проход. Либо в самом алгоритме, либо в сборщике мусора – в зависимости от того, как реализовано управление памятью.
мы же его сортируем, он итак будет разрушен.
Я подразумевал сортировку в новый список, а не разрушение исходного.
Ну тогда все еще проще: строим новый список развернутым, а потом его на месте сортируем. Никакого лишнего сборщика мусора и лишней памяти. Да, лишние O(n) операций. Ну это проблема из-за односвязности списка. Зато искомая адаптивность. И код такой же простой, насколько он может быть простым при работе с односвязными списками.
Из квадратичных сортировок для массивов хорошо по нынешним временам выглядит сортировка выбором:
1) она использует хорошо векторизуемую операцию minind, так что можно сказать, что она выполняется за N векторных операций;
2) она строит результат в последовательных ячейках памяти.
Также она легко применима и к спискам.
Упоминание про O(n) и radix sort имеет "так себе" смысл, потому что как в поразрядной, так и в распределяющей сортировке это log N присутствует косвенно, в виде количества битов. Если у вас элементы с ключом в 10 бит, вы сделаете до 10 проходов, а если 20 бит - до 20 проходов, рекурсивно или в цикле - не суть важно. Поэтому у неё тоже O(n log n), а утверждение по O(n) - чисто трюк.
Доказательство теоремы 1 выглядит слишком вольно написанным и не соответствующим математической строгости. Есть ссылка на более формальный вид?
Финальный проход sort() в GCC библиотеке - тут я бы подчеркнул, что эта сортировка вставками никогда не будет перемещать элементы за пределами каждого того отрезка, за которым мы бросили рекурсию из-за малости длины отрезка. Поэтому она не становится квадратичной. Но что мне не совсем нравится в этой реализации, это то, что она будет финально проходиться и по тем участкам, на которых было переключение в heapsort из-за исчерпания бюджета рекурсии - а они уже отсортированы. Цена того скана, конечно, мала, но не ноль. Надеюсь, тут было применено и не один раз сравнение на каких-то больших тестовых данных.
Поэтому у неё тоже O(n log n)
Нет, у нее O(n log M), где M - максимальный элемент. Это может быть как быстрее так и медленнее n log n, в зависимости от того, какие у вас данные. Но вообще, если считать за n длину входных данных в битах (а не количество чисел в массиве), а числа считать k-битными, то сложность получается O(n/k*k) = O(n). Абсолютно линейно от длины входа. Да, там константа большая и на практике на не слишком больших массивах этот O(n) хуже O(n log n) для всяких qsort'ов (потому что там есть константа 1/k например, ибо чисел-то в массиве в k раз меньше чем бит).
В пузырьковой же сортировке, если так подсчитать, получается O((n/k)^2*k) = O(n^2/k) = O(n^2).
Коррекции ваши полезны, если углубляться в детали - тут 100% (и я плюсанул) - но само такое углубление почти никогда не нужно. В битах точно никто такие вещи не считает. Ну а максимальный элемент практически всегда признаётся равным 2^N-1, без битового представления ключа метод в принципе не работает.
так и в распределяющей сортировке это log N присутствует косвенно, в виде количества битов
A few moments later ...
В битах точно никто такие вещи не считает
Ну кам он =)
Доказательство теоремы 1 выглядит слишком вольно написанным и не соответствующим математической строгости. Есть ссылка на более формальный вид?
По поводу вольности написания -- я категорически отказываюсь делать более формальные утверждения до тех пор пока на Хабре нет адекватной поддержки латеха (например markdown вместо wysiwyg). Если вы как-то на это повлияете, то я с удовольствием стану писать подробнее
на Хабре нет адекватной поддержки латеха
Есть же! И в комментах и в статье. Вставляете формулу (кнопка "сигма"), пишите латех:
Раньше оно умело формулы прям в тексте делать, сейчас дает только отдельным параграфом. Хотя, может это только в комментариях этой возможности теперь нет. Может, в статьях все еще дает прям в параграфы вставлять.
Вот тут у меня встатье все формулы латехные: https://habr.com/ru/articles/746774/
Edit: Или вам надо прям всю статью латехом оформлять?
Инлайн 
есть, но соврешенно не очевиден интуитивно. А еще я потратил 5 минут, чтобы набрать "тех" с телефона, с ноутбука не смльно лучше. Уверен Вы видели мою статью по кратчайшим путям -- вот там просто жесть была, глючило все, после каждой новой формулы мне приходилось проверять, не сломалась ли какая-нибудь из старых (а они ломались!), я думаю, что из-за этого статья писалась в 3 раза дольше. Больше я на это издевательство не готов. В общем не просто так я теперь в каждой статье предлагаю предлагаю хабру перейти на маркдаун вместо визивиг. Понятно что делать из хабра оверлиф -- это не вариант, но маркдаун -- это формат, принятый по всему миру и он простой. А еще там вполне человеческая поддержка латеха.
Я не разбираюсь во фронте, но уверен, что если дать клич по хабру, то найдутся умельцы, которые сервер с редактором маркдауна и загрузкой картинок поднимут за полдня.
Три теоремы о сортировках