1

我试图比较这两个函数，看看哪个算法最好。我一直在研究 n 复杂度的顺序，虽然我不知道如何从数学上得出它（这很遗憾），但我有时可以猜到顺序。我认为要知道该算法是否比另一个更好，我需要在渐近时间、复杂性和实验方面来看待它们。

let flatten1 xs = List.fold (@) [] xs

let flatten2 xs = List.foldBack (@) xs []

我使用了 F##time功能，这就是我得到的。

Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int list =
  [1; 2; 3; 5; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19;
   20; 5; 4; 5; 6]
>
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int list =
  [1; 2; 3; 5; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19;
   20; 5; 4; 5; 6]
4

2 回答 2

5

xs长度n和每个操作f都是 O(1)，List.fold f xs并且具有List.foldBack f xs相同的复杂度O(n)。

然而，@比这更复杂。假设您在长度上运行flatten1，其中每个元素都是长度列表。结果列表的长度flatten2xsnmn*m

因为第一个列表的长度@是O(k)哪里，所以复杂度是：kflatten1

// After each `@` call, the first list (the accumulator) increases its length by `m`
O(m + 2*m + 3*m + ... + (n-1)*m) 
= O(n*(n-1)*m/2)

在 的情况下flatten2，第一个列表总是长度为 的列表m：

O(m + m + ... + m) // n-1 steps
= O((n-1)*m)

您可以很容易地看到这flatten2将比flatten1. List.foldBack无论如何，时间复杂度的差异将支配额外的分配。为了说明，这是一个显示差异的快速测试

let flatten1 xs = List.fold (@) [] xs
let flatten2 xs = List.foldBack (@) xs []

let xs = [ for _ in 1..1000 -> [1..100] ]

#time "on";;

// Real: 00:00:01.456, CPU: 00:00:01.466, GC gen0: 256, gen1: 124, gen2: 1
let xs1 = flatten1 xs;;

// Real: 00:00:00.007, CPU: 00:00:00.000, GC gen0: 1, gen1: 0, gen2: 0
let xs2 = flatten2 xs;;

请注意，您可以只使用List.concat，这是一种有效的flatten功能实现。

于 2013-06-06T08:08:54.607 回答
1

如果有疑问，请查看源代码（来自 /src/fsharp/FSharp.Core/list.fs）

    // this version doesn't causes stack overflow - it uses a private stack 
    [<CompiledName("FoldBack")>]
    let foldBack<'T,'State> f (list:'T list) (acc:'State) = 
        let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
        match list with 
        | [] -> acc
        | [h] -> f.Invoke(h,acc)
        | [h1;h2] -> f.Invoke(h1,f.Invoke(h2,acc))
        | [h1;h2;h3] -> f.Invoke(h1,f.Invoke(h2,f.Invoke(h3,acc)))
        | [h1;h2;h3;h4] -> f.Invoke(h1,f.Invoke(h2,f.Invoke(h3,f.Invoke(h4,acc))))
        | _ -> 
            // It is faster to allocate and iterate an array than to create all those 
            // highly nested stacks.  It also means we won't get stack overflows here. 
            let arr = toArray list
            let arrn = arr.Length
            foldArraySubRight f arr 0 (arrn - 1) acc

并折叠

    [<CompiledName("Fold")>]
    let fold<'T,'State> f (s:'State) (list: 'T list) = 
        match list with 
        | [] -> s
        | _ -> 
            let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
            let rec loop s xs = 
                match xs with 
                | [] -> s
                | h::t -> loop (f.Invoke(s,h)) t
            loop s list

由此我们可以看出两者具有相同的时间复杂度(O(n))。因为两者都对数据执行单个循环。但是，您可以轻松地foldback以O(n^2). 从代码中可以看出，foldback由于创建了一个临时数组以启用以相反顺序遍历列表，因此会产生更多开销。

于 2013-06-06T06:04:58.747 回答