Как работать с графами среднего размера в Haskell?

Mar 21, 2010 19:21

Кто знает, как пошустрее работать с графами ( Read more... )

Leave a comment

Comments 30

anonymous March 21 2010, 17:21:44 UTC
я не знаю, правильно или нет, но я примерно так делал в одной несерьезной программе:

type UniqID = Integer -- на самом деле у меня были строки
data Vertex a = V UniqID a [Vertex a]
type Graph a = [Vertex a]

как раз было порядка миллиона ребер.

здесь вершины образуют не дерево, а именно что граф, т. е. вершина 1 может содержать в списке вершину 2 у которой в списке вершина 3 у которой в списке опять вершина 1, и так далее.

вместо списков, понятное дело, могут быть массивы или что угодно, а хоть и FiniteMap, чтобы по идентификатору быстро искать вершину.

гадание по капче: allow thieves

Reply

nealar March 21 2010, 18:40:03 UTC
Массивы - это модуль Data.Graph. Более хитрая конструкция, с более приятными асимптотиками - это Data.Graph.Inductive (библиотека fgl). Но и её я легко загонял в своп тупыми действиями. Ей тупо не хватило оперативы рёбра хранить. То есть, в некоторых случаях некоторые алгоритмы лучше руками.

Reply

anonymous March 22 2010, 05:31:05 UTC
Да, точно, сейчас же есть стандартные библиотеки для графов. Тогда не было.

Reply

nivanych March 22 2010, 09:57:31 UTC
Хорошая штука, но ведь (уже update'ил)
исходная задача и состоит в том, чтобы
быстро делать поиск по идентификатору.

Reply


nealar March 22 2010, 15:44:21 UTC
Граф - это же просто пачка (помеченных) узлов + пачка (помеченных рёбер). Объекты у него на рёбрах, целые числа или () - к реализации графов не относится, а только к использованию.

Reply

nivanych March 22 2010, 15:50:10 UTC
Чем помечены, конечно, не важно.
А вот от того, как индексируются,
будет зависеть скорость работы с ними.

Reply

nealar March 22 2010, 16:03:16 UTC
Скорость каких операций?

Reply

nivanych March 22 2010, 18:10:21 UTC
Скорость нахождения объекта по ссылке.
Как я уже писал, в качестве ссылки можно
вполне эффективно пользовать индекс массива.
Только придётся делать что-то типа
работы с памятью для эффективного
использования индексов.
Но это гораздо лучше, проще и правильнее,
чем использовать ссылки и тогда писать свой GC.
Тем более, что в GHC он сделан отлично,
и лучше использовать его.

Reply


Leave a comment

Up