Почему, ленивый чисто функциональный стек в F # медленнее, чем не ленивый стек?

Question

я сравнил ленивый стек и не связанные реализации ленивым стека из: http://en.wikibooks.org/wiki/F_Sharp_Programming/Advanced_Data_Structures#Lazy_Data_Structures

В этой статье говорится, добавить функцию в O (1) для ленивых и O (п) для не ленивых. Однако работа над программой показывает, что ленивый стек в два раза медленнее от не ленивого варианта. Что может быть причиной этого?

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) становится более эффективным.

Попробуйте добавить два очень больших стека, и вы увидите существенную разницу.