О! Когда-то хотел написать про это статью, но заленился Спасибо, что взяли на себя.
Зачем нужна вся история с многоагентным поиском? Она появляется только во введении и нигде дальше не используется (и это замечательно). Мне кажется всё это можно выбросить и посвятить статью просто приоритетным очередям на основе куч. Которые можно использовать не только в поиске но и в какой-нибудь в обработке запросов (ну или где ещё нужны приоритетные очереди). Тема отличная, и совсем не обязательно хвастаться, что вы знаете, что такое tf-idf и ещё много умных слов, не имеющих отношения к делу
По С-шному интерфейсу, лучше так:
bool empty() --> bool empty() const
int size() --> int size() const (size_t size() const)
int push(T obj) --> int push(const T& obj)
T top() --> const T& top() const
bool change(int id, T new_obj) --> bool change(int id, const T& new_obj)
Лишние константы не помешают, а лишних копирований стоит избегать (на случай если T вдруг окажется не int-ом).
Идея с id-шниками в общей реализации кажется мне сомнительной. Она нужна только когда нужна, а тормозить будет всегда. Может быть сделать отдельную реализацию?
>> В литературе обычно умалчивается информация об авторе данной структуры данных,
Скрывают!
Умалчивание это сознательное сокрытие известной информации.
Думаю, что этот смысл тут не подходит, а значит и слово нужно другое.
>> Рисунок 2. Хранение кучи в виде массива. Верхний ряд – индекс элемента, нижний – числовое значение
Даже при том, что я знаю, как устроена бинарная куча, c первого взгляда я ничего не понял. Вот эти синие -- это от кого куда? Почему только по одной, детей же двое? Синие сверху и синие снизу как-то связаны?
Со второго взгляда, прикинув, как должно быть, я понял, что сверху одна половина, а снизу другая. Но в общем картинка неудачна, ничего не проясняет.
>> При этом может произойти нарушения целостности кучи (см. п. 2).
Я бы не называл это целостностью... Или это устоявшееся словоприменение?
>> Т.к. дерево является бинарным, то сложность данной операции O(log(N)).
Я бы ещё отметил, что это не просто бинарное дерево, а это всегда идеально сбалансированное бинарное дерево. Именно поэтому гарантируется O(log(N))
>> Перед тем как удалить элемент, его необходимо сделать корневым. Для этого можно проинициализировать текущий элемент значением меньшим, чем минимальный элемент кучи, и выполнить предыдущий пункт. После этого выполнить операцию удаления минимального элемента кучи.
??
Почему нельзя просто поменять местами с последним, т.е. удалить по тому же алгоритму, что и корневой?
>> Учитывая возможности современного компьютера и адекватных потребностей при использовании биномиальной кучи можно ограничить общее количество элементов в ней до 231-1.
Что-то не так с русским языком.
>> Для удаления элемента необходимо сначала сделать его корневым узлом пирамидального дерева, в котором он находится, после чего удалить корневой узел этого дерева. Проще всего это сделать, если присвоить данному элементу значение меньшее, чем у минимального элемента всей биномиальной кучи.
Здесь это хотя бы осмысленно, хотя тоже не оптимально.
>> Рисунок 9. Пример корректного фибоначчиева дерева.
Много стрелочек, которые на рисунке выглядят одинаково, а на самом деле принципиально отличаются. Три типа:
— ссылка на ребёнка
— ссылка на родителя
— ссылки между братьями
Может их как-то различать? Или хотя бы убрать ссылки на родителей?
>> Но, тем не менее, амортизированная сложность ее O(logN)[6].
Что такое "амортизированная сложность"? Я легко могу не знать этого термина, это нормально. Средняя ожидаемая сложность?
>> Демонстрационный проект
А можно вместо Дейкстры приложить код, который позволяет посчитать статистику? Меня честно говоря удивила бинарная куча, я думал хотя бы в первом тесте она будет достаточно хороша. А вот втором по идее, она должна отставать более чем линейно из-за долгих объединений, разве нет? В общем, что-то меня смущают полученные результаты. Кстати, а что там на осях, секунды и количество элементов? Надо бы упомянуть где-нибудь.
Делай что должно, и будь что будет
Re: Приоритетная очередь на основе бинарной, биномиальной и
Кстати, ещё по поводу id. Насколько я понял реализацию, для бинарной кучи сложность _умножается_ на logN, так как там на каждую операцию перемещения приходится перестраивать таблицы, а для остальных _суммируется_ с logN, так как указатели на узлы остаются теми же.
Можете пересчитать статистику с отключенными id? Если я прав, бинарная куча должна вырваться вперёд
И ещё, на картинках со статистикой графики бинарных куч подозрительно совпадают, хотя тесты вроде как разные. Тут точно нет ошибки?
Делай что должно, и будь что будет
Re: Приоритетная очередь на основе бинарной, биномиальной и фибо
Сорри, а автор в курсе, что я ему ответил?
Тему создавал не он (кстати, предлагаю это как-нибудь изменить, пусть сами создают), так что письма он автоматически не получил, мог и не догадаться посмотреть на форуме.
Можно ему как-нибудь сообщить? В профиле нет его email-а, но у редакции по идее должен быть.
Делай что должно, и будь что будет
Re[2]: Приоритетная очередь на основе бинарной, биномиальной и
K>>Код к статье
SH>О! Когда-то хотел написать про это статью, но заленился Спасибо, что взяли на себя.
SH>Зачем нужна вся история с многоагентным поиском? Она появляется только во введении и нигде дальше не используется (и это замечательно). Мне кажется всё это можно выбросить и посвятить статью просто приоритетным очередям на основе куч. Которые можно использовать не только в поиске но и в какой-нибудь в обработке запросов (ну или где ещё нужны приоритетные очереди). Тема отличная, и совсем не обязательно хвастаться, что вы знаете, что такое tf-idf и ещё много умных слов, не имеющих отношения к делу
Если бы изначально была задача написать статью про приоритетные очереди, то конечно бы не было этого утомительного введения про многоагентный поиск. Мне нужно было показать использование различных видов приоритетных очередей конкретно в информационном поиске на примере конкретной задачи. Собственно сама задача была описана только во введении. А дальше описывается обобщенная реализация приоритетной очереди вне зависимости от предметной области. И в конце демонстрационный пример также имеет обобщенный характер.
SH>По С-шному интерфейсу, лучше так:
SH>bool empty() --> bool empty() const SH>int size() --> int size() const (size_t size() const) SH>int push(T obj) --> int push(const T& obj) SH>T top() --> const T& top() const SH>bool change(int id, T new_obj) --> bool change(int id, const T& new_obj)
SH>Лишние константы не помешают, а лишних копирований стоит избегать (на случай если T вдруг окажется не int-ом).
Согласен.
SH>Идея с id-шниками в общей реализации кажется мне сомнительной. Она нужна только когда нужна, а тормозить будет всегда. Может быть сделать отдельную реализацию?
Идея с id-шниками появилась и реализовывалась только из-за того, что разные кучи имеют различную внутреннюю организацию, и только для того, чтобы приоритетная очередь вне зависимости от внутренней кучи имела один и тот же интерфейс.
>>> В литературе обычно умалчивается информация об авторе данной структуры данных,
SH>Скрывают! SH>Умалчивание это сознательное сокрытие известной информации. SH>Думаю, что этот смысл тут не подходит, а значит и слово нужно другое.
>>> Рисунок 2. Хранение кучи в виде массива. Верхний ряд – индекс элемента, нижний – числовое значение
SH>Даже при том, что я знаю, как устроена бинарная куча, c первого взгляда я ничего не понял. Вот эти синие -- это от кого куда? Почему только по одной, детей же двое? Синие сверху и синие снизу как-то связаны?
SH>Со второго взгляда, прикинув, как должно быть, я понял, что сверху одна половина, а снизу другая. Но в общем картинка неудачна, ничего не проясняет.
Возможно рисунок не самый удачный.
>>> При этом может произойти нарушения целостности кучи (см. п. 2).
SH>Я бы не называл это целостностью... Или это устоявшееся словоприменение?
Скорее устоявшееся. Если вам известно другое определение этого понятия, пожалуйста поделитесь.
>>> Т.к. дерево является бинарным, то сложность данной операции O(log(N)).
SH>Я бы ещё отметил, что это не просто бинарное дерево, а это всегда идеально сбалансированное бинарное дерево. Именно поэтому гарантируется O(log(N))
Полностью согласен.
>>> Перед тем как удалить элемент, его необходимо сделать корневым. Для этого можно проинициализировать текущий элемент значением меньшим, чем минимальный элемент кучи, и выполнить предыдущий пункт. После этого выполнить операцию удаления минимального элемента кучи.
SH>??
SH>Почему нельзя просто поменять местами с последним, т.е. удалить по тому же алгоритму, что и корневой?
Если просто поменять местами с последним, то может возникнуть ситуация, при которой целостность кучи будет нарушена двумя элементами. А представленные алгоритмы могут восстановить целостность кучи только если она нарушена не более одним элементом.
>>> Учитывая возможности современного компьютера и адекватных потребностей при использовании биномиальной кучи можно ограничить общее количество элементов в ней до 231-1.
SH>Что-то не так с русским языком.
Согласен.
>>> Для удаления элемента необходимо сначала сделать его корневым узлом пирамидального дерева, в котором он находится, после чего удалить корневой узел этого дерева. Проще всего это сделать, если присвоить данному элементу значение меньшее, чем у минимального элемента всей биномиальной кучи.
SH>Здесь это хотя бы осмысленно, хотя тоже не оптимально.
Идея та же самая, что и в прошлый раз. Что подразумевается под оптимальным способом?
>>> Рисунок 9. Пример корректного фибоначчиева дерева.
SH>Много стрелочек, которые на рисунке выглядят одинаково, а на самом деле принципиально отличаются. Три типа: SH>- ссылка на ребёнка SH>- ссылка на родителя SH>- ссылки между братьями
SH>Может их как-то различать? Или хотя бы убрать ссылки на родителей?
Если стрелки разукрашивать, то получится слишком ярко. Если убрать ссылки на родителя, то может потеряться понимание общей организации кучи.
>>> Но, тем не менее, амортизированная сложность ее O(logN)[6].
SH>Что такое "амортизированная сложность"? Я легко могу не знать этого термина, это нормально. Средняя ожидаемая сложность?
Гарантируется средняя производительность операций в наишудшем случае.
>>> Демонстрационный проект
SH>А можно вместо Дейкстры приложить код, который позволяет посчитать статистику? Меня честно говоря удивила бинарная куча, я думал хотя бы в первом тесте она будет достаточно хороша. А вот втором по идее, она должна отставать более чем линейно из-за долгих объединений, разве нет? В общем, что-то меня смущают полученные результаты. Кстати, а что там на осях, секунды и количество элементов? Надо бы упомянуть где-нибудь.
Проект для подсчета статистики: http://goo.gl/FLxlR (подцепляйте нужные файлы: test_speed_0.cpp или test_speed_1.cpp)
Бинарная куча в первом тесте проигрывает из-за того, что высота поддерева, в котором происходит просейка вверх/вниз всегда будет больше, чем у биномиальной или фибоначчиевой кучи.
По поводу второго теста вы правы, там отставание не линейное, а квазилинейное, т.к. сложность объединения O(N*logN).
На осях секунды и количество элементов. Проглядел. Спасибо, что заметили.
Re[2]: Приоритетная очередь на основе бинарной, биномиальной и
K>>Код к статье
SH>Кстати, ещё по поводу id. Насколько я понял реализацию, для бинарной кучи сложность _умножается_ на logN, так как там на каждую операцию перемещения приходится перестраивать таблицы, а для остальных _суммируется_ с logN, так как указатели на узлы остаются теми же.
Вообще для каждого вида куч сложность любой операции умножается на logN.
Для биномиальной и фибоначчиевой куч указатели на узлы остаются, но сами элементы, которые хранятся в узлах "гуляют" по дереву. Поэтому id-шники должны обновляться при каждой операции swap. Сейчас я не могу понять, почему они не обновляются в фибоначчиевой куче. Возможно недостаточно хорошо тестировал операцию change.
SH>Можете пересчитать статистику с отключенными id? Если я прав, бинарная куча должна вырваться вперёд
Отключение id приведет к тому, что появится 3 различные реализации приоритетной очереди без единого интерфейса. Изначально поддержка единого интерфейса была одной из основных задач, поэтому данное действие противоречит первоначальной задумке.
SH>И ещё, на картинках со статистикой графики бинарных куч подозрительно совпадают, хотя тесты вроде как разные. Тут точно нет ошибки?
Да здесь есть ошибка.
Переделал графики:
Тест 1:
Тест 2:
Сергей, спасибо Вам за ценные замечания и вдумчивое изучение материала.
Re[3]: Приоритетная очередь на основе бинарной, биномиальной и
Здравствуйте, slipstak2, Вы писали:
S>Если бы изначально была задача написать статью про приоритетные очереди, то конечно бы не было этого утомительного введения про многоагентный поиск. Мне нужно было показать использование различных видов приоритетных очередей конкретно в информационном поиске на примере конкретной задачи. Собственно сама задача была описана только во введении. А дальше описывается обобщенная реализация приоритетной очереди вне зависимости от предметной области. И в конце демонстрационный пример также имеет обобщенный характер.
Т.е. эта статья в рамках какой-нибудь кандидатской-диплома-етс, и по формальным причинам Вам нужно это упомянуть.
Идея понятна. Нельзя ли это как-нибудь вынести за пределы статьи? Или минимизировать вступление. Примерно так:
— достаточно общё сформулировать задачу, решаемую приоритетными очередями
— уточнить, что в частности их можно использовать для хранения документов и получения списка наиболее релевантных.
Мне просто жалко читателей, которым эта часть не нужна вообще. Для того чтобы что-то узнать о поиске там слишком мало, а для введения слишком много.
S>Идея с id-шниками появилась и реализовывалась только из-за того, что разные кучи имеют различную внутреннюю организацию, и только для того, чтобы приоритетная очередь вне зависимости от внутренней кучи имела один и тот же интерфейс.
Я имел ввиду, что id используются только в операции change. Если в конкретной ситуации нам не нужна эта операция, можно было бы без них обойтись.
SH>>Я бы не называл это целостностью... Или это устоявшееся словоприменение? S>Скорее устоявшееся. Если вам известно другое определение этого понятия, пожалуйста поделитесь.
Обычно в таких случаях говорят что-то про сохранение инвариантов, может быть действительно "целостность" это правильное слово для описания состояния выполнения инвариантов, тем более если оно используется в литературе.
S>Если просто поменять местами с последним, то может возникнуть ситуация, при которой целостность кучи будет нарушена двумя элементами. А представленные алгоритмы могут восстановить целостность кучи только если она нарушена не более одним элементом.
Не совсем понял, как.
Берём элемент, меняем его с последним, после чего выкидываем.
После чего применяем к бывшему последнему, оказавшемуся в неправильном месте, алгоритм для "просеивания вниз".
Где подвох? Можете привести пример, на котором этот вариант ломается?
Кстати, если всё так, как Вы говорите, возможно, стоит добавить пример в статью, т.к. подобная "оптимизация" приходит в голову моментально, если она что-то рушит, стоит это показать.
>>>> Для удаления элемента необходимо сначала сделать его корневым узлом пирамидального дерева, в котором он находится, после чего удалить корневой узел этого дерева. Проще всего это сделать, если присвоить данному элементу значение меньшее, чем у минимального элемента всей биномиальной кучи.
SH>>Здесь это хотя бы осмысленно, хотя тоже не оптимально. S>Идея та же самая, что и в прошлый раз. Что подразумевается под оптимальным способом?
Честно говоря не помню уже Видимо, два месяца назад у меня была какая-то мысль, как сделать это оптимальнее. Сейчас не могу сказать.
S>Если стрелки разукрашивать, то получится слишком ярко. Если убрать ссылки на родителя, то может потеряться понимание общей организации кучи.
Использовать пунктир и пояснить в подписи, какие что означают?
S>Проект для подсчета статистики: http://goo.gl/FLxlR (подцепляйте нужные файлы: test_speed_0.cpp или test_speed_1.cpp) S>Бинарная куча в первом тесте проигрывает из-за того, что высота поддерева, в котором происходит просейка вверх/вниз всегда будет больше, чем у биномиальной или фибоначчиевой кучи. S>По поводу второго теста вы правы, там отставание не линейное, а квазилинейное, т.к. сложность объединения O(N*logN).
Скачал, постараюсь сегодня посмотреть.
Делай что должно, и будь что будет
Re[4]: Приоритетная очередь на основе бинарной, биномиальной и
Здравствуйте, SergH, Вы писали:
S>>Если просто поменять местами с последним, то может возникнуть ситуация, при которой целостность кучи будет нарушена двумя элементами. А представленные алгоритмы могут восстановить целостность кучи только если она нарушена не более одним элементом.
SH>Не совсем понял, как. SH>Берём элемент, меняем его с последним, после чего выкидываем. SH>После чего применяем к бывшему последнему, оказавшемуся в неправильном месте, алгоритм для "просеивания вниз". SH>Где подвох? Можете привести пример, на котором этот вариант ломается?
Здесь я не прав. Нет подвоха, все будет работать так, как Вы написали.
Re[5]: Приоритетная очередь на основе бинарной, биномиальной и
Здравствуйте, slipstak2, Вы писали:
SH>>Не совсем понял, как. SH>>Берём элемент, меняем его с последним, после чего выкидываем. SH>>После чего применяем к бывшему последнему, оказавшемуся в неправильном месте, алгоритм для "просеивания вниз". SH>>Где подвох? Можете привести пример, на котором этот вариант ломается?
S>Здесь я не прав. Нет подвоха, все будет работать так, как Вы написали.
Ну, только иногда надо будет запускать просеивание не вниз, а вверх. Если бывший нижний узел окажется не в "своей" ветке дерева, он может оказаться и меньше.
По поводу тестов.
Во-первых, VC++ очень добрый компилятор, если такое пропускает Для gcc мне пришлось немного допилить шаблоны.
(см. в теме и по ссылкам в ответе Павла Кузнецова)
Решается при помощи this->get_next_i() и using base::node_by_id.
Аналогично с остальными двумя кучами.
Во-вторых, Ваши результаты у меня подтвердились и даже время примерно то же (я только test_speed_0 запускал).
В-третьих, я поставил эксперимент. Убрал наследование от base_head, все id-шники и заменил _less на <.
Бинарная куча всех сделала Хотя тут результаты очень близкие, она только немного быстрее биномиальной. По соотношениям с исходной версией -- биномиальная ускорилась примерно в 5 раз. И наибольшую роль тут играют именно id-шники. _less компилятор подставляет довольно эффективно, вызовы виртуальных функций тоже, видимо, не производит, вызывает напрямую, а вот с этими картами возиться приходится (я проверял, как меняется скорость, если оставить base_heap, но убрать из _swap перестановку в картах и из push/pop добавление/удаление связей). Вот примерно так операции change и remove влияют на общую производительность кучи.
В-четвёртых, чтобы делать подробные замечания по коду мне надо разобраться в нём глубже, не уверен, что буду это делать. Но вот функции check_XXX_heap и XXXX_0 из модуля test_speed_0.cpp просто так и просятся на то, чтобы сделать их шаблонными и передавать тип кучи в параметре.
По поводу введения. Если я прав, и статья для диплома/кандидатской, наверное, у Вас есть научный руководитель? Обсудите с ним, может это можно сделать как-то изящнее. Просто я вспомнил анекдот Про студента, который перед экзаменом по зоологии выучил только про блох, и отвечал примерно так "медведь это такой большой зверь, у него есть четыре лапы, голова и хвост. Он весь покрытый шерстью. В шерсти медведя водятся блохи. Так вот о блохах ..." В текущем виде статья построена по такой же модели. Мне кажется, должен быть лучший вариант.
Делай что должно, и будь что будет
Re[5]: Приоритетная очередь на основе бинарной, биномиальной и
Итого. Вроде бы все замечания понятны. Дорабатывайте статью и как-нибудь выкладывайте. Не уверен, что submit@rsdn.ru сработает, хотя и туда тоже можно послать.
А я пока попробую связаться с Михаилом Купаевым, что-то он подозрительно долго молчит и функции свои не выполняет.
Спасибо, что взяли на себя. 
Видимо, два месяца назад у меня была какая-то мысль, как сделать это оптимальнее. Сейчас не могу сказать. 