并行计算 NFA 转换

Question

我有这段代码是用 F# 写的：

type NondeterministicFiniteAutomaton = {
    initialState: string
    finalStates: string List
    transitions: Map<string * char, string List>
}

let private nextState (symbol:char) (state:string) (transitions:Map<string * char, string List>) =
    transitions |> Map.tryFind (state, symbol)

let rec private haltState (input:string) (index:int) (state:string) (transitions:Map<string * char, string List>) =
    match index with
    | x when x = input.Length -> state
    | _ ->
        match nextState input.[index] state transitions with
        | x when x.IsNone -> null
        | x -> haltState input (index+1) x.Value transitions

在最后一行，x.Value 将 return 我的自动机可以进入的状态列表，比如说 ["s1"; "s2"; "s3"]。对于此列表中的每个状态，我想并行调用 haltState，从而并行计算每个可能的路径。

如何并行调用它们？
完成后我如何"join"他们？

Answer 1

我建议首先编写完整的顺序版本。然后您可以查看添加并行性是否对您将要进行的计算有意义。

至于加入结果，即使在顺序版本中，这也是您需要做的事情。您的 haltState 函数 return 是一个字符串，但如果这是一个 NFA，那么它可能以多个不同的状态结束。因此，您可以将其更改为 return 一系列可能的结果：

let rec private haltState (input:string) (index:int) (state:string) (transitions:Map<string * char, string List>) =
    match index with
    | x when x = input.Length -> Seq.singleton x
    | _ ->
        match nextState input.[index] state transitions with
        | None -> Seq.empty
        | Some states -> 
            states |> Seq.collect (fun state -> 
              haltState input (index+1) state transitions)

这 return 是一个序列，它连接了使用 Seq.collect 为多个可能状态生成的序列。请注意，我还在选项值上使用了更多惯用模式匹配。

您可以使用 Array.Parallel.map 将其并行化，但我怀疑这会使处理速度更快 - 开销可能会更大。

let rec private haltState (input:string) (index:int) (state:string) (transitions:Map<string * char, string List>) =
    match index with
    | x when x = input.Length -> [| state |]
    | _ ->
        match nextState input.[index] state transitions with
        | None -> [| |]
        | Some states -> 
            states
            |> Array.ofSeq
            |> Array.Parallel.collect (fun state -> haltState input (index+1) state transitions)

并行计算 NFA 转换

Compute NFA transitions in parallel

parallel-processing

f#

finite-automata