Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 16
В priority_queue приоритет объекта поменять невозможно, но зато можно добавить его снова с новым приоритетом (старый элемент останется дубликатом). После чего нужно будет только при извлечении элемента из очереди проверять, не является ли он дубликатом (сравнить cur.first и dist[cur.second]).
Сложность будет O(E log E), что в предположении что нет кратных ребер равно O(E log V). На практике, когда пытался сравнивать, получалось что с priority_queue чуть быстрее.
P.S. — про фибоначчиеву кучу рассказали бы :)
Сложность будет O(E log E), что в предположении что нет кратных ребер равно O(E log V). На практике, когда пытался сравнивать, получалось что с priority_queue чуть быстрее.
P.S. — про фибоначчиеву кучу рассказали бы :)
Конечно, будет быстрее, у кучи коэффициент поменьше, чем у красно-черного дерева будет :)
За линию можно убрать кратные ребра, и будет опять ElogV.
А до кучи Фибоначчи, надеюсь, дело дойдет
За линию можно убрать кратные ребра, и будет опять ElogV.
А до кучи Фибоначчи, надеюсь, дело дойдет
Поменять приоритет элемента (при ручной реализации бинарной кучи) возможно — надо только хранить обратные ссылки из вершин графа в их текущее положение в массиве (и поддерживать при каждом перемещении элемента). После этого поднять элемент с уменьшившимся весом на нужное место — дело техники (log(N)). А очередь с повторениями требует слишком уж много памяти — дополнительные O(E).
Вопрос в том, какой из способов — очередь с повторениями, очередь без повторений, бинарное дерево или фибоначчиева куча (для графов, умещающихся в память) окажется, в конечном итоге, быстрее.
Фибоначчиева куча — было бы интересно.
Вопрос в том, какой из способов — очередь с повторениями, очередь без повторений, бинарное дерево или фибоначчиева куча (для графов, умещающихся в память) окажется, в конечном итоге, быстрее.
Фибоначчиева куча — было бы интересно.
Да, именно так и надо. На практике быстрее всего работает куча фибоначчи — лет семь назад ставил эксперименты. Причем отсутствие логарифма при изменении расстояния заметно уже на небольших задачах (считавшихся менее, чем за 0.5 секунды на Pentium III 500MHz).
Если прямо интересно — могу за пару дней провести заново такие эксперименты и написать.
Если не очень интересно — могу просто скинуть реализацию кучи фибоначчи
Если прямо интересно — могу за пару дней провести заново такие эксперименты и написать.
Если не очень интересно — могу просто скинуть реализацию кучи фибоначчи
Ну кто же будет писать свою реализацию кучи, когда есть priority_queue :)
На самом деле, это уже вторая ситуация, с которой я сталкиваюсь, когда добавление нужного функционала к контейнеру stl занимает буквально пару строк, но этого функционала там нет
Например, те, у кого нет stl. Кто пишет на С или на C#. Возможно, они не будут писать свою реализацию, а возьмут чужую — но тогда сами же и добавят обратные ссылки.
Вот мне совсем недавно пришлось написать, вместо использования stl. По двум причинам:
а) Необходимо было обновлять вес элемента за логарифмическое время. В принципе, это можно реализовать поверх кучи stl, но для этого надо предполагать, что куча stl устроена как массив, представляющий дерево--а это не очень хорошо, ведь в каких-то реализациях она может быть устроена по-другому, или нумерация может быть не с начала массива, а с конца, кто знает. Мы разрушаем абстракцию, одним словом.
б) (самое важное) Мне необходимо было всегда знать permutation элементов кучи, то есть где находится элемент, бывший вначале на позиции i (в то время как обычно вы знаете только, какой элемент сейчас находится на позиции i). Кажется, я пришел к выводу, что без написания своей реализации сделать этого нельзя.
а) Необходимо было обновлять вес элемента за логарифмическое время. В принципе, это можно реализовать поверх кучи stl, но для этого надо предполагать, что куча stl устроена как массив, представляющий дерево--а это не очень хорошо, ведь в каких-то реализациях она может быть устроена по-другому, или нумерация может быть не с начала массива, а с конца, кто знает. Мы разрушаем абстракцию, одним словом.
б) (самое важное) Мне необходимо было всегда знать permutation элементов кучи, то есть где находится элемент, бывший вначале на позиции i (в то время как обычно вы знаете только, какой элемент сейчас находится на позиции i). Кажется, я пришел к выводу, что без написания своей реализации сделать этого нельзя.
Ну да, это я погорячился. Ну точнее спроецировал это на программистские контесты.
В них времени мало, и гораздо проще использовать вместо кучи сет (как автор в посте и сделал), при этом получив возможность обновления веса (удаление + добавление) и немножко увеличив константу времени выполнения. Ну или хранить дубликаты, как я предложил.
Хотя в принципе это не только к контестам применимо. В продакшене — если только это не критическое по производительности место — я бы использовал один из вышеописанных вариантов, просто потому что меньше сложность кода будет чем при написании своей кучи. Где вы работаете что вам приходится писать свою кучу? Я тоже так хочу.
А про знание permutation — можно подробнее, зачем бы это знать? Мне это казалось деталью реализации, которую в в голову не может прийти хотеть знать. Ну если смотреть на интерфейс priority_queue — это push && top && pop. То что внутри это куча, хранящаяся в массиве — это так сложилось. Внутри могло бы быть какое-то дерево, для которого «позиция i» вообще не определена.
В них времени мало, и гораздо проще использовать вместо кучи сет (как автор в посте и сделал), при этом получив возможность обновления веса (удаление + добавление) и немножко увеличив константу времени выполнения. Ну или хранить дубликаты, как я предложил.
Хотя в принципе это не только к контестам применимо. В продакшене — если только это не критическое по производительности место — я бы использовал один из вышеописанных вариантов, просто потому что меньше сложность кода будет чем при написании своей кучи. Где вы работаете что вам приходится писать свою кучу? Я тоже так хочу.
А про знание permutation — можно подробнее, зачем бы это знать? Мне это казалось деталью реализации, которую в в голову не может прийти хотеть знать. Ну если смотреть на интерфейс priority_queue — это push && top && pop. То что внутри это куча, хранящаяся в массиве — это так сложилось. Внутри могло бы быть какое-то дерево, для которого «позиция i» вообще не определена.
Я пишу диссертацию в германии. В нашей группе в основном занимаются моделированием гидродинамики в пористых средах (и потом смотрят, как геометрия среды влияет на гидродинамические характеристики). Про гидродинамику я писал вот тут, про среды еще не писал. В качестве пористой среды мы используем упаковки твердых шариков. Лично я теперь занимаюсь свойствами таких упаковок шариков, потому что это хорошая и одновременно простая модель для жидкости, стекла, твердого тела, помимо того, что некоторые пористые среды выглядят именно так. Есть много алгоритмов создания упаковок шариков (это совсем не просто, как выяснилось), один из них проиллюстрирован в этом ролике--это моделирование молекулярной динамики упругих столкновений, притом что шарики одновременно растут. В нем-то мне и понадобился permutation.
Дело вот в чем: алгоритм лучше реализовывать как event-driven molecular dynamics, то есть не двигать шарики непрерывно, а обновлять скорости шариков после каждого столкновения. В куче как раз и хранятся все столкновения, которые нужно хранить, чтоб не пропустить столкновения. В самом простом случае можно хранить столкновения каждого шарика с каждым, но тогда вам не хватит ни памяти, ни времени вычисления. Столкновения можно выбрать специальным образом, и хранить всего N столкновений (где N--число шариков), в этом и есть основная фишка алгоритма. На каждый шарик должно приходится ближайшее для него столкновение, исключая те, что уже есть в куче (тогда мы не пропустим ни одно столкновение), то есть столкновения можно идентифицировать номером шарика.
На каждой итерации алгоритма я выбираю ближайшее столкновение (top из priority_queue). Потом пересчитываю ближайшее столкновение для данного шарика (делаю update top--можно сделать и pop-push), потом мне надо пересчитать ближайшее столкновение для второго шарика, и обновить его--и вот тут я нахожу позицию столкновения для второго шарика в очереди через permutation[topEvent.neighborID] (как я сказал, столкновения можно идентифицировать по номеру шарика), оно может быть в самом конце очереди, ведь это столкновение, ближайшее для второго шарика _без учета текущего_.
Кроме того, эти два шарика могли быть парными в столкновениях, ближайших для других шариков, а теперь перестать ими быть, или могут стать парными шариками в новых ближайших столкновениях для других шариков. Я определяю эти изменения, пока ищу ближайшие столкновения для моей столкнувшейся пары. И тогда я должен обновить события для этих измененных соседей. И индексы (в куче) событий для соседей я снова нахожу по permutation[neighborID].
Этот алгоритм (как и все алгоритмы для генерации упаковок шариков) плохо параллелится (вообще не параллелится), и может работать очень долго (если плохо реализовать--200 дней, если хорошо--2 дня, если очень хорошо--не знаю сколько, у меня работает 2 дня на конфигурации, бывшей hi-end 2 года назад). Поэтому set, пожалуй, не вариант.
Я открыл свой исходный код (правда, там не все хорошо с точки зрения C++, например, я строки передаю только by value, по аналогии с .NET, хотя часто можно как const reference, и есть некритичные баги). Вот классы для работы с модифицированной кучей: один, два, три.
Дело вот в чем: алгоритм лучше реализовывать как event-driven molecular dynamics, то есть не двигать шарики непрерывно, а обновлять скорости шариков после каждого столкновения. В куче как раз и хранятся все столкновения, которые нужно хранить, чтоб не пропустить столкновения. В самом простом случае можно хранить столкновения каждого шарика с каждым, но тогда вам не хватит ни памяти, ни времени вычисления. Столкновения можно выбрать специальным образом, и хранить всего N столкновений (где N--число шариков), в этом и есть основная фишка алгоритма. На каждый шарик должно приходится ближайшее для него столкновение, исключая те, что уже есть в куче (тогда мы не пропустим ни одно столкновение), то есть столкновения можно идентифицировать номером шарика.
На каждой итерации алгоритма я выбираю ближайшее столкновение (top из priority_queue). Потом пересчитываю ближайшее столкновение для данного шарика (делаю update top--можно сделать и pop-push), потом мне надо пересчитать ближайшее столкновение для второго шарика, и обновить его--и вот тут я нахожу позицию столкновения для второго шарика в очереди через permutation[topEvent.neighborID] (как я сказал, столкновения можно идентифицировать по номеру шарика), оно может быть в самом конце очереди, ведь это столкновение, ближайшее для второго шарика _без учета текущего_.
Кроме того, эти два шарика могли быть парными в столкновениях, ближайших для других шариков, а теперь перестать ими быть, или могут стать парными шариками в новых ближайших столкновениях для других шариков. Я определяю эти изменения, пока ищу ближайшие столкновения для моей столкнувшейся пары. И тогда я должен обновить события для этих измененных соседей. И индексы (в куче) событий для соседей я снова нахожу по permutation[neighborID].
Этот алгоритм (как и все алгоритмы для генерации упаковок шариков) плохо параллелится (вообще не параллелится), и может работать очень долго (если плохо реализовать--200 дней, если хорошо--2 дня, если очень хорошо--не знаю сколько, у меня работает 2 дня на конфигурации, бывшей hi-end 2 года назад). Поэтому set, пожалуй, не вариант.
Я открыл свой исходный код (правда, там не все хорошо с точки зрения C++, например, я строки передаю только by value, по аналогии с .NET, хотя часто можно как const reference, и есть некритичные баги). Вот классы для работы с модифицированной кучей: один, два, три.
Вот самая понятная и короткая реализация алгоритма Дейкстры, из всех что я видел:
На языке логического программирования Dyna.
path(start) min= 0.
path(B) min= path(A) + edge(A,B).
goal min= path(end).
На языке логического программирования Dyna.
Комменнтарии по синтаксису:
1. путь до узла start принимается равным нулю
2. путь до каждого узла (B) это минимум суммы длины входящего ребра и значения пути для второго узла этого ребра
3. цель это минимум длины всех путей до узла end
Язык полностью декларативный и чистый. Следовательно используется лишь как часть большей программы (в виде библиотеки). В самом языке нет операци ввода-вывода или возможности напрямую повлиять на ход вычислений.
A, B — свободные переменные (начинаются с большой буквы)start, end — фиксированные константы (начинаются с маленькой буквы)path, edge — праметризованные константы (нечто вроде конструктора в ООП и pattern-matching в ФП)min= — операция аггрегирования альтенатив. Должна быть одинакова для всех использований данного типа1. путь до узла start принимается равным нулю
2. путь до каждого узла (B) это минимум суммы длины входящего ребра и значения пути для второго узла этого ребра
3. цель это минимум длины всех путей до узла end
Язык полностью декларативный и чистый. Следовательно используется лишь как часть большей программы (в виде библиотеки). В самом языке нет операци ввода-вывода или возможности напрямую повлиять на ход вычислений.
А что за цифры над рёбрами на картинке, это не вес перехода?
Может быть, я, конечно, чего-то не понимаю, но путь 1-3-6-5 будет 9+2+9=21, в то время как 1-2-3-6-5, которым прошёл алгоритм — 7+10+2+9=28.
А нам требуется найти кратчайший путь.
Может быть, я, конечно, чего-то не понимаю, но путь 1-3-6-5 будет 9+2+9=21, в то время как 1-2-3-6-5, которым прошёл алгоритм — 7+10+2+9=28.
А нам требуется найти кратчайший путь.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Графы для самых маленьких: Dijkstra или как я не ходил на собеседование в Twitter