Генератор графа неориентированные графы


Я все еще очень новой для Haskell и я работаю над генератором граф неориентированный непомеченный графы, содержащие циклы и у меня узкое место в следующих функциях. До сих пор я не думал о производительности и просто смотрел на корректность.

Я знаю, что этот вопрос не очень популярен, но я был бы заинтересован в общие рекомендации по повышению производительности с учетом некоторых наивной, но правильной реализации, как показано ниже.

Например:

  1. Где применить строгость?
  2. Должен ли я использовать вектор/массив вместо списков? Когда, где и почему?
  3. Я должен улучшить отдельные функции, заменив рекурсию, используя складки/карты/и т. д. или похожие?

Дополнительные информация:

  1. Я использую -О2 с помощью GHC
  2. профилирование показывает (при нормировании времени выполнения соединений до 100%)
    • arqSeq 40% (с почти все время проводим в boundsequences)
    • connectionCombinations 60% С четверть времени проводят в случаях

Я не думаю, что вам нужно понять все детали. Я смотрю больше для микро-улучшений (следующие определяет дуги от данного узла до классов эквивалентности вершин, сгруппированных по степени их).

import Data.List
import Control.Monad

type Arcs = Int
type Count = Int
type Vertex = Int    
type MSequence = [Int]
data EquivClass = EC { order :: Int, verts :: [Vertex] } deriving (Eq, Show)
type ECPartition = [EquivClass]
type NodeSelection = [(Arcs,Count)]
type ECNodeSelection = (EquivClass, NodeSelection)

-- number of occurences of unique elements in a list
occurences :: (Ord a) => [a] -> [(a, Int)]
occurences = map (\xs@(x:_) -> (x, length xs)) . group . reverse . sort

-- number of vertices in an equivalence class
ecLength :: EquivClass -> Int
ecLength = length . verts

-- for a given y = (y_1,...,y_n) and a bound m, find all vectors
-- x = (x_1,...,x_n) such that |x| = m and x_i <= y_i
boundSequences :: (Num a, Ord a, Enum a) => a -> [a] -> [[a]]
boundSequences m x | m <= sum x = (fByM . sequence . ranges) x
                   | otherwise = [[]]
    where fByM = filter (\x -> sum x == m)
          ranges = map (\x -> [0..x])

-- return m-sequences (combinations of number of arcs) for the given
-- order to an ECPartition
arcSeq :: Int -> ECPartition -> [MSequence]
arcSeq m x = boundSequences m (map ecProd x)
    where ecProd e = ecLength e * order e

-- return all the possible arc combinations  to an equivalence
-- class for a given number of arcs
connectionCombinations :: Int -> EquivClass -> [NodeSelection]
connectionCombinations arcs = map groupOcc . prune arcs . sequence . orderRep
    where orderRep (EC o v) = replicate (length v) [0..o]
          prune a = nub . map (reverse . sort) . filter ((== a) . sum)
          groupOcc = filter ((/= 0) . fst) . occurences

-- return all the possible lists of equivalence class node selections
-- from a Partition and a givne number of arcs
connections :: ECPartition -> Int -> [[ECNodeSelection]]
connections p order = concatMap (con p) $ arcSeq order p
     where con p arcs = map (zip p) $ zipWithM connectionCombinations arcs p

main = do
    -- small example. In the complete app this is called 10,000's of
    -- times in case of high degrees or vertex counts
    let cons = connections [EC 4 [1], EC 1 [2,3,4]] 5
    mapM_ (print) cons


542
10
задан 1 декабря 2011 в 06:12 Источник Поделиться
Комментарии
1 ответ

-- for a given y = (y_1,...,y_n) and a bound m, find all vectors
-- x = (x_1,...,x_n) such that |x| = m and x_i <= y_i
boundSequences :: (Num a, Ord a, Enum a) => a -> [a] -> [[a]]
boundSequences m x | m <= sum x = (fByM . sequence . ranges) x
| otherwise = [[]]
where fByM = filter (\x -> sum x == m)
ranges = map (\x -> [0..x])

Исключая некоторые случаи повезло, вы тратите много работы здесь. последовательности . диапазоны производит (y_1+1) * ... * (y_n+1) списки, которые вы должны проверить. Если вы пишете функцию, чтобы выпускать только успешные списки, вы можете получить много производительности для больших входных данных (это не слишком много для шорт-листы с мелкими элементами, но это поможет для тех, кто слишком).
Не в случае сумма х < м возвращение [] , а не [[]]?

-- return all the possible arc combinations  to an equivalence
-- class for a given number of arcs
connectionCombinations :: Int -> EquivClass -> [NodeSelection]
connectionCombinations arcs = map groupOcc . prune arcs . sequence . orderRep
where orderRep (EC o v) = replicate (length v) [0..o]
prune a = nub . map (reverse . sort) . filter ((== a) . sum)
groupOcc = filter ((/= 0) . fst) . occurences

Вместо обратного . сортировать, использовать sortBy (флип сравнить). Это не сделает большой разницы для коротких списков, но это чище, ИМО. чернослив дуги . последовательность содержится еще один экземпляр boundSequences проблему, создав множество списков и отфильтровывать большинство из них сразу. нуб - это не хорошо, это квадратичная (в худшем случае, O(в общей сложности*различные) в целом). Что вы nubbing имеют ОГА примеру, если порядок не имеет значения, карта в голове . группы . вроде это гораздо быстрее, чем нуб нуб (еще лучше данные.Набор.список . Данных.Набор.изсписок), если порядок имеет значение, сохранить набор увиденных элементов, и для каждого нового, вывода и добавить его к набору видно.

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

Итак, приведенные данные не работать достаточно долго, чтобы произвести содержательный профиль, поэтому я изменил его на

let cons = connections [EC 4 [1 .. 6], EC 6 [2 .. 9]] 5

Который работает достаточно долго, чтобы собрать горсть образцов. К сожалению, профиль не очень информативное:

    total time  =        7.90 secs   (395 ticks @ 20 ms)
total alloc = 8,098,386,128 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
connectionCombinations Main 100.0 100.0

Поэтому я вставил пару {-# ЮБК #-} прагмы. Этот сайт biggo в том, что программа-это последовательность . orderRep, что неудивительно. Рерайт по указанной выше линии,

boundSequences :: (Num a, Ord a, Enum a) => a -> [a] -> [[a]]
boundSequences m xs
| sm < m = []
| sm == m = [xs]
| otherwise = go sm m xs
where
sm = sum xs
go _ r []
| r == 0 = [[]]
| otherwise = []
go _ r [y]
| y < r = []
| otherwise = [[r]]
go s r (y:ys) = do
let mny | s < r+y = r+y-s
| otherwise = 0
mxy = min y r
c <- [mny .. mxy]
map (c:) (go (s-y) (r-c) ys)

и используя, что в connectionCombinations вместо чернослива дуги . последовательность (требуется небольшое изменение в orderRep),

connectionCombinations :: Int -> EquivClass -> [NodeSelection]
connectionCombinations arcs = map groupOcc . nub . map (sortBy (flip compare)) .
boundSequences arcs . orderRep
where orderRep (EC o v) = replicate (length v) o
groupOcc = filter ((/= 0) . fst) . occurences

принес время работы (с GHC -О2, без профилирования) значительно снизились:

dafis@schwartz:~/Cairo> time ./orArcs > /dev/null

real 0m5.836s
user 0m5.593s
sys 0m0.231s
dafis@schwartz:~/Cairo> time ./arcs > /dev/null

real 0m0.008s
user 0m0.005s
sys 0m0.003s

Ли какие-либо дальнейшей оптимизации (например, вышеупомянутый нуб) необходимы, и где большую часть времени в реальной программе тратится, так что можно выделить наиболее важные моменты, я не могу сказать без более реалистичные данные.

11
ответ дан 1 декабря 2011 в 06:12 Источник Поделиться