为什么,F#中的Lazy纯函数堆栈比非惰性堆栈慢？

Question

我已经比较了懒惰堆栈和非惰性堆栈实现:http://en.wikibooks.org/wiki/F_Sharp_Programming/Advanced_Data_Structures#Lazy_Data_Structures

在本文中它说,append函数对于惰性函数是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.由于这种开销相对稳定,但在某些时候它最终会更快.从这里考虑这个图:

该O(1)溶液被固定在29塔顶,而O(n)溶液最初开始比低得多,但线性增长.只有当解决方案变得更有效时才会n > 52这样O(1).

尝试附加两个非常大的堆栈,您将看到显着的差异.