f#中的seq <int>与Lazy <LazyList <int >>的性能

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位有符号整数后溢出).这段代码在我的机器上运行序列的前2000个元素~45ms; 前10000个元素需要~3500ms.

Answer 2

您的seqforhamming会在每次递归调用时从头开始重新评估。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丑陋。编写一些东西将其转换为 aseq可以使处理它变得更好：

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