递归计算列表平均值

Question

我有一份OCaml的作业，其中一个问题是关于计算列表平均值的。我在1或2年前已经用另一种语言完成了这个问题，正如我第一次做时所决定的那样，我决定不仅仅将所有元素相加并除以长度。主要原因是担心浮点溢出。

因此，我在维基百科上找到了我上次使用过的公式：递归平均值公式。

我在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

使之工作了。

我告诉自己第二行代码逻辑上是计算正确答案的好方法，但我不明白一开始哪里出错了。我是否翻译了有偏见的公式？或者翻译时漏掉了些什么？

到目前为止，对我来说，第一行代码仍然是公式的转录，而第二行代码是计算正确答案的方式。但我相信这里有些事情我无法理解。请有人为我解惑吧。

- Samy DULOR

Answer 1

以下是一个不会出现溢出且时间复杂度正确的函数版本供参考：

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.)

相对误差值：float类型，-1.66533453693773481e-16

- octachron

Answer 2

但我相信在这里有些东西我无法理解

总体逻辑没有问题，我认为公式本身是混淆的根源。

显然，在计算中被除数中的（n-1）个乘数不能变成零（否则您会“丢弃”先前累积的值-这实际上是在您的第一次尝试中发生的），而保证这一点的唯一方法是设置n>0。因此，默认情况下的第一个方程必须以1为索引，而不是0。

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

- Konstantin Strukov

---

你确认了我的想法。还有一个问题：这是否意味着公式是“错误”的？ 应该更正为基本情况类似于û1 = u1吗？我不知道如何在这里编写数学内容，但我认为您会明白我的意思。或者，基本情况应该分为两种情况，其中索引= 0和索引= 1？ - Samy DULOR

是的，公式似乎是错误的。在数学归纳法中，以0为基础情况索引是很典型的，但这并非必须要求。而且，在这种特殊情况下，只有当“n”从1开始时，该公式才是正确的... - Konstantin Strukov

Answer 3

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

在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!"
;;

递归调用应该只评估一次，因为它是纯的。

- pjs

---

你不想在这里使用 List.length，因为它会使函数在列表长度上呈二次方增长。而且递归调用被评估了两次，使得函数在列表长度上呈指数级增长。 - octachron

@octachron 我是偶尔使用OCaml的用户（十年中只用了3次），所以如果有更好的方法来使用列表的大小，我非常愿意听取建议。话虽如此，我查阅的文档说，如果OCaml能够检测到在两次调用函数之间没有任何变化，那么它被认为是“纯”的，只会在第一次评估时进行计算，并且结果将被保留以供后续评估使用。 - pjs

OCaml 在函数级别上不追踪纯度。更一般地说，依赖编译器优化来改变算法复杂度总是很脆弱的。即使使用 -O3，你的函数也没有被优化。让我写出正确的函数。 - octachron

Answer 4

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

你调用了aux hd 1 l。所以你从列表头开始平均并计数为1。但是在公式中，你将前一个平均值乘以count - 1，在第一次调用时为0。所以你把头扔掉了。

以这种方式编写调用：aux 0.0 1 (hd::tl)或aux hd 2 tl。

如果你进一步允许空列表的平均值为0.0，那么你甚至不需要模式匹配外部函数。更进一步，如果你使平均值和计数参数可选（默认为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.

- Goswin von Brederlow

---

但是在这个公式中，你要用前一个平均数乘以计数-1。没错，我正在这样做，但这不是公式所说的吗？我想我的思维过程有些问题：该公式是针对n=1定义的，否则它就不会是递归的了。对于n(=1)-1的平均值x0被乘以n(=1)-1，所以是0。所以是的，我们失去了第一个值...我在纸上用笔也是这么想的。我愚蠢地把我的问题标记为Ocaml，但我几乎不相信这更多是关于维基百科或者是我和数学的问题。我认为这是第二个选项。 - Samy DULOR

在这个公式中，计数应该是当前项目的数量。你删除了列表的头部（第一个项目），所以当你使用这个公式时，下一个项目应该有计数2。但是你只有1。你少算了1。 - Goswin von Brederlow

我没有问题看出我的代码为什么不起作用。它似乎与维基百科上的这个公式相矛盾。现在我更好地理解了这个公式的含义，但它仍然对我来说很奇怪。在法语维基上，它说n是“连续值的计数”，他们也称之为“周期”。但对我来说，0个连续值的平均值是零；而不是列表中的第一个值。它字面上写在起始情况旁边，“周期为0的移动平均值只取一个项”。那么一个连续期的移动平均值不应该只有一个项吗？ - Samy DULOR

维基百科也可能是错误的。该公式仅在第一个项目计数为1，第二个项目计数为2等等时有效。如果您的索引应该是以0为基础，则必须在公式中使用count和count+1。请注意我在那里使用索引一词。大多数情况下，索引是以0为基础的，但计数、大小或长度为1的。在我的看法中，0期应与计数为1配对。 - Goswin von Brederlow

Answer 5

为什么要把它搞得这么复杂呢？为什么不直接计算总和和数量呢？

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

现在你有元素的数量和元素的总和。

- G4143

---

好的，有两件事情，首先，即使算法相同，它也必须应用于浮点数列表。另一方面，为了回答你的问题，我使用这种方法来避免sum变量溢出。count变量也可能会溢出，但我不会每天都遇到Int.max_int大小的列表。 - Samy DULOR

你的递归函数在计算 count * average 时仍然会溢出。 - octachron

@octachron 请看我的答案，其中有一种避免溢出计算的变体。 - pjs

Answer 6

我在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

这是你要找的吗？

- G4143

---

为什么提供两个答案？你真的认为这个问题值得两个单独的回答吗？ - Dharman

@G4143 我并不是在寻找代码；用修改后的一行代替原始代码可以完美地使函数工作。我无法理解的是，第一行似乎是将OCaml中的数学公式“翻译”成代码，而修改后的代码似乎不是这样。所以，要么我在公式中遗漏了某些东西，而我的修改后的代码才是其翻译；要么这个公式是错误的...（这让我很难相信）。我承认这个问题更多涉及到数学而非OCaml。同时，非常感谢您对我的问题所付出的关注。 - Samy DULOR