Приведенный в статье код имеет познавателтно-развлекательный характер и используется для верификации теорем, про которые я писал. Этот код не претендует на оптимальность, поэтому и проводить детальный анализ и тем более бенчмаркать его нет никакого смысла.
Почему это воскресает, живее всех живых! std::sort неприменим к std::list, он рассчитан на RandomAccessIterator, для которого работает Inplace. А вот mergesort inplace для std::list и собственно std::list::sort -- это вариации mergesort. Тимсорт -- продвинутый mergesort
Смотрите, тут есть два независимых друг от друга множества, по которому можно брать минимум/среднее/максимум
Множество возможных алгоритмов
Множество возможных входных данных
Когда говорят про лучший/худший/в среднем случаи конкретного алгоритма, то имеют в виду, что на лучшем/в среднем/худшем наборе данных будет вот как-то так.
В теореме утверждается, что лучший алгоритм сортировки по худшему набору данных будет делать , омега в данным случае относится к алгоритму, а не к данным
Неясно, почему в качестве метрики для "бесполезной фигни" вы используете именно количество сравнений, и делаете из этого генеральное обобщение
Не совсем, "бесполезная фигня" она ровно в том плане, что по количеству свопов она такая же как сортировка вставками, а по количеству сравнений всегда ей проигрывает. Именно для этого во всех примерах происходит подсчет и того и другого, и выбраны они именно для наглядности.
UPD. По-хорошему наверно стоит сравнивать пузырек с оптимизацией "если за целый проход по внутреннему циклу ничего не произошло, то остановиться" -- это при желании можно сделать самостоятельно
Отличие в том, что пока есть внешние безусловные сильные ссылки, то такой объект будет держать сам себя, но когда они исчезнут, то сразу распадётся. Я сейчас проверяю теорию, не до конца у меня все сходится, кажется, что объект может развалиться частично, но как будто идея стоит рассмотрения
Немного подумал, попробую вот так расписать. Пусть у нас есть unique_ptr и shared_ptr -- стандартные для C++ сильные указатели. Докидываем к ним mixed_ptr, работающий по 3 варианту моего описания. Если развивать идею автора с запретом ссылок можно договориться, что для shared и unique они запрещены, а для mixed нет. Но я скорее думал в направлении, что на стеке все ссылки shared/unique, а в heap -- mixed.
Насчет третьего варианта - если у нас граф не фиксированный а изменяется, то рано или поздно возникнет момент когда на узел ссылаются только узлы с большим адресом и соответственно он удалится.
Так да, Вы в точности объяснили суть этой схемы, уточню что если на граф из объектов нет внешних сильных ссылок, то в нем в каждый момент времени будет узел, на который есть только слабые ссылки
Универсильный -- в худшем случае для всех возможных n-элементых последовательностей [различных элементов].
Подразумевается нижняя оценка, Вы имеете в виду, что мне стоило там написать ? Формально Вы правы, я просто зарекся не перегружать математическими терминами на хабре.
Не совсем понимаю, в чем вопрос, попытаюсь догадаться
Если Вы сравниваете реализации на Python и C одного и того же алгоритма на предмет времени работы, то стоит ожидать тотального проигрыша первого. Python -- это язык, который минимизирует время разработчика, C -- это язык который минимизирует runtime. В этой статье у меня не было цели сделать полноценные бенчмарки, мне важно было понятней объяснить концепцию, поэтому примеры на Python, для бенчмаркинга они не предназначены
Нотация асимптотического времени работы алгоритма означает, что есть какая-то глобальная константа C, что для любой последовательности размера n время работы будет не больше . К сожалению константа С может быть как очень маленькой, так и очень большой. Есть даже специальная категория алгоритмов, которые имеют хорошую асимптотическую сложность, но на практике бесполезны, потому что С там неприлично огромное
Зачем вообще тогда нужна асимптотика? Очень просто -- это первичный способ отсеивания плохих алгоритмов. Можно бенчмаркать всё подряд, а можно сначала отсеять совсем плохие по асимптотике и не переводить углеводороды просто так.
Для двусвязного списка ссылки вперед сильные, ссылки назад слабые -- циклов по сильным нет
Для бинарного дерева поиска ссылки на потомков сильные, на предков (ели нужны) слабые -- тоже циклов нет
В произвольной графовой структуре делаем что-то такое: делаем специальный указатель, который а) сильный если номинально указывает на область памяти с бОльшим номером, чем адрес объекта, где он используется; б) слабый в обратном случае
Первые два я на практике несколько раз использовал. 3ий придумал пока читал статью и честно говоря сомневаюсь, что до меня никто такого не предлагал. Сходу у 3 вижу несколько потенциальных проблем, но они кажутся решаемыми.
А Вы пробовали когди-нибудь в TAoCP найти какую-то конкретную информацию? Я вот пробовал -- менее эффективно я еще никогда времени не проводил. Была у меня и совсем забавная история: я пытался найти одно утверждение, на которое раньше там натыкался -- не нашел. Задал вопрос дипсику -- он нашел только послу уточнения со ссылками на несколько разделов -- и это все равно не помогло. После 1,5 часов прочтения единственное, что я понял -- это то, что искомое утверждение было в 3 томе Кнута, но где именно я хз.
Ваше предложение примерно равнозначно "идите закончите магистратуру по CS, без этого я с Вами говорит не буду"
P. S. Кнут -- великий человек, TAoCP -- это безусловно монументальный труд. Проблема в том, что он слишком монументальный и по современным меркам испытывает явные проблемы с индексацией. TAoCP -- это последнее место, которое я бы рекомендовал для изучения, только когда во всех остальных источниках я нужного материала не нашел
Даже самый тупой тренер в самом затрапезном фитнес зале знает, что если появились боль и стресс -- можно начинать считать. Вот это "следует немедленно прекратить занятия" -- это для новичков, чтобы они не сдохли и не подали в суд на тренера.
порванных связок и сломанного носа точно не будет
вместо этого там кукуха едет (не совсем пример в тему, но вон посмотрите на Илона).
Продолжая аналогию с залом: если цель занятий в тренажерке -- это подкачать пятую точку и выложить её в инсту или оф, то смысла горбатиться нет никакого. Если вы профессиональный спортсмен -- мне почему-то кажется очевидным, что стоит прислушиваться к Мухамеду Али, а не к диванному аналитику.
https://habr.com/ru/companies/ruvds/articles/892306/
Буквально недавно была хорошая статья, её еще можно заапвоутить. Там много ссылок на реализации сортировка на CUDA
Как узнаете -- напишите статью)
Приведенный в статье код имеет познавателтно-развлекательный характер и используется для верификации теорем, про которые я писал. Этот код не претендует на оптимальность, поэтому и проводить детальный анализ и тем более бенчмаркать его нет никакого смысла.
Рекомендую прочитать эту статью
https://habr.com/ru/articles/662181/
Там на большинство ваших вопросов ответы есть
Вполне допускаю. Если хотите предметного обсуждения -- нужны конкретные реализации и бенчмарки
Почему это воскресает, живее всех живых! std::sort неприменим к std::list, он рассчитан на RandomAccessIterator, для которого работает Inplace. А вот mergesort inplace для std::list и собственно std::list::sort -- это вариации mergesort. Тимсорт -- продвинутый mergesort
Смотрите, тут есть два независимых друг от друга множества, по которому можно брать минимум/среднее/максимум
Множество возможных алгоритмов
Множество возможных входных данных
Когда говорят про лучший/худший/в среднем случаи конкретного алгоритма, то имеют в виду, что на лучшем/в среднем/худшем наборе данных будет вот как-то так.
В теореме утверждается, что лучший алгоритм сортировки по худшему набору данных будет делать
, омега в данным случае относится к алгоритму, а не к данным
Не совсем, "бесполезная фигня" она ровно в том плане, что по количеству свопов она такая же как сортировка вставками, а по количеству сравнений всегда ей проигрывает. Именно для этого во всех примерах происходит подсчет и того и другого, и выбраны они именно для наглядности.
UPD. По-хорошему наверно стоит сравнивать пузырек с оптимизацией "если за целый проход по внутреннему циклу ничего не произошло, то остановиться" -- это при желании можно сделать самостоятельно
Отличие в том, что пока есть внешние безусловные сильные ссылки, то такой объект будет держать сам себя, но когда они исчезнут, то сразу распадётся. Я сейчас проверяю теорию, не до конца у меня все сходится, кажется, что объект может развалиться частично, но как будто идея стоит рассмотрения
Немного подумал, попробую вот так расписать. Пусть у нас есть unique_ptr и shared_ptr -- стандартные для C++ сильные указатели. Докидываем к ним mixed_ptr, работающий по 3 варианту моего описания. Если развивать идею автора с запретом ссылок можно договориться, что для shared и unique они запрещены, а для mixed нет. Но я скорее думал в направлении, что на стеке все ссылки shared/unique, а в heap -- mixed.
Это лучший случай, а не худший
Так да, Вы в точности объяснили суть этой схемы, уточню что если на граф из объектов нет внешних сильных ссылок, то в нем в каждый момент времени будет узел, на который есть только слабые ссылки
Универсильный -- в худшем случае для всех возможных n-элементых последовательностей [различных элементов].
Подразумевается нижняя оценка, Вы имеете в виду, что мне стоило там написать
? Формально Вы правы, я просто зарекся не перегружать математическими терминами на хабре.
Не совсем понимаю, в чем вопрос, попытаюсь догадаться
Если Вы сравниваете реализации на Python и C одного и того же алгоритма на предмет времени работы, то стоит ожидать тотального проигрыша первого. Python -- это язык, который минимизирует время разработчика, C -- это язык который минимизирует runtime. В этой статье у меня не было цели сделать полноценные бенчмарки, мне важно было понятней объяснить концепцию, поэтому примеры на Python, для бенчмаркинга они не предназначены
Нотация
асимптотического времени работы алгоритма означает, что есть какая-то глобальная константа C, что для любой последовательности размера n время работы будет не больше 
. К сожалению константа С может быть как очень маленькой, так и очень большой. Есть даже специальная категория алгоритмов, которые имеют хорошую асимптотическую сложность, но на практике бесполезны, потому что С там неприлично огромное
Зачем вообще тогда нужна асимптотика? Очень просто -- это первичный способ отсеивания плохих алгоритмов. Можно бенчмаркать всё подряд, а можно сначала отсеять совсем плохие по асимптотике и не переводить углеводороды просто так.
Вы это к чему?
Почему не сделать так:
Для двусвязного списка ссылки вперед сильные, ссылки назад слабые -- циклов по сильным нет
Для бинарного дерева поиска ссылки на потомков сильные, на предков (ели нужны) слабые -- тоже циклов нет
В произвольной графовой структуре делаем что-то такое: делаем специальный указатель, который а) сильный если номинально указывает на область памяти с бОльшим номером, чем адрес объекта, где он используется; б) слабый в обратном случае
Первые два я на практике несколько раз использовал. 3ий придумал пока читал статью и честно говоря сомневаюсь, что до меня никто такого не предлагал. Сходу у 3 вижу несколько потенциальных проблем, но они кажутся решаемыми.
А Вы пробовали когди-нибудь в TAoCP найти какую-то конкретную информацию? Я вот пробовал -- менее эффективно я еще никогда времени не проводил. Была у меня и совсем забавная история: я пытался найти одно утверждение, на которое раньше там натыкался -- не нашел. Задал вопрос дипсику -- он нашел только послу уточнения со ссылками на несколько разделов -- и это все равно не помогло. После 1,5 часов прочтения единственное, что я понял -- это то, что искомое утверждение было в 3 томе Кнута, но где именно я хз.
Ваше предложение примерно равнозначно "идите закончите магистратуру по CS, без этого я с Вами говорит не буду"
P. S. Кнут -- великий человек, TAoCP -- это безусловно монументальный труд. Проблема в том, что он слишком монументальный и по современным меркам испытывает явные проблемы с индексацией. TAoCP -- это последнее место, которое я бы рекомендовал для изучения, только когда во всех остальных источниках я нужного материала не нашел
Хорошим тоном было бы указать это в начале статьи.
Даже самый тупой тренер в самом затрапезном фитнес зале знает, что если появились боль и стресс -- можно начинать считать. Вот это "следует немедленно прекратить занятия" -- это для новичков, чтобы они не сдохли и не подали в суд на тренера.
вместо этого там кукуха едет (не совсем пример в тему, но вон посмотрите на Илона).
Продолжая аналогию с залом: если цель занятий в тренажерке -- это подкачать пятую точку и выложить её в инсту или оф, то смысла горбатиться нет никакого. Если вы профессиональный спортсмен -- мне почему-то кажется очевидным, что стоит прислушиваться к Мухамеду Али, а не к диванному аналитику.
FYI на хабре уже есть добротная статья
https://habr.com/ru/companies/vk/articles/479822/
Оказалось, что я забыл привести код для параллельного разворота битов, исправил.