编写一个函数,计算列表中大于或等于平均值的元素数量(为简单起见,使用整数除法)。
只使用一个single traversal
列表结构!
我已经有一个解决方案,但它涉及ref
从闭包更改的变量foo'
。
我对一种在满足时如何在 功能 上传递价值[]
的方式感兴趣?
我的天真解决方案使用ref
:
let foo ls =
let avg = ref 0
let rec foo' xs sumAcc lenAcc =
match xs with
| x'::xs' ->
let s = foo' xs' (x' + sumAcc) (1 + lenAcc)
if x' < !avg then s else s + 1
| [] ->
avg := (sumAcc / lenAcc) //? how to change THIS to functional code ?
0
foo' ls 0 0
编辑(3):
我对性能很感兴趣...关于list [1..11000]
`(my solution with REF) 5501: elapsed <00.0108708>`
`(nlucaroni) 5501: elapsed <00.0041484>`
`(kvb) 5501: elapsed <00.0029200>` <-- continuation is fastest
`(two pass solution) 5501: elapsed <00.0038364>`
因为1.和3.解决方案是非尾递归的,
// simple two-pass solution
let foo2pass (xs : System.Numerics.BigInteger list) =
let len = System.Numerics.BigInteger.Parse(xs.Length.ToString())
let avg = List.sum xs / len
(List.filter (fun x -> x >= avg) xs).Length
两个 pass和kvb的版本适用于大列表,即list [1I .. 10 000 000I]
:
(two-pass solution) 5000001: elapsed <00:00:12.3200438> <-- 12 first time
(two-pass solution) 5000001: elapsed <00:00:06.7956307> <-- 6
(two-pass solution) 5000001: elapsed <00:00:09.1390587> <-- 9? WHY IS THAT
(two-pass solution) 5000001: elapsed <00:00:06.8345791> <-- 6
(two-pass solution) 5000001: elapsed <00:00:09.1071856> <-- 9? WHY IS THAT
每种溶液 5 次
(kvb tail-recursive) 5000001I: elapsed <00:00:21.1825866> <-- 21 first time
(kvb tail-recursive) 5000001I: elapsed <00:00:14.8113939> <-- stable
(kvb tail-recursive) 5000001I: elapsed <00:00:14.8335997>
(kvb tail-recursive) 5000001I: elapsed <00:00:14.8418234>
(kvb tail-recursive) 5000001I: elapsed <00:00:14.8331327>
而对于list [1I .. 1 000 000I]
, kvb的解决方案更快
(two-pass solution) 500001I: elapsed <00:00:01.8975782>
(kvb tail-recursive) 500001: elapsed <00:00:00.6004453>