F#::遍历列表然后再返回

Question

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

---

两个通道和 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>

Answer 1

您只需要使用返回值传递堆栈的平均值:

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

Answer 2

这是另一种选择:

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)