я не знаю, правильно или нет, но я примерно так делал в одной несерьезной программе:
type UniqID = Integer -- на самом деле у меня были строки data Vertex a = V UniqID a [Vertex a] type Graph a = [Vertex a]
как раз было порядка миллиона ребер.
здесь вершины образуют не дерево, а именно что граф, т. е. вершина 1 может содержать в списке вершину 2 у которой в списке вершина 3 у которой в списке опять вершина 1, и так далее.
вместо списков, понятное дело, могут быть массивы или что угодно, а хоть и FiniteMap, чтобы по идентификатору быстро искать вершину.
Массивы - это модуль Data.Graph. Более хитрая конструкция, с более приятными асимптотиками - это Data.Graph.Inductive (библиотека fgl). Но и её я легко загонял в своп тупыми действиями. Ей тупо не хватило оперативы рёбра хранить. То есть, в некоторых случаях некоторые алгоритмы лучше руками.
Граф - это же просто пачка (помеченных) узлов + пачка (помеченных рёбер). Объекты у него на рёбрах, целые числа или () - к реализации графов не относится, а только к использованию.
Скорость нахождения объекта по ссылке. Как я уже писал, в качестве ссылки можно вполне эффективно пользовать индекс массива. Только придётся делать что-то типа работы с памятью для эффективного использования индексов. Но это гораздо лучше, проще и правильнее, чем использовать ссылки и тогда писать свой GC. Тем более, что в GHC он сделан отлично, и лучше использовать его.
Comments 30
type UniqID = Integer -- на самом деле у меня были строки
data Vertex a = V UniqID a [Vertex a]
type Graph a = [Vertex a]
как раз было порядка миллиона ребер.
здесь вершины образуют не дерево, а именно что граф, т. е. вершина 1 может содержать в списке вершину 2 у которой в списке вершина 3 у которой в списке опять вершина 1, и так далее.
вместо списков, понятное дело, могут быть массивы или что угодно, а хоть и FiniteMap, чтобы по идентификатору быстро искать вершину.
гадание по капче: allow thieves
Reply
Reply
Reply
исходная задача и состоит в том, чтобы
быстро делать поиск по идентификатору.
Reply
Reply
А вот от того, как индексируются,
будет зависеть скорость работы с ними.
Reply
Reply
Как я уже писал, в качестве ссылки можно
вполне эффективно пользовать индекс массива.
Только придётся делать что-то типа
работы с памятью для эффективного
использования индексов.
Но это гораздо лучше, проще и правильнее,
чем использовать ссылки и тогда писать свой GC.
Тем более, что в GHC он сделан отлично,
и лучше использовать его.
Reply
Leave a comment