4

これは私の最初のF＃プログラムです。最初の演習として、コンウェイのライフゲームを実装しようと思いました。

次のコードがなぜそのようなひどいパフォーマンスをするのか理解するのを手伝ってください。

let GetNeighbours (p : int, w : int, h : int) : seq<int> =
    let (f1, f2, f3, f4) = (p > w, p % w <> 1, p % w <> 0, p < w * (h - 1))
    [
    (p - w - 1, f1 && f2);
    (p - w, f1);
    (p - w + 1, f1 && f3);
    (p - 1, f2);
    (p + 1, f3);
    (p + w - 1, f4 && f2);
    (p + w, f4);
    (p + w + 1, f4 && f3)
    ]
    |> List.filter (fun (s, t) -> t)
    |> List.map (fun (s, t) -> s)
    |> Seq.cast

let rec Evolve (B : seq<int>, S : seq<int>, CC : seq<int>, g : int) : unit =
    let w = 10
    let h = 10
    let OutputStr = (sprintf "Generation %d:  %A" g CC) // LINE_MARKER_1
    printfn "%s" OutputStr
    let CCN = CC |> Seq.map (fun s -> (s, GetNeighbours (s, w, h)))
    let Survivors =
        CCN
        |> Seq.map (fun (s, t) -> (s, t |> Seq.map (fun u -> (CC |> Seq.exists (fun v -> u = v)))))
        |> Seq.map (fun (s, t) -> (s, t |> Seq.filter (fun u -> u)))
        |> Seq.map (fun (s, t) -> (s, Seq.length t))
        |> Seq.filter (fun (s, t) -> (S |> Seq.exists (fun u -> t = u)))
        |> Seq.map (fun (s, t) -> s)
    let NewBorns =
        CCN
        |> Seq.map (fun (s, t) -> t)
        |> Seq.concat
        |> Seq.filter (fun s -> not (CC |> Seq.exists (fun t -> t = s)))
        |> Seq.groupBy (fun s -> s)
        |> Seq.map (fun (s, t) -> (s, Seq.length t))
        |> Seq.filter (fun (s, t) -> B |> Seq.exists (fun u -> u = t))
        |> Seq.map (fun (s, t) -> s)
    let NC = Seq.append Survivors NewBorns
    let SWt = new System.Threading.SpinWait ()
    SWt.SpinOnce ()
    if System.Console.KeyAvailable then
        match (System.Console.ReadKey ()).Key with
        | System.ConsoleKey.Q -> ()
        | _ -> Evolve (B, S, NC, (g + 1))
    else 
        Evolve (B, S, NC, (g + 1))

let B = [3]
let S = [2; 3]
let IC = [4; 13; 14]
let g = 0
Evolve (B, S, IC, g)

最初の5回の反復、つまり世代0、1、2、3、4は、問題なく発生します。次に、約100ミリ秒の短い休止の後、第5世代が完了します。ただし、その後、ブレークポイントVisual Studioで示されるように、プログラムは「LINE_MARKER_1」とマークされた行でハングします。printfnそれは決してラインに到達しません。

奇妙なことに、すでに第2世代までCCに、関数内のシーケンスEvolveはすでにシーケンスに安定している[4; 13; 14; 3]ため、第6世代が進化しない理由はわかりません。

コードの大きなセグメントを貼り付けてデバッグの助けを求めることは一般的に不適切であると考えられていることを理解していますが、これを最小限の実用的な例に減らす方法がわかりません。デバッグに役立つポインタはありがたいことに感謝します。

よろしくお願いします。

編集

私を助けたいと思っている人は、その機能をほとんど無視するかもしれないと本当に信じていGetNeighboursます。完全を期すためだけに含めました。

4

4 に答える 4

6

パフォーマンスを修正する最も簡単な方法は、次を使用することSeq.cacheです。

let GetNeighbours (p : int, w : int, h : int) : seq<int> =
    let (f1, f2, f3, f4) = (p > w, p % w <> 1, p % w <> 0, p < w * (h - 1))
    [
    (p - w - 1, f1 && f2);
    (p - w, f1);
    (p - w + 1, f1 && f3);
    (p - 1, f2);
    (p + 1, f3);
    (p + w - 1, f4 && f2);
    (p + w, f4);
    (p + w + 1, f4 && f3)
    ]
    |> List.filter (fun (s, t) -> t)
    |> List.map (fun (s, t) -> s)
    :> seq<_> // <<<<<<<<<<<<<<<<<<<<<<<< MINOR EDIT, avoid boxing

let rec Evolve (B : seq<int>, S : seq<int>, CC : seq<int>, g : int) : unit =
    let w = 10
    let h = 10
    let OutputStr = (sprintf "Generation %d:  %A" g CC) // LINE_MARKER_1
    printfn "%s" OutputStr
    let CCN =
        CC
        |> Seq.map (fun s -> (s, GetNeighbours (s, w, h)))
        |> Seq.cache // <<<<<<<<<<<<<<<<<< EDIT
    let Survivors =
        CCN
        |> Seq.map (fun (s, t) -> (s, t |> Seq.map (fun u -> (CC |> Seq.exists (fun v -> u = v)))))
        |> Seq.map (fun (s, t) -> (s, t |> Seq.filter (fun u -> u)))
        |> Seq.map (fun (s, t) -> (s, Seq.length t))
        |> Seq.filter (fun (s, t) -> (S |> Seq.exists (fun u -> t = u)))
        |> Seq.map (fun (s, t) -> s)
    let NewBorns =
        CCN
        |> Seq.map (fun (s, t) -> t)
        |> Seq.concat
        |> Seq.filter (fun s -> not (CC |> Seq.exists (fun t -> t = s)))
        |> Seq.groupBy (fun s -> s)
        |> Seq.map (fun (s, t) -> (s, Seq.length t))
        |> Seq.filter (fun (s, t) -> B |> Seq.exists (fun u -> u = t))
        |> Seq.map (fun (s, t) -> s)
    let NC =
        Seq.append Survivors NewBorns
        |> Seq.cache // <<<<<<<<<<<<<<<<<< EDIT
    let SWt = new System.Threading.SpinWait ()
    SWt.SpinOnce ()
    if System.Console.KeyAvailable then
        match (System.Console.ReadKey ()).Key with
        | System.ConsoleKey.Q -> ()
        | _ -> Evolve (B, S, NC, (g + 1))
    else
        Evolve (B, S, NC, (g + 1))

let B = [3]
let S = [2; 3]
let IC = [4; 13; 14]
let g = 0
Evolve (B, S, IC, g)

大きな問題はSeqそれ自体を使用することではなく、正しく使用することです。デフォルトでは、シーケンスは遅延ではなく、トラバーサルごとに再評価される計算を定義します。これは、何か（ などSeq.cache）を行わない限り、シーケンスを再評価すると、プログラムのアルゴリズムの複雑さが台無しになる可能性があることを意味します。

元のプログラムは指数関数的に複雑です。これを確認するには、反復ごとにトラバースされる要素の数が 2 倍になることに注意してください。

Seqまた、あなたのプログラミング スタイルでは、演算子の後に演算子を使用することは、 or演算子Seq.cacheを使用するよりもわずかに有利であることに注意してください。ListArray

于 2012-06-21T18:33:34.970 に答える
4

コメントとすべてを参照してくださいが、このコードは地獄のように実行されます-両方List.*と他のいくつかの小さな最適化で：

let GetNeighbours p w h =
    let (f1, f2, f3, f4) = p > w, p % w <> 1, p % w <> 0, p < w * (h - 1)
    [
        p - w - 1, f1 && f2
        p - w, f1
        p - w + 1, f1 && f3
        p - 1, f2
        p + 1, f3
        p + w - 1, f4 && f2
        p + w, f4
        p + w + 1, f4 && f3
    ]
    |> List.choose (fun (s, t) -> if t then Some s else None)

let rec Evolve B S CC g =
    let w = 10
    let h = 10
    let OutputStr = sprintf "Generation %d:  %A" g CC // LINE_MARKER_1
    printfn "%s" OutputStr
    let CCN = CC |> List.map (fun s -> s, GetNeighbours s w h)
    let Survivors =
        CCN
        |> List.choose (fun (s, t) ->
            let t =
                t
                |> List.filter (fun u -> CC |> List.exists ((=) u))
                |> List.length
            if S |> List.exists ((=) t) then
                Some s
            else None)
    let NewBorns =
        CCN
        |> List.collect snd
        |> List.filter (not << fun s -> CC |> List.exists ((=) s))
        |> Seq.countBy id
        |> List.ofSeq
        |> List.choose (fun (s, t) ->
            if B |> List.exists ((=) t) then
                Some s
            else None)
    let NC = List.append Survivors NewBorns
    let SWt = new System.Threading.SpinWait()
    SWt.SpinOnce()
    if System.Console.KeyAvailable then
        match (System.Console.ReadKey()).Key with
        | System.ConsoleKey.Q -> ()
        | _ -> Evolve B S NC (g + 1)
    else 
        Evolve B S NC (g + 1)

let B = [3]
let S = [2; 3]
let IC = [4; 13; 14]
let g = 0
Evolve B S IC g
于 2012-06-21T17:16:25.133 に答える
3

私のような他の初心者が同じ問題に遭遇した場合に備えて、簡単な答えを追加すると思いました。

Ramon Snir、ildjarnおよび上記のアドバイスに従って、呼び出しをpadに変更しました。が を持っていないという事実を説明するために、単純な追加のキャスト ステップを追加する必要がありましたが、それを行うと、コードは魅力的に動作するようになりました!Seq.XList.XListgroupBy

どうもありがとう。

于 2012-06-21T17:03:01.950 に答える
2

ML ファミリの言語の最も驚くべき特徴の 1 つは、短いコードは多くの場合高速なコードであり、これは F# にも当てはまるということです。

あなたの実装を、私がここでブログに書いたはるかに高速なものと比較してください:

let count (a: _ [,]) x y =
  let m, n = a.GetLength 0, a.GetLength 1
  let mutable c = 0
  for x=x-1 to x+1 do
    for y=y-1 to y+1 do
      if x>=0 && x<m && y>=0 && y<n && a.[x, y] then
        c <- c + 1
  if a.[x, y] then c-1 else c

let rule (a: _ [,]) x y =
  match a.[x, y], count a x y with
  | true, (2 | 3) | false, 3 -> true
  | _ -> false
于 2013-02-01T01:56:26.197 に答える