性能 – 为什么List.foldBack与List.fold一样快

“F#中的列表实现为单链表,这意味着只访问列表头部的操作是O(1),元素访问是O(n).” – http://msdn.microsoft.com/en-us/library/dd233224.aspx

考虑到这一点,访问从最后一个元素到第一个元素的元素的List.foldBack应该比List.fold慢得多.但是,我无法通过测试证实这一点:

let f acc x = acc + x
List.fold f 100 [1 .. 5000000] ;;
List.foldBack f [1 .. 5000000] 100;;

#time

> List.fold f 100 [1 .. 5000000] ;;
Real: 00:00:01.379, CPU: 00:00:01.468, GC gen0: 29, gen1: 26, gen2: 2
val it : int = 1647668740
> List.foldBack f [1 .. 5000000] 100;;
Real: 00:00:01.417, CPU: 00:00:01.500, GC gen0: 28, gen1: 25, gen2: 2
val it : int = 1647668740
>

为什么List.foldBack对List.fold执行相同的操作?

如果你查看 the source for List.foldBack,你可以看到它将列表转换为数组,然后从最后应用累加器函数迭代它以获得结果.
相关文章
相关标签/搜索