如何阻止延迟评估减慢分而治之算法

Question

我在 F Sharp 中使用递归函数构建特定的树结构，使用在每个阶段评估的容器。我被指示改用 Seq ，因为它的惰性评估应该最大限度地减少操作次数。（我知道，例如，使用惰性求值的 .NET 排序函数比在数组上使用就地交换更快）。这种变化实际上产生了相反的效果，对于大量输入，大大减慢了树的构建速度。我想我已经广泛地解决了这个问题，如下面的代码所示：

首先我们有一个"lessthan"函数来计算它被调用的次数：

let mutable count=0
let lessthan a b=count<-count+1
                 b<a

Seq 和 Array 的简单分而治之版本：

let rec recursion n inSeq = 
  if  n<=1 then inSeq
  else 
     let pivot = n/2
     let left = inSeq |> Seq.filter (fun i->i|>lessthan pivot) |> recursion (n/2)
     let right = inSeq |> Seq.filter (fun i->not (i|>lessthan pivot)) |> recursion (n/2)
     Seq.append left right


 //the same function with arrays to give eager evaluation
let rec recursionA n inAr  =
  if  n<=1 then inAr
  else let pivot = n/2
     let left = inAr |> Array.filter (fun i->i|>lessthan pivot) |> recursionA (n/2)
     let right = inAr |> Array.filter (fun i->not (i|>lessthan pivot)) |> recursionA (n/2)
     Array.append left right

最后测试调用比较的次数，以及惰性版本何时调用。

let test n= 
    let reverse = Seq.init  n (fun i->i) |>recursion n
    do printf "lazy:"
    for n in reverse do printf "%d (%d) " n count
    do printf "\n\n"
    do count<-0  
    let reverseArray=Array.init  n (fun i->i)|>recursionA n
    do printf "eager:\n%d\n" count

 //IO
do printf "Type an integer\n"
let intstring=System.Console.ReadLine()
let worked, numberofpoints = System.Int32.TryParse(intstring) 
do if worked then test numberofpoints

当我输入 2 的幂时，m=2^k，函数的数组版本调用小于 2*m*k。这是有道理的（每个递归级别 2 k）。当 As m 增长时，Seq 版本调用少于 m(log m)^2 次，这可能类似于将每个值评估为

"in 0..2^n-1" AND 小于 2^(n-1) AND 在 0..2^(n-1)-1 AND 小于 2^(n-2) AND..."

（但这并不完全取决于调用次数何时激增以及我们在调试模式下进行的比较）

是否有任何方法可以消除这些影响并让惰性评估提高性能，就像其他算法一样？

注意。我检查了在调试模式下手动计数递增计数器并没有什么不同。

我知道数组版本可以使用 Array.Partition

进行更少的比较

Answer 1

使用 seq<'T> 的惰性解决方案的问题是序列不做任何缓存。这意味着当您创建一个序列并使用它两次时，它会被重新计算：

let test = Seq.init 10 (fun i -> printfn "%d" i; i)
test |> Seq.map id |> Seq.length  // Prints 0 .. 9
test |> Seq.map id |> Seq.length  // Prints 0 .. 9 again

避免这种情况的一种方法是使用 Seq.cache，其中 returns 一个仅计算一次并缓存其结果的序列（因此，它变得更快，但需要更多内存）。

在您的示例中，您可以运行 Seq.cache 在 recursion 中（在您将 inSeq 传递给两个处理它的不同函数）：

let rec recursion n inSeq =   
  if  n<=1 then inSeq
  else 
    let pivot = n/2
    let inSeq = Seq.cache inSeq
    let left = inSeq |> Seq.filter (lessthan pivot) |> recursion (n/2)
    let right = inSeq |> Seq.filter (lessthan pivot >> not) |> recursion (n/2)
    Seq.append left right

(我还使用了更合理的缩进——缩进函数的整个主体，使其在 = 符号之后显然有效，但这并不是真正推荐的模式。添加换行符使代码成为更具可读性...)

如何阻止延迟评估减慢分而治之算法

How to stop lazy evaluation slowing down a divide and conquer algorithm

algorithm

recursion

f#

lazy-evaluation