7

ハミング数の無限ストリーム (つまり、すべて正の整数 ) を生成するためのよく知られた解決策がありnますn = 2^i * 3^j * 5^k。これを F# で 2 つの異なる方法で実装しました。最初の方法は を使用しseq<int>ます。ソリューションはエレガントですが、パフォーマンスはひどいものです。2 番目の方法は、末尾が でラップされるカスタム タイプを使用しLazy<LazyList<int>>ます。ソリューションは不格好ですが、パフォーマンスは驚くべきものです。

を使用したパフォーマンスseq<int>が非常に悪い理由と、それを修正する方法があるかどうかを誰かが説明できますか? ありがとう。

を使用した方法 1 seq<int>。

// 2-way merge with deduplication
let rec (-|-) (xs: seq<int>) (ys: seq<int>) =
    let x = Seq.head xs
    let y = Seq.head ys
    let xstl = Seq.skip 1 xs
    let ystl = Seq.skip 1 ys
    if x < y then seq { yield x; yield! xstl -|- ys }
    elif x > y then seq { yield y; yield! xs -|- ystl }
    else seq { yield x; yield! xstl -|- ystl }

let rec hamming: seq<int> = seq {
    yield 1
    let xs = Seq.map ((*) 2) hamming
    let ys = Seq.map ((*) 3) hamming
    let zs = Seq.map ((*) 5) hamming
    yield! xs -|- ys -|- zs
}

[<EntryPoint>]
let main argv = 
    Seq.iter (printf "%d, ") <| Seq.take 100 hamming
    0

を使用した方法 2 Lazy<LazyList<int>>。

type LazyList<'a> = Cons of 'a * Lazy<LazyList<'a>>

// Map `f` over an infinite lazy list
let rec inf_map f (Cons(x, g)) = Cons(f x, lazy(inf_map f (g.Force())))

// 2-way merge with deduplication
let rec (-|-) (Cons(x, f) as xs) (Cons(y, g) as ys) =
    if x < y then Cons(x, lazy(f.Force() -|- ys))
    elif x > y then Cons(y, lazy(xs -|- g.Force()))
    else Cons(x, lazy(f.Force() -|- g.Force()))

let rec hamming =
    Cons(1, lazy(let xs = inf_map ((*) 2) hamming
                 let ys = inf_map ((*) 3) hamming
                 let zs = inf_map ((*) 5) hamming
                 xs -|- ys -|- zs))

[<EntryPoint>]
let main args =
    let a = ref hamming
    let i = ref 0
    while !i < 100 do
        match !a with
        | Cons (x, f) ->
            printf "%d, " x
            a := f.Force()
            i := !i + 1
    0
4

3 に答える 3

3

forはseq、hamming再帰呼び出しごとに最初から再評価されます。Seq.cacheいくつかの助けです：

let rec hamming: seq<int> =
    seq {
        yield 1
        let xs = Seq.map ((*) 2) hamming
        let ys = Seq.map ((*) 3) hamming
        let zs = Seq.map ((*) 5) hamming
        yield! xs -|- ys -|- zs
    } |> Seq.cache

ただし、ご指摘のLazyListとおり、すべてのシーケンスがキャッシュされている場合でも、大規模な入力では依然としてはるかに優れています。

なぜそれらが小さな一定の要因よりも大きく異なるのかは完全にはわかりませんが、おそらく、見栄えのLazyList悪いものを作ることに集中する方がよいでしょう. それを a に変換する何かを書くと、seq処理がはるかにうまくなります:

module LazyList =
    let rec toSeq l =
        match l with
        | Cons (x, xs) ->
            seq {
                yield x
                yield! toSeq xs.Value
            }

main次に、単純なものを直接使用できます。を処理するために突然変異を使用する必要もありませんLazyList。再帰的に行うことができます。

定義はそれほど悪くはありませんがlazy、Force()少し雑然としています。.Valueの代わりに使用すると、わずかに良く見えます.Force()。同様の計算ビルダーを定義して、非常に優れた構文を回復することもできますが、努力する価値があるかどうかはわかりません。LazyListseq

于 2014-07-06T20:35:43.707 に答える