多个序列的惰性笛卡尔积（序列的序列）

Question

你能提出更简单、更清晰的编写此函数的方法吗？

let cartesian_product sequences = 
    let step acc sequence = seq { 
        for x in acc do 
        for y in sequence do 
        yield Seq.append x [y] }
    Seq.fold step (Seq.singleton Seq.empty) sequences 

- Vladimir Reshetnikov

---

请查看以下链接：https://dev59.com/gHA75IYBdhLWcg3wW3y8#3334871。 - Juliet

对于一个与这个 F# 解决方案基本相同的 C# 解决方案，请参见 https://dev59.com/JXA75IYBdhLWcg3w0cjx#3098381。 - Eric Lippert

Answer 1

我对朱丽叶链接的函数进行了基准测试：

let items = List.init 6 (fun _ -> [0..9])
cart1 items |> Seq.length |> ignore

实际时间：00:00:03.324，CPU时间：00:00:03.322，GC第0代：80，第1代：0，第2代：0

稍作修改（以进行苹果到苹果的比较）的版本：

let cartesian items =
  items |> Seq.fold (fun acc s ->
    seq { for x in acc do for y in s do yield x @ [y] }) (Seq.singleton [])

cartesian items |> Seq.length |> ignore

真实时间: 00:00:00.763, CPU时间: 00:00:00.780, 垃圾回收第0代：37次，第1代：2次，第2代：1次

你的程序明显更快（且导致更少的GC）。在我看来，你的代码已经很好了。

- Daniel

---

老问题了，但你那里有一个第二代集合。那会导致更少的垃圾回收吗？ - Arshia001

Answer 2

不太优雅，但速度似乎更快的解决方案：

let cartesian_product2 sequences = 
    let step acc sequence = seq { 
        for x in acc do 
        for y in sequence do 
        yield seq { yield! x ; yield y } }
    Seq.fold step (Seq.singleton Seq.empty) sequences 

;

> cartesian items |> Seq.length;;
Real: 00:00:00.405, CPU: 00:00:00.405, GC gen0: 37, gen1: 1, gen2: 0
val it : int = 1000000
> cartesian_product2 items |> Seq.length;;
Real: 00:00:00.228, CPU: 00:00:00.234, GC gen0: 18, gen1: 0, gen2: 0
val it : int = 1000000

- Ed'ka

---

这似乎更快，因为你返回的是 seq<seq<_>> 而不是 seq<list<_>>，也就是说，你的内部序列没有被计算。尝试使用 cartesian_product2 items |> Seq.map Seq.toList |> Seq.length。 - Daniel

@Daniel：说得好。但它仍然比作者的解决方案快2倍（同时仍然保持懒惰，如所需）。 - Ed'ka

这个方案在构建序列和实现它方面更快吗？还是因为测试没有实现子序列而两者都不是？ - Maslow