Использование Monad/ST для непараллельной передачи сообщений в изменяемый граф

Я пытаюсь разработать структуру данных для следующей ситуации.

Структура графика

Я планирую иметь граф узлов с невзвешенными направленными ребрами: Graph = [Node]

Каждый узел имеет:

  1. Некоторое внутреннее (постоянное) состояние TBD
  2. Очередь входящих сообщений
  3. Тип сообщения, которое он может отправить, определяется функцией, которая принимает текущее состояние узла (с возможностью отказа).
  4. Список ребер

Node { nodeState :: NodeState, inbox :: Queue NodeMessage, nodeMessage :: (NodeState -> Maybe NodeMessage), connections::[NodeEdge] }

Каждое ребро — это промежуточный этап захвата ожидающих сообщений для целевого узла.

NodeEdge { pendingMessage:: Maybe NodeMessage, targetNode :: Node }

Передача сообщений

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

  • Фаза 1: проверьте папку «Входящие» каждого узла, обработайте все сообщения и обновите NodeState, если это необходимо.
  • Фаза 2: Запустите на каждом узле nodeMessage, если это приведет к Just NodeMessage, отправьте NodeMessage на каждое соединение ([NodeEdge])
  • Фаза 3: проверьте каждый край узла, если у него есть сообщение, добавьте его в очередь сообщений целевого узла.

Монат/ST

Мой первоначальный план состоял в том, чтобы присвоить каждому узлу идентификатор (возможно, простой Int) и сохранить каждый узел в узле Map Int. Я раньше не пробовал ST Monad, но подумал, что могу использовать что-то вроде ST s (M.Map Int Node). Для любой заданной фазы активность отправки сообщения каждым узлом может быть обработана за O (k log N).

С другой стороны, если бы узлы/ребра могли обновлять изменяемое состояние своих ребер/узлов, то любая отдельная очередь могла бы быть обработана за O(k).

Хотя метод ST/Map кажется довольно интуитивным, возможность изменения всего графа мне не по плечу.

Любые предложения/советы/рекомендуемое чтение?


state haskell st-monad
person TheCriticalImperitive    schedule 11.09.2014    source источник
comment
Похоже, вы хотите, чтобы ваш график был чистым для некоторых функций, но изменяемым для других. Вы можете добиться этого, просто имея 2 типа графиков или (больше печатать, но красивее) написав data NodeEdge f = NodeEdge (Maybe NodeMessage) (f (Node f)) и разрешив f==Identity для неизменяемых графов и f==STRef s для изменяемых графов. Но если вас беспокоит производительность, вам следует просто использовать более эффективное представление (что-то вроде списка/матрицы смежности с IntSet в качестве списка).   -  person user2407038    schedule 11.09.2014
comment
Совсем не знаком со списками смежности. Было бы интересно посмотреть, как они работают. Какой-то конкретный пакет, на который я должен обратить внимание? Сохранение 2 графиков кажется немного грязным, но тогда мой вариант внешнего вида не стал чище. Для производительности я решил использовать массив.   -  person TheCriticalImperitive    schedule 12.09.2014

Ответы (1)


arrow_upward
1
arrow_downward

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

Поскольку количество узлов в моем графе никогда не изменится, я понял, что могу использовать массив. На самом деле я пересматриваю использование изменяемого типа данных - хотя я получаю гораздо более простой рабочий процесс, обновляющий массив, я получаю меньше преимуществ от лени, и в конечном итоге я пишу тонну кода в императивном стиле. На самом деле я думаю об использовании массива и государственной монады, а не ST.

Вот небольшой тестовый код, который я написал, используя STArray. «Правильный» ответ на этот вопрос был бы похожим типом данных специально для графиков — возможно, есть библиотека STGraph?

Во всяком случае, вот пример кода с использованием STArray:

import Control.Monad.ST
import Data.Array.ST
import Data.Array

import qualified Data.Dequeue as DQ

type Id = Int

data Node = Node {
    nodeId :: Id,
    nodeState :: NodeState,
    nodeInbox :: DQ.BankersDequeue NodeMessage,
    nodeMessage :: (NodeState -> Maybe NodeMessage),
    connections :: [NodeEdge] }

instance Show Node where
    show x = "Node: " ++ (show . nodeId $ x) ++ " :: Inbox: " ++ (show . nodeInbox $ x) ++ " :: " ++ (show . connections $ x)

data NodeEdge = NodeEdge { pendingMessage:: Maybe NodeMessage, targetNode :: Id } deriving Show

data NodeState = NodeState { stateLevel :: Int } deriving Show

data NodeMessage = NodeMessage { value :: Int } deriving Show

es = [[NodeEdge Nothing 1,NodeEdge Nothing 2],[NodeEdge Nothing 0,NodeEdge Nothing 2],[NodeEdge Nothing 0,NodeEdge Nothing 1]]
ns = take 3 $ map (\x -> Node x (NodeState 0) (DQ.fromList []) (\_ -> Nothing) (es !! x)) $ [0,1..]

testArray :: Array Int Node
testArray = listArray (0,2) ns

testSTarr = do  arr <- newListArray (0,2) ns :: ST s (STArray s Int Node)
                a <- readArray arr 1
                let i = targetNode . head $ connections a
                b <- readArray arr i
                let m = NodeMessage 2
                    ms = DQ.pushBack (nodeInbox b) m
                    b' = b { nodeInbox = ms }
                writeArray arr (nodeId b) b'
                return arr

testSTarr' x = do a <- readArray x 0
                  return a

bp = testSTarr >>= testSTarr'

main = do
            print $ runST bp 
            return ()
person TheCriticalImperitive    schedule 12.09.2014