Отличие в том, что пока есть внешние безусловные сильные ссылки, то такой объект будет держать сам себя, но когда они исчезнут, то сразу распадётся. Я сейчас проверяю теорию, не до конца у меня все сходится, кажется, что объект может развалиться частично, но как будто идея стоит рассмотрения
Немного подумал, попробую вот так расписать. Пусть у нас есть 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 -- это последнее место, которое я бы рекомендовал для изучения, только когда во всех остальных источниках я нужного материала не нашел
Даже самый тупой тренер в самом затрапезном фитнес зале знает, что если появились боль и стресс -- можно начинать считать. Вот это "следует немедленно прекратить занятия" -- это для новичков, чтобы они не сдохли и не подали в суд на тренера.
порванных связок и сломанного носа точно не будет
вместо этого там кукуха едет (не совсем пример в тему, но вон посмотрите на Илона).
Продолжая аналогию с залом: если цель занятий в тренажерке -- это подкачать пятую точку и выложить её в инсту или оф, то смысла горбатиться нет никакого. Если вы профессиональный спортсмен -- мне почему-то кажется очевидным, что стоит прислушиваться к Мухамеду Али, а не к диванному аналитику.
По поводу константного времени. Подразумевается, что у вас есть какая-то статическая структура, которую вы долго (ну или не очень, но уж точго не за константу, а хотя бы за один проход) инициализируете, а потом к ней применяете какие-то запросы (в данном случае rank-select). Инициализация долгая, но запросы быстрые. Вот простой пример как сделать rank-select за константу, но не succint:
Изначально у нас есть последовательность битов v_1, v_2, ... v_n.
Вычисляем за линейный проход частичные суммы s_i=s_{i-1}+v_i и кладем в массив. rank(i) -- это просто s_i
Вычисляем за линейный проход чем-то вроде `for(i = 0; i < v.size(); ++i) { if (v[i] ) p.push_back(i); }` в итоге в массиве p у нас позиции единичных битов, select(i) -- это просто p[i].
Собственно ценность succint структур в том, чтобы не хранить два отдельных вектора с числами, а делать это как-то хитро, чтобы занимало меньше памяти.
P. S. Я сам очень увлекаюсь такими структурами и если на хабре есть такой запрос, то с удовольствием сделаю подробный обзор по ним. Для самостоятельного изучаения рекомендую вот эту репу
Это вы меня комментировали? Не понял про что вы, как и, если честно, каждое Ваше сообщение в этом треде.
Позвольте дать совет, о котором Вы не просили: судя по всему у Вас плохо получается общаться с людьми и доносить свои мысли до других. Это нормально и часто встречается у технических специалистов, но вот когда даже опытные коллеги по цеху говорят вам, что ничего не понятно -- стоит что-то менять в себе.
Далее для сравнения список сортируется встроенным сортировщиком (в .NET метод Array.Sort()), где на таком объёме работает алгоритм «Пирамидальная сортировка» (а на меньшем объёме — QuickSort)
Очень удивился. Пошерстил код, кажется как и в gcc там все-таки IntroSort -- сначала quicksort пока не превысили предел вложенности рекурсии, потом heapsort, а на блоках длины <=16 insertion sort
Прочитал эту статьи и парочку из тех, что вы указали в списке литературы. Сложилось впечатление, что вы рассматриваете гораздо более частную оптимальность, чем заявленную в заголовке. Больше всего меня например спутала заглавная картинка, которая обычно приводится для противопоставления централизованного и децентрализованного сценария, и я полагал что статья про это, но ошибся.
У А. Гасникова тьма добротных публикаций по теме, что ж вы земляка своего нигде не цитируете? Неужели Сколково с Иннополисом не дружат?
В любом случае спасибо за очень грамотную с математической точки зрения статью, я вот лично больше не готов писать на хабре статей с большим количеством формул.
В алгоритмике крутейшая страница про деревья отрезков и дерево Фенвика с векторизцией и укладыванием в кэш. И это лучший мануал по ним, который я вообще видел в сети (для полноты картины добавлю основную ссылку со страницы)
Отличие в том, что пока есть внешние безусловные сильные ссылки, то такой объект будет держать сам себя, но когда они исчезнут, то сразу распадётся. Я сейчас проверяю теорию, не до конца у меня все сходится, кажется, что объект может развалиться частично, но как будто идея стоит рассмотрения
Немного подумал, попробую вот так расписать. Пусть у нас есть 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/
Оказалось, что я забыл привести код для параллельного разворота битов, исправил.
Хорошо, готовлю
По поводу константного времени. Подразумевается, что у вас есть какая-то статическая структура, которую вы долго (ну или не очень, но уж точго не за константу, а хотя бы за один проход) инициализируете, а потом к ней применяете какие-то запросы (в данном случае rank-select). Инициализация долгая, но запросы быстрые. Вот простой пример как сделать rank-select за константу, но не succint:
Изначально у нас есть последовательность битов v_1, v_2, ... v_n.
Вычисляем за линейный проход частичные суммы s_i=s_{i-1}+v_i и кладем в массив. rank(i) -- это просто s_i
Вычисляем за линейный проход чем-то вроде `for(i = 0; i < v.size(); ++i) { if (v[i] ) p.push_back(i); }` в итоге в массиве p у нас позиции единичных битов, select(i) -- это просто p[i].
Собственно ценность succint структур в том, чтобы не хранить два отдельных вектора с числами, а делать это как-то хитро, чтобы занимало меньше памяти.
P. S. Я сам очень увлекаюсь такими структурами и если на хабре есть такой запрос, то с удовольствием сделаю подробный обзор по ним. Для самостоятельного изучаения рекомендую вот эту репу
https://github.com/simongog/sdsl-lite
Это вы меня комментировали? Не понял про что вы, как и, если честно, каждое Ваше сообщение в этом треде.
Позвольте дать совет, о котором Вы не просили: судя по всему у Вас плохо получается общаться с людьми и доносить свои мысли до других. Это нормально и часто встречается у технических специалистов, но вот когда даже опытные коллеги по цеху говорят вам, что ничего не понятно -- стоит что-то менять в себе.
Очень удивился. Пошерстил код, кажется как и в gcc там все-таки IntroSort -- сначала quicksort пока не превысили предел вложенности рекурсии, потом heapsort, а на блоках длины <=16 insertion sort
Прочитал эту статьи и парочку из тех, что вы указали в списке литературы. Сложилось впечатление, что вы рассматриваете гораздо более частную оптимальность, чем заявленную в заголовке. Больше всего меня например спутала заглавная картинка, которая обычно приводится для противопоставления централизованного и децентрализованного сценария, и я полагал что статья про это, но ошибся.
У А. Гасникова тьма добротных публикаций по теме, что ж вы земляка своего нигде не цитируете? Неужели Сколково с Иннополисом не дружат?
В любом случае спасибо за очень грамотную с математической точки зрения статью, я вот лично больше не готов писать на хабре статей с большим количеством формул.
Динамический массив, и в питоне всегда по умолчанию ссылки на элементы
В алгоритмике крутейшая страница про деревья отрезков и дерево Фенвика с векторизцией и укладыванием в кэш. И это лучший мануал по ним, который я вообще видел в сети (для полноты картины добавлю основную ссылку со страницы)