Сталася такая беда, что надо сделать реализацию биномиальной кучи. Вроде много чего есть по этому поводу(наверное лучше всего на википедии буржуйской, там даже реализация на яве есть), но проблемка в том что везде чего-то не хватает, тоесть наскоком разобратся не получается.
Собственно просьба: если у кого нить есть реализация биномиальных куч (вставка, удаление минимального узла, слияние,...) на С++, Delphi или С# или если кто может подсказать где смотреть, пожалуйста, помогите.
З.Ы.: Нужна реализация именно биномиальной кучи, не бинарной и не очереди (как мне удалось разобратся, это не совсем то что надо). И Кормена с Седжвиком я уже смотрел, но по причине усталости после работы, разобратся с описанием алгоритмов не удалось(а очень надо), почему и опускаюсь до такой вот просьбы.
"...наставники более мудры не благодаря умению действовать, а потому, что они обладают отвлеченным знанием и знают причины..." Аристотель.
Здравствуйте, FallAngel, Вы писали:
FA>З.Ы.: Нужна реализация именно биномиальной кучи, не бинарной и не очереди (как мне удалось разобратся, это не совсем то что надо).
Кстати да, нафига она нужна, эта биномиальная куча? Насколько я понял, ее единственное преимущество перед бинарной кучей в том, что она сливается с другой кучей за O(log n) вместо O(n). Но на практике чтобы создать кучу или вытащить из нее все элементы, надо в обоих случаях O(n log n), так что характеристику общего времени работы алгоритма это не улучшает. Зачем же так изводить себя?
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>так что характеристику общего времени работы алгоритма это не улучшает.
Смотря какого алгоритма. Есть такие задачи, где слияний куч выполняется много, там как раз и нужны meldable heaps.
Здравствуйте, Mab, Вы писали:
S>>так что характеристику общего времени работы алгоритма это не улучшает. Mab>Смотря какого алгоритма. Есть такие задачи, где слияний куч выполняется много, там как раз и нужны meldable heaps.
Количество слияний куч никак не влияет на эту оценку. Так как каждую из этих сливаемых куч надо для начала создать, а это O(n log n). Вот если бы кучи не только сливались, но еще и "разливались", вот тогда от этого мог бы быть какой-то смысл. Ну или если бы было критично само по себе время на выполнение слияния куч (например, от него зависела бы задержка отклика на внешнее устройство), но это довольно нетипичная ситуация...
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>Количество слияний куч никак не влияет на эту оценку.
Конечно, сливаемые кучи придумали от того, что заняться нечем было.
S>Так как каждую из этих сливаемых куч надо для начала создать, а это O(n log n).
И что теперь? Сливать-то кучу можно с остальными многократно.
Простейший пример: имели n куч по одному элементу. Затем итеративно берем первую и вторую кучу из списка, сливаем и снова ставим в начало. Если куча meldable, то оценка будет O(n log n), а если нет -- то квадратичная.
Здравствуйте, Mab, Вы писали:
S>>Количество слияний куч никак не влияет на эту оценку. Mab> Mab>Конечно, сливаемые кучи придумали от того, что заняться нечем было.
В Computer Science вообще довольно много сомнительной ценности изобретений.
S>>Так как каждую из этих сливаемых куч надо для начала создать, а это O(n log n). Mab>И что теперь? Сливать-то кучу можно с остальными многократно. Mab>Простейший пример: имели n куч по одному элементу. Затем итеративно берем первую и вторую кучу из списка, сливаем и снова ставим в начало. Если куча meldable, то оценка будет O(n log n), а если нет -- то квадратичная.
Да-да, остается только еще эту получившуюся в итоге кучу выбросить и не использовать, и тогда выйдет пример, где такая куча реально нужна.
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>Да-да, остается только еще эту получившуюся в итоге кучу выбросить и не использовать, и тогда выйдет пример, где такая куча реально нужна.
Ну я же говорю -- пример простейший. Хотите сложный -- пожалуйста. Попробуйте найти minimum weight branching за O(E log V) без сливаемых очередей, будет очень интересно на это посмотреть.
Здравствуйте, Mab, Вы писали:
Mab>Ну я же говорю -- пример простейший. Хотите сложный -- пожалуйста. Попробуйте найти minimum weight branching за O(E log V) без сливаемых очередей, будет очень интересно на это посмотреть.
Нее, я предпочитаю попроще и попонятнее. За счет чего достигается, что при нахождении MWB выигрыш от применения сливаемых очередей не перекрывается эффектом от 1) образования и балансировки сливаемых очередей 2) вытягиванием элементов из слитой очереди?
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>За счет чего достигается, что при нахождении MWB выигрыш от применения сливаемых очередей не перекрывается эффектом от 1) образования и балансировки сливаемых очередей 2) вытягиванием элементов из слитой очереди?
Не понимаю смысл вопроса. Я же уже показал на примере, что от применения medlable heaps асимптотика может уменьшиться. Вот в этом алгоритме то же самое. Там делается порядка V слияний очередей суммарного размера E. За подробностями смотрите сам алгоритм.
@article
{
GGST-86,
author = {H. Gabow and Z. Galil and T. Spencer and R.Tarjan},
title = {Efficient algorithms for finding minimum spanning trees in undirected and directed graphs},
journal = {Combinatorica},
volume = {6},
number = {2},
year = {1986},
pages = {109--122},
}
Правда там еще более сильная версия с оценкой O(E + V log V) изложена.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, subdmitry, Вы писали:
S>>За счет чего достигается, что при нахождении MWB выигрыш от применения сливаемых очередей не перекрывается эффектом от 1) образования и балансировки сливаемых очередей 2) вытягиванием элементов из слитой очереди?
Mab>Не понимаю смысл вопроса. Я же уже показал на примере, что от применения medlable heaps асимптотика может уменьшиться.
Не показали, что потом делается с полученной очередью. Если из нее выбирать все элементы по одному, то это O(n log n) операций, что перекрывает выигрыш от применения быстросливаемых очередей. Можно, конечно, доставать их не все... Это и имеется в виду?
Mab>За подробностями смотрите сам алгоритм.
Сожалею, у меня сейчас нет доступа в библиотеку. А в электронном виде ее можно найти?
And if you listen very hard the alg will come to you at last.
Abstract Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time.
И никаких тебе биномиальных хипов.
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>Не показали, что потом делается с полученной очередью. Если из нее выбирать все элементы по одному, то это O(n log n) операций, что перекрывает выигрыш от применения быстросливаемых очередей. Можно, конечно, доставать их не все... Это и имеется в виду?
Какая разница, что с ней делается? Если сливать в лоб, создавая новую очередь за время, равное сумме размеров старых, то время работы будет как минимум квадратичным. И никакой n log n его не перекроет.
Или имелось в виду, что мы применяем "ранговую эвристику" -- добавляем элементы меньшей кучи в большую? Хорошо, пусть исходно есть n^{1/2} куч по n^{1/2} элементов. И пусть там надо слить их в одну кучу из n элементов по турнирной системе. Решение с meldable heaps c ценой слияния O(log n) работает за O(n^{1/2} (общее число слияний) * log n (время слияния)) = O(n^{1/2} log n).
А решение без medlable heaps требует порядка n * log^2 n времени. Это даже асимптотически больше, чем время построения этих куч тупым способом (путем последовательных вставок), не говоря уже о том, что многие виды куч допускают построение из начальной последовательности за линейное время.
S>Сожалею, у меня сейчас нет доступа в библиотеку. А в электронном виде ее можно найти?
Все это есть и в электронном виде (хотя бы в ACM Digital Library), но только доступ требует подписки.
Здравствуйте, subdmitry, Вы писали:
S>И никаких тебе биномиальных хипов.
Наверное не удивительно, учитывая, что F-heaps -- это их релаксация?
Вообще же практического толку от F-heaps не много.
Если не нужны слияния, то побеждают k-ary heaps и разные специфические вариации, заточенные под задачу (вроде multi-level buckets для shortest path problems). Если нужны слияния, но не нужны произвольные удаления, то лучше применять leftist или skew heaps.
Re: Биномиальные очереди
От:
Аноним
Дата:
12.06.08 20:54
Оценка:
Здравствуйте, FallAngel, Вы писали:
FA>Доброго времени суток.
FA> Сталася такая беда, что надо сделать реализацию биномиальной кучи. Вроде много чего есть по этому поводу(наверное лучше всего на википедии буржуйской, там даже реализация на яве есть), но проблемка в том что везде чего-то не хватает, тоесть наскоком разобратся не получается. FA>Собственно просьба: если у кого нить есть реализация биномиальных куч (вставка, удаление минимального узла, слияние,...) на С++, Delphi или С# или если кто может подсказать где смотреть, пожалуйста, помогите.
FA>З.Ы.: Нужна реализация именно биномиальной кучи, не бинарной и не очереди (как мне удалось разобратся, это не совсем то что надо). И Кормена с Седжвиком я уже смотрел, но по причине усталости после работы, разобратся с описанием алгоритмов не удалось(а очень надо), почему и опускаюсь до такой вот просьбы.
Здравствуйте, Mab, Вы писали:
Mab>Какая разница, что с ней делается? Если сливать в лоб, создавая новую очередь за время, равное сумме размеров старых, то время работы будет как минимум квадратичным. И никакой n log n его не перекроет.
Mab>Или имелось в виду, что мы применяем "ранговую эвристику" -- добавляем элементы меньшей кучи в большую? Хорошо, пусть исходно есть n^{1/2} куч по n^{1/2} элементов. И пусть там надо слить их в одну кучу из n элементов по турнирной системе. Решение с meldable heaps c ценой слияния O(log n) работает за O(n^{1/2} (общее число слияний) * log n (время слияния)) = O(n^{1/2} log n).
Да, тут согласен. Если сливать много мелких куч, то набегает квадрат логарифма. Так что если нет возможности слить все сразу в одну кучу, то выигрыш есть. Спасибо за объяснение.
Правда, все равно выгоднее сразу разбираться с кучами Фиббоначи как с более универсальной структурой данных, имеющей и более чудесатые свойства.
And if you listen very hard the alg will come to you at last.
Здравствуйте, Mab, Вы писали:
Mab>Наверное не удивительно, учитывая, что F-heaps -- это их релаксация? Mab>Вообще же практического толку от F-heaps не много.
Ну F-heaps хотя бы поддерживают уменьшение ключа за O(1), а биномиальные хипы — нет. Что, например, критично для shortest path problem.
Mab>Если не нужны слияния, то побеждают k-ary heaps и разные специфические вариации, заточенные под задачу (вроде multi-level buckets для shortest path problems). Если нужны слияния, но не нужны произвольные удаления, то лучше применять leftist или skew heaps.
Это уже результаты изучения практического значения констант времени выполнения этих алгоритмов? Просто на уровне O-оценки хипы Фиббоначи вполне так себе оптимальны.
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>Ну F-heaps хотя бы поддерживают уменьшение ключа за O(1), а биномиальные хипы — нет. Что, например, критично для shortest path problem.
Естественно. Но только получить практически эффективный алгоритм на F-heaps кажется не реально.
S>Это уже результаты изучения практического значения констант времени выполнения этих алгоритмов? Просто на уровне O-оценки хипы Фиббоначи вполне так себе оптимальны.
Все эти структуры слабее F-heaps. Но на практике они лучше, как по времени, так и по памяти.
Здравствуйте, Mab, Вы писали:
Mab>Все эти структуры слабее F-heaps. Но на практике они лучше, как по времени, так и по памяти.
Интересно. Я раньше такую штуку слышал только про PAT trie. Что, дескать, хотя она и имеет лучшую характеристику по сравнению с сортировкой массива суффиксов, но на деле существенно его тяжелее. Говорил это, правда, некто Sadakane, который продвигал свой собственный метод сортировки массива суффиксов на основе техники удвоения (гарантированно строится за O(n log n)). Не знаешь, это действительно так? Сейчас вот думаю, стоит ли прикручивать этот hi-teach (деревья суффиксов) к своему алгоритму сжатия.
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>Интересно. Я раньше такую штуку слышал только про PAT trie. Что, дескать, хотя она и имеет лучшую характеристику по сравнению с сортировкой массива суффиксов, но на деле существенно его тяжелее. Говорил это, правда, некто Sadakane, который продвигал свой собственный метод сортировки массива суффиксов на основе техники удвоения (гарантированно строится за O(n log n)). Не знаешь, это действительно так? Сейчас вот думаю, стоит ли прикручивать этот hi-teach (деревья суффиксов) к своему алгоритму сжатия.
Речь про suffix arrays vs suffix trees? Естественно на практике suffix arrays бывают сильно быстрее, и они всегда компактнее. Кроме того, сложность построения у них не зависит от мощности алфавита, в отличие от деревьев.
Что же касается n log n -- такой метод предлагали еще Manber и Meyers, которые эти массивы и придумали. Сейчас никто так суффисные массивы не строит. Уже лет 5 известные практические алгоритмы с линейным временем работы. Вот довольно популярный анализ практической эффективности:
Недавно рецензировал статью на FOCS08, там народ предлагает еще один алгоритм с линейным временем работы, который на практике еще быстрее существующих. Естественно, выигрыш не асимптотический, а измеряется в десятках процентов.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, subdmitry, Вы писали:
S>>Интересно. Я раньше такую штуку слышал только про PAT trie. Что, дескать, хотя она и имеет лучшую характеристику по сравнению с сортировкой массива суффиксов, но на деле существенно его тяжелее. Говорил это, правда, некто Sadakane, который продвигал свой собственный метод сортировки массива суффиксов на основе техники удвоения (гарантированно строится за O(n log n)). Не знаешь, это действительно так? Сейчас вот думаю, стоит ли прикручивать этот hi-teach (деревья суффиксов) к своему алгоритму сжатия.
Mab>Речь про suffix arrays vs suffix trees? Естественно на практике suffix arrays бывают сильно быстрее, и они всегда компактнее.
Да, если речь не идет об online построении, т.к. suffix array строится с линейным временем только целиком на фиксированной строке.
По памяти для массивов на каждый символ используется 4 байта, для деревьев — 16. По времени построения массивы не сильно быстрее деревьев.
Mab> Кроме того, сложность построения у них не зависит от мощности алфавита, в отличие от деревьев.
Сложность построения suffix tree на PATRICIA не зависит от алфавита ни по времени, ни по памяти. Ибо фактически используется бинарный алфавит.
