f# Flatten函数效率比较

Question

我试图比较这两个函数，看看哪个有最好的算法。我一直在研究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]

Answer 1

xs长度为n, f各操作为0(1)，则List.fold f xs和List.foldBack f xs具有相同的复杂度O(n)。

然而，@比这更复杂。假设在长度为n的xs上运行flatten1和flatten2，其中每个元素都是长度为m的列表。生成的列表长度为n*m

由于@为O(k)，其中k为第一个列表的长度，因此flatten1的复杂度为:

// 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函数的高效实现。

Answer 2

如果有疑问，请查看源代码(从/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))。因为两者都对数据执行单个循环。但是，您可以轻松地以O(n^2)的方式实现foldback。从代码中可以看出，foldback中有更多的开销，因为创建了一个临时数组以允许以反向顺序遍历列表。