F#展平功能效率比较

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是O(1),List.fold f xs并且List.foldBack f xs具有相同的复杂性O(n).

但是,@比这更复杂.假设你运行flatten1和flatten2在xs长的n每个元素是长的名单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函数实现.