爲什麼在F＃中懶惰的純功能堆棧比非懶惰堆棧慢？

Question

我比較懶惰棧和非懶堆棧實現從：http://en.wikibooks.org/wiki/F_Sharp_Programming/Advanced_Data_Structures#Lazy_Data_Structures

在這篇文章中，它說，附加功能是O（1）懶惰和O（n）的非懶。但是，在程序下面運行時，懶惰堆棧的速度比非懶惰速度慢兩倍。這可能是什麼原因？

type lazyStack<'a> = 
    | Node of // return an integer exit code 
       Lazy<'a * 'a lazyStack> 
    | EmptyStack 

module LazyStack = 
    let (|Consx|Nil|) = 
     function 
     | Node(item) -> 
      let hd, tl = item.Force() 
      Consx(hd, tl) 
     | EmptyStack -> 
      Nil 

    let hd = 
     function 
     | Consx(hd, tl) -> hd 
     | Nil -> failwith "empty" 

    let tl = 
     function 
     | Consx(hd, tl) -> tl 
     | Nil -> failwith "empty" 

    let cons (hd, tl) = Node(lazy (hd, tl)) 
    let empty = EmptyStack 

    let rec append x y = 
     match x with 
     | Consx(hd, tl) -> 
      Node(lazy (hd, append tl y)) 
     | Nil -> 
      y 

    let rec iter f = 
     function 
     | Consx(hd, tl) -> 
      f (hd) 
      iter f tl 
     | Nil ->() 

    let doDummyWork i = i + 1 
    let x = cons (1, cons (2, cons (3, cons (4, EmptyStack)))) 
    let y = cons (5, cons (6, cons (7, EmptyStack))) 

    let public dowork() = 
     let z = append x y 
     let z = append z y 
     () 

     hd z |> ignore 

module Stack = 
    type stack<'a> = 
     | EmptyStack 
     | StackNode of 'a * 'a stack 

    let hd = 
     function 
     | EmptyStack -> failwith "Empty stack" 
     | StackNode(hd, tl) -> hd 

    let tl = 
     function 
     | EmptyStack -> failwith "Emtpy stack" 
     | StackNode(hd, tl) -> tl 

    let cons hd tl = StackNode(hd, tl) 
    let empty = EmptyStack 

    let rec update index value s = 
     match index, s with 
     | index, EmptyStack -> failwith "Index out of range" 
     | 0, StackNode(hd, tl) -> StackNode(value, tl) 
     | n, StackNode(hd, tl) -> StackNode(hd, update (index - 1) value tl) 

    let rec append x y = 
     match x with 
     | EmptyStack -> 
      y 
     | StackNode(hd, tl) -> 
      StackNode(hd, append tl y) 

    let rec map f = 
     function 
     | EmptyStack -> EmptyStack 
     | StackNode(hd, tl) -> StackNode(f hd, map f tl) 

    let rec rev s = 
     let rec loop acc = 
      function 
      | EmptyStack -> acc 
      | StackNode(hd, tl) -> loop (StackNode(hd, acc)) tl 
     loop EmptyStack s 

    let rec contains x = 
     function 
     | EmptyStack -> false 
     | StackNode(hd, tl) -> hd = x || contains x tl 

    let rec fold f seed = 
     function 
     | EmptyStack -> seed 
     | StackNode(hd, tl) -> fold f (f seed hd) tl 

    let rec iter f = 
     function 
     | StackNode(hd, tl) -> 
      f (hd) 
      iter f tl 
     | EmptyStack ->() 

    let doDummyWork i = i + 1 
    let x = StackNode(1, StackNode(2, StackNode(3, StackNode(4, EmptyStack)))) 
    let y = StackNode(5, StackNode(6, StackNode(7, EmptyStack))) 

    let public dowork() = 
     let z = append x y 
     let z = append z y 

     hd z |> ignore 


[<EntryPoint>] 
let main argv = 
    let sw = System.Diagnostics.Stopwatch() 
    sw.Start() 
    let n = 1000000 
    for i = 0 to n do 
     Stack.dowork() 
    printfn "%A" sw.Elapsed 
    sw.Restart() 
    for i = 0 to n do 
     LazyStack.dowork() 
    printfn "%A" sw.Elapsed 
    0 

Answer 1

Big-O是運行時如何隨着輸入大小變大而增長的。 O(1)函數比O(n)函數具有更大的開銷是相當常見的，因此對於非常小的值n會比較慢。由於這個開銷是相對恆定的，但是在某個時候它最終會變得更快。從here考慮該曲線圖：

的O(1)溶液被固定在29塔頂，而O(n)溶液最初開始比低得多，但線性增長。只有當n > 52時，O(1)解決方案變得更有效率。

嘗試追加兩個非常大的堆棧，您將看到顯着的差異。