Сталася такая беда, что надо сделать реализацию биномиальной кучи. Вроде много чего есть по этому поводу(наверное лучше всего на википедии буржуйской, там даже реализация на яве есть), но проблемка в том что везде чего-то не хватает, тоесть наскоком разобратся не получается.
Собственно просьба: если у кого нить есть реализация биномиальных куч (вставка, удаление минимального узла, слияние,...) на С++, 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 не зависит от алфавита ни по времени, ни по памяти. Ибо фактически используется бинарный алфавит.
Здравствуйте, Mab, Вы писали:
Mab>Вот довольно популярный анализ практической эффективности:
Большое спасибо, с интересом сейчас изучаю. Очень ценно. Уже подивился, с какой лихостью они приводят скорости работы алгоритмов, ведь ясно, что на деле эти цифры могут отличаться наверное минимум на порядок в зависимости от среднего lcp и размера алфавита, не говоря уже про нестабильность некоторых алгоритмов (bzip, к примеру, виснет на длинных прогонах ababab...). Но все-таки это позволило мне осознать, что на практике разница между характеристиками алгоритмов в log n и аналогичные функции ничего не означает — константы при O элементарно их перевешивают. Был несколько удивлен этим обстоятельством. Буду привыкать.
Mab>Недавно рецензировал статью на FOCS08, там народ предлагает еще один алгоритм с линейным временем работы, который на практике еще быстрее существующих. Естественно, выигрыш не асимптотический, а измеряется в десятках процентов.
Я тоже, признаться, тоже этим грешу. Вот как-то придумал, как можно уменьшить объем работы в алгоритме Sadakane-Larsson так, чтобы применять технику удвоения только к части суффиксов (примерно 1/7), а остальное за гарантированное O(n log n) время отсортировать более быстрым способом с Induced Copying. Надо бы как-то попробовать это реализовать и посмотреть, что получится, но не знаю, когда у меня дойдут до этого руки.
And if you listen very hard the alg will come to you at last.
Здравствуйте, R.K., Вы писали:
RK>По памяти для массивов на каждый символ используется 4 байта, для деревьев — 16.
Для деревьев все сильно зависит от того, как именно хранить дуги. А это, в свою очередь, дает memory-time tradeoff.
RK>По времени построения массивы не сильно быстрее деревьев.
Ну разница легко может быть в разы. Кому сильно, кому не сильно.
RK>Сложность построения suffix tree на PATRICIA не зависит от алфавита ни по времени, ни по памяти. Ибо фактически используется бинарный алфавит.
Тогда просто длина строки возрастает в log A раз, казалось бы.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, R.K., Вы писали:
RK>>По памяти для массивов на каждый символ используется 4 байта, для деревьев — 16. Mab>Для деревьев все сильно зависит от того, как именно хранить дуги. А это, в свою очередь, дает memory-time tradeoff.
Дуги можно хранить по-разному, это да. Но в реализации PATL
я предпочел постоянный 16-ти байтный (по 4 байта: длина префикса, парент и два дочерних) размер узла, так намного удобнее, чем городить структуры переменной длины.
Вообще для полноценной замены дерева необходимо совместно с массивами для разных применений вычислять дополнительные структуры, которые также тянут время и память. Конкретный пример: enhanced suffix array в Seqan. А дерево — более универсальная структура и сразу предоставляет большинство своих возможностей. Вот и получается такой довольно нетривиальный трейдофф: все в одном, красиво и достаточно быстро vs экономно, ограниченно и всегда по-разному.
RK>>По времени построения массивы не сильно быстрее деревьев. Mab>Ну разница легко может быть в разы. Кому сильно, кому не сильно.
Таки надо сделать забег Seqan против PATL
RK>>Сложность построения suffix tree на PATRICIA не зависит от алфавита ни по времени, ни по памяти. Ибо фактически используется бинарный алфавит. Mab>Тогда просто длина строки возрастает в log A раз, казалось бы.
Как это? Нет, длина строки, как и размер дерева, линейны от индексируемого объема.
Здравствуйте, R.K., Вы писали:
Mab>>Тогда просто длина строки возрастает в log A раз, казалось бы. RK>Как это? Нет, длина строки, как и размер дерева, линейны от индексируемого объема.
Это я как-то не понимаю. Мы рассматриваем вставляемые строки как последовательности бит? Или что-то иное?
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, R.K., Вы писали:
Mab>>>Тогда просто длина строки возрастает в log A раз, казалось бы. RK>>Как это? Нет, длина строки, как и размер дерева, линейны от индексируемого объема.
Mab>Это я как-то не понимаю. Мы рассматриваем вставляемые строки как последовательности бит? Или что-то иное?
Да, именно "рассматриваем вставляемые строки как последовательности бит", но с каких это пор представление увеличивает длину?
Здравствуйте, R.K., Вы писали:
RK>Да, именно "рассматриваем вставляемые строки как последовательности бит", но с каких это пор представление увеличивает длину?
Ну очевидно как. Размер дерева становится линеен по битовой длине строки, а она как раз в log A раз больше, чем символьная.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, R.K., Вы писали:
RK>>Да, именно "рассматриваем вставляемые строки как последовательности бит", но с каких это пор представление увеличивает длину?
Mab>Ну очевидно как. Размер дерева становится линеен по битовой длине строки, а она как раз в log A раз больше, чем символьная.
Т.е., имеется в виду, что А = log(8 * sizeof(symbol_type))? Ну что ж, таков коэффициент линейной сложности. С точки зрения теории O(N) остается той же, а на практике возможные тормоза прояснятся как сами по себе, так и из сравнения с реализацией через массивы. Isn't it?
Здравствуйте, R.K., Вы писали:
RK>Т.е., имеется в виду, что А = log(8 * sizeof(symbol_type))?
Имелось в виду, что log A = число бит на символ, и этот множитель пролезает в оценку.
RK>Ну что ж, таков коэффициент линейной сложности. С точки зрения теории O(N) остается той же, а на практике возможные тормоза прояснятся как сами по себе, так и из сравнения с реализацией через массивы. Isn't it?
C теоретической точки зрения алгоритм оказыватеся alphabet-dependent. Я лишь это и хотел отметить, ничего более.
Конечно, на практике алфавит фиксирован, поэтому надо сравнивать с другими реализациями на осмысленных практических тестах.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, R.K., Вы писали:
RK>>Ну что ж, таков коэффициент линейной сложности. С точки зрения теории O(N) остается той же, а на практике возможные тормоза прояснятся как сами по себе, так и из сравнения с реализацией через массивы. Isn't it? Mab>C теоретической точки зрения алгоритм оказыватеся alphabet-dependent. Я лишь это и хотел отметить, ничего более.
Возможно, возможно... Но вот что я подразумеваю под независимостью от алфавита: с увеличением размера в битах каждого символа уменьшается кол-во символов в некотором ограниченном объеме памяти. Вот линейную зависимость от индексируемого объема памяти я и подразумевал. Право, не знаю, как это выразить через O(N).
Mab>Конечно, на практике алфавит фиксирован, поэтому надо сравнивать с другими реализациями на осмысленных практических тестах.
Здравствуйте, 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).
Mab>А решение без medlable heaps требует порядка n * log^2 n времени.
Кстати, а почему это мы добавляем элементы из одной кучи в другую по одному? Есть более эффективный способ слияния хипов примерно одного размера — свалить в одну кучу и выстроить, делается за O(n). Сливая по турнирной системе описанные выше кучи таким способом мы получаем итоговую сложность O(n log n), что вполне аналогично времени на вытаскивание этих элементов из результирующей кучи (тоже O(n log n)). Если же брать маленькие кучи и большие, до для них нельзя организовать турнирную систему, а в нетурнирной сложность поэлементной вставки опять O(n log n).
Итого вывод — использование биномиальных куч не улучшает общей асипмтотики времени работы алгоритма, который правильно реализован на бинарных кучах, если только этот алгоритм не оставляет невычерпанными существенное количество элементов в создаваемых им очередях. А есть такие алгоритмы?
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>Итого вывод — использование биномиальных куч не улучшает общей асипмтотики времени работы алгоритма, который правильно реализован на бинарных кучах, если только этот алгоритм не оставляет невычерпанными существенное количество элементов в создаваемых им очередях. А есть такие алгоритмы?
