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

两个 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>
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 回答