递归计算列表平均值

Question

我在OCaml中有作业要做，其中一题是计算一个列表的平均值。我在 1 或 2 年前已经用另一种语言做到了，就像我第一次做的那样，我决定不仅对所有元素求和并除以长度。主要原因是怕浮点数溢出

所以我在维基百科上找到了我上次使用的公式：recursive average formula。

我在 OCaml 中是这样编码的：

let average = function
| []    -> raise Empty_list
| hd::l ->
    let rec aux average count = function
        | hd::l -> aux ((average*.(float (count-1))+.hd)/.(float (count))) (count+1) l
        | _     -> average
    in aux hd 1 l
;;

对我来说，这看起来像是 OCaml 中公式的精确转录。

但是它没有用，但是，在拿了一张纸，一支笔并考虑了一下之后，我设法通过替换行使其工作：

| hd::l -> aux ((average*.(float (count-1))+.hd)/.(float (count))) (count+1) l

与：

| hd::l -> aux ((average*.(float (count))+.hd)/.(float (count+1))) (count+1) l

它奏效了。

我告诉自己第二行在逻辑上是计算正确答案的好方法，但我不明白一开始哪里出了问题。我是否翻译了有偏见的公式？还是我翻译的时候遗漏了什么？

此时，它还在找我，第一行是公式的转录，第二行是计算正确答案的方法。但我相信这里有一些我无法理解的东西。有人可以帮我解释一下吗？

Answer 1

为什么搞得这么复杂？为什么不只计算总和和计数？

let int_avg lst =
  let rec int_avg_aux cnt sum lst =
    match lst with
    | [] -> (cnt, sum)
    | hd::tl -> int_avg_aux (cnt + 1) (hd + sum) tl in
  int_avg_aux 0 0 lst

let (c, s) = int_avg [1;2;3;4;5;]

let () = Printf.printf "%d %d\n" c s

现在你有了元素的个数和元素的总和。

Answer 2

我在 OCaml 中尝试了你的公式，我认为我做对了：

let avg c lst =
  let rec avg_aux c l =
  match l with
  | [] -> 0.0
  | hd::tl ->
    (((avg_aux (c -. 1.0) tl) *. (c -. 1.0)) +. hd) /. c in
  avg_aux c lst

let lst = [max_float;2.0;max_float;4.0;5.0;6.0]

let ans = avg (float(List.length lst)) lst

let () = Printf.printf "%f\n" ans

这是您要找的吗？

Answer 3

But I believe there's something I can't understand here

总的来说你的逻辑没有错，我认为公式本身就是混乱的根源。

很明显，在计算过程中，股息中的 (n - 1) 乘数不能变为零（否则你 "discard" 之前累积的值 - 这实际上发生在你的第一次尝试中），并且确保这一点的唯一方法是设置 n > 0。因此，第一个等式（默认情况）的索引必须为 1，而不是 0。

因此，对于基本情况，您有 n = 1，对于下一次迭代，n = 2 等。这与您的第二个（正确的）表达式匹配，而不是第一个...

Answer 4

平均值公式有一种更简洁的形式，它可以找到旧平均值和新观测值之间的差值，然后按样本大小缩放差值以更新平均值。基本情况是单个观察值的平均值就是该观察值。（空列表的平均值未定义。）

在 OCaml 中：

let rec avg lst =
  match lst with
    | [x]     -> x
    | x::rest -> avg rest +. (x -. avg rest) /. float(List.length lst)
    | []      -> failwith "avg called on empty list!"
;;

递归调用应该只计算一次，因为它是纯粹的。

Answer 5

问题不在于公式，而在于你使用它的方式。

你打电话给aux hd 1 l。因此，您从列表头部的平均值和计数 1 开始。但是在公式中，您将前一个平均值乘以 count - 1，在第一次调用时为 0。所以你所做的就是把头扔掉。

这样写就是aux 0.0 1 (hd::tl)或aux hd 2 tl.

如果您进一步允许空列表的平均值为 0.0，您甚至不需要外部函数的模式匹配。更进一步，如果你将 average 和 count 参数设为可选（分别默认为 0.0 和 1），你甚至不需要辅助函数：

let rec average ?(avg=0.0) ?(count=1) = function
| []     -> avg
| hd::tl -> average
                ~avg:((avg*.(float (count-1))+.hd)/.(float (count)))
                ~count:(count+1)
                tl;;
val average : ?avg:float -> ?count:int -> float list -> float = <fun>

# average [1.;2.;3.];;
- : float = 2.

Answer 6

作为参考，这里是一个不会溢出的函数版本，具有正确的时间复杂度：

let avg l =
  let mu_n' (n,mu_n) x =
    let n' = n + 1 in
    n', mu_n +. (x -. mu_n) /. float n' in
  snd (List.fold_left mu_n' (0,0.) l)

let x = avg [max_float; 1.; 2.; max_float;2.; 3.; max_float; 5.; 6.]
let relative_error = (x -. max_float /. 3.) /. (max_float /. 3.)

val relative_error : float = -1.66533453693773481e-16

递归计算列表平均值

Recursively calculate a list average

recursion

ocaml

average