Вот про перетановки я как раз понимал и догадался до "сортируем ссылки хорошей сортировкой, свопаем оъекты по циклам" (и по хорошему на практике только так и надо делать), но то, что сортировка выбором делает вторую часть -- это я упустил. Но ничего, получил бурю эмоций и урок на всю жизнь.
Для меня до сих не очевидно как быть если есть повторяющиеся элементы.
Приведенный в статье код имеет познавателтно-развлекательный характер и используется для верификации теорем, про которые я писал. Этот код не претендует на оптимальность, поэтому и проводить детальный анализ и тем более бенчмаркать его нет никакого смысла.
Почему это воскресает, живее всех живых! 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 -- это последнее место, которое я бы рекомендовал для изучения, только когда во всех остальных источниках я нужного материала не нашел
Вот про перетановки я как раз понимал и догадался до "сортируем ссылки хорошей сортировкой, свопаем оъекты по циклам" (и по хорошему на практике только так и надо делать), но то, что сортировка выбором делает вторую часть -- это я упустил. Но ничего, получил бурю эмоций и урок на всю жизнь.
Для меня до сих не очевидно как быть если есть повторяющиеся элементы.
А есть референс на т.3 вне 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 -- это последнее место, которое я бы рекомендовал для изучения, только когда во всех остальных источниках я нужного материала не нашел