f# - F# 中 seq 与 Lazy> 的性能

Question

有一个众所周知的解决方案可以生成无限的汉明数流(即所有正整数 n 其中 n = 2^i * 3^j * 5^k )。我在 F# 中以两种不同的方式实现了这一点。第一种方法使用 seq<int> .解决方案很优雅，但性能很糟糕。第二种方法使用自定义类型，其中尾部包裹在 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

Answer 1

Ganesh 是对的，因为您正在多次评估序列。 Seq.cache将有助于提高性能，但您可以从 LazyList 中获得更好的性能因为底层序列只会被评估一次然后被缓存，所以它可以被更快地遍历。事实上，这是一个很好的例子，其中 LazyList应该在正常情况下使用 seq .

看起来您使用 Seq.map 会带来一些显着的开销。这里。我相信编译器每次在那里被调用时都会分配一个闭包。我换了你的seq使用的基础代码 seq -expressions 代替，它比序列中的前 40 个数字的原始速度快约 1/3:

let rec hamming: seq<int> = seq {
    yield 1
    let xs = seq { for x in hamming do yield x * 2 }
    let ys = seq { for x in hamming do yield x * 3 }
    let zs = seq { for x in hamming do yield x * 5 }
    yield! xs -|- ys -|- zs
}

我的 ExtCore库包括一个 lazyList计算生成器的工作方式与 seq 类似，因此您可以像这样简化代码:

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

let rec hamming : LazyList<uint64> = lazyList {
    yield 1UL
    let xs = LazyList.map ((*) 2UL) hamming
    let ys = LazyList.map ((*) 3UL) hamming
    let zs = LazyList.map ((*) 5UL) hamming
    yield! xs -|- ys -|- zs
}

[<EntryPoint>]
let main argv =
    let watch = Stopwatch.StartNew ()

    hamming
    |> LazyList.take 2000
    |> LazyList.iter (printf "%d, ")

    watch.Stop ()
    printfn ""
    printfn "Elapsed time: %.4fms" watch.Elapsed.TotalMilliseconds

    System.Console.ReadKey () |> ignore
    0   // Return an integer exit code

(注意:我还使您的 (-|-) 函数通用，并修改了 hamming 以使用 64 位无符号整数，因为 32 位有符号整数在位后溢出)。这段代码在大约 450 毫秒内遍历了我机器上序列的前 2000 个元素；前 10000 个元素需要大约 3500 毫秒。