F#中seq<int>与Lazy<LazyList<int>>的性能差异

Question

生成无限个哈明数（即所有满足条件 n = 2^i * 3^j * 5^k 的正整数 n）有一个众所周知的解决方案。我已经用 F# 实现了两种不同的方法。第一种方法使用 seq，这种解决方案优雅而简洁，但性能很差。第二种方法使用自定义类型，其中尾部包裹在 Lazy> 中，这种解决方案笨重，但性能很惊人。

可以有人解释一下为什么使用 seq 的性能如此之差，如果有办法修复它吗？谢谢。

第一种方法使用 seq。

// 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

使用Lazy<LazyList<int>>的方法2。

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

- Fysx

Answer 1

甘尼什是正确的，因为您正在多次评估该序列。Seq.cache将有助于提高性能，但使用LazyList会获得更好的性能，因为底层序列只被评估一次然后缓存，因此可以更快地遍历。实际上，这是一个很好的例子，说明应该使用LazyList而不是普通的seq。

此外，您在这里使用Seq.map引入了一些显着的开销。我认为编译器每次调用它时都会分配一个闭包。我将基于seq的代码更改为在那里使用seq表达式，对于序列中的前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个元素大约需要450毫秒；前10000个元素需要大约3500毫秒。

- Jack P.

---

@fysx 请使用我的ExtCore库 - 它包含了F# PowerPack中更新（和维护）的LazyList代码版本。它还有一个lazyList构建器，极大地简化了编写此类代码的过程。 - Jack P.

@fysx seq 推导通常更快，因为编译器可以更好地进行优化。Seq.map 本质上并不慢，但在这种情况下，由于代码重复评估序列，编译后的代码每次调用 Seq.map 都必须分配一个闭包，因此存在很多开销。 - Jack P.

@fysx 这很奇怪 - 即使我注释掉 main，我编译上面的代码也没有问题。你介意在ExtCore的github页面上开一个问题吗？我想帮助你解决这个问题，并且在那里讨论会更容易。 - Jack P.

我的错。我同时引用了FSharp.PowerPack和ExtCore。移除FSharp.PowerPack后它就可以工作了。 - Fysx

LazyList 包含在 ExtCore 中，它是 FSharp 的一个 Nuget 包：https://github.com/jack-pappas/ExtCore - George

Answer 2

在每次递归调用时，hamming的seq从头开始重新计算。使用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看起来更简洁。编写一些代码将其转换为seq可以使其处理更加美观：

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

你可以直接使用简单的main。处理LazyList时，不一定非要使用mutation，你也可以采用递归的方式进行处理。

虽然定义中有lazy和Force()这些内容，但看起来并不糟糕。如果你使用.Value代替.Force()，那么看起来会好一些。你还可以为LazyList定义一个计算生成器，类似于seq的生成器，以恢复真正好用的语法，但我不确定这是否值得努力。

- GS - Apologise to Monica

---

在使用 seq {...} 后撒上 |> Seq.cache 可以提高性能，但并不显著（特别是当我计算序列中更大的数字时）。我注意到了 https://dev59.com/tWox5IYBdhLWcg3wcj54，这似乎很好地补充了你的建议。 - Fysx

对于1..100，与非常缓慢相比，它使其几乎瞬间完成。在您的惰性列表仍然大幅优于它的典型数字是多少？ - GS - Apologise to Monica

好的，我看到它在1000上并不真正有效，即使我在每个序列上都放置了Seq.cache，10000也是一个死亡损失。 - GS - Apologise to Monica

尝试1500。 LazyList版本应该明显更快。 - Fysx

ExtCore 包含一个 lazyList 计算生成器，因此您无需自己构建 :) - Jack P.

Answer 3

这是一个性能更好的基于序列的版本。

let hamming =
    let rec loop nextHs =
        seq {
            let h = nextHs |> Set.minElement
            yield h
            yield! nextHs 
                |> Set.remove h 
                |> Set.add (h*2) |> Set.add (h*3) |> Set.add (h*5) 
                |> loop
            }

    Set.empty<int> |> Set.add 1 |> loop

- jyoung