6

编写一个函数,计算列表中大于或等于平均值​​的元素数量(为简单起见,使用整数除法)。
只使用一个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

两个 passkvb的版本适用于大列表,即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>
4

3 回答 3

9

您只需要将平均值与返回值一起向上传递:

let foo ls =
    let rec foo xs sumAcc lenAcc  = match xs with
        | x::xs -> let avg,s = foo xs (x + sumAcc) (1 + lenAcc) in
                   if x < avg then (avg,s) else (avg,s+1)
        | []    -> (sumAcc / lenAcc),0
    in
    let avg,res = foo ls 0 0 in
    res
于 2009-11-23T18:23:44.387 回答
7

这是另一种选择:

let foo =
  let rec helper sum ct getCt = function
  | x::xs -> 
      helper (sum+x) (ct+1) (fun avg -> getCt(avg) + (if avg <= x then 1 else 0)) xs
  | [] -> getCt(sum/ct)
  helper 0 0 (fun avg -> 0)

为了帮助澄清这里发生了什么,我将描述辅助函数的参数:

  • sum:到目前为止看到的所有项目的总和
  • ct:到目前为止看到的所有项目的计数
  • getCt:一个采用单个参数的函数,它返回到目前为止看到的至少与该参数一样大的项目数的总数
  • 模式匹配的最终列表参数
    • 如果它为空,则通过将总数除以计数来计算所有项目的平均值,然后将其传递给getCt函数以确定有多少项目大于它。
    • 否则,递归到列表的尾部,传入更新的总数和计数。新getCt函数应该调用前一个getCt函数来查看在此之前有多少项大于平均值,如果该项也大于平均值,则增加该总数。

也可以创建仅使用尾调用的修改版本,因此即使在任意大小的列表上也不会导致堆栈溢出。为此,我们的getCt函数现在需要一个累加器参数来表示到目前为止的计数:

let foo =
  let rec helper sum ct getCt = function
  | x::xs -> 
      helper (sum+x) (ct+1) (fun avg n -> getCt avg (if avg <= x then n+1 else n)) xs
  | [] -> getCt (sum/ct) 0
  helper 0 0 (fun avg n -> n)
于 2009-11-23T18:32:25.197 回答
0

Haskell 的懒惰评价真的在“喜结良缘”上大放异彩:

avgList t = let (final, sum, count) = go t 0 0 0
                avg = sum `div` count
                go [] finalA sumA countA = (finalA, sumA, countA)
                go (x:xs) finalA sumA countA = go xs (x' + finalA) (sumA + x) (countA + 1)
                    where x' = if x >= avg then 1 else 0
            in final
于 2009-12-31T20:46:28.730 回答