Рекурсивно рассчитать средний список

Question

У меня есть домашняя работа в OCaml, и один вопрос касается вычисления среднего по списку. Я делал это уже 1 или 2 года go на другом языке, и, как и в первый раз, я решил не только суммировать все элементы и делить на длину. Основная причина - страх переполнения с плавающей точкой.

Итак, я нашел формулу, которую использовал в последний раз в Википедии: рекурсивная формула среднего значения .

Я закодировал это так в 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 (<b>count</b>))+.hd)/.(float (<b>count+1</b>))) (count+1) l

и это сработало.

Я сказал себе, что вторая строка логически хороша для вычисления правильного ответа, но я не могу понять, что было не так с самого начала. Я перевел предвзятую формулу? Или я что-то упустил при переводе?

На данный момент мне все еще кажется, что первая строка - это транскрипция формулы, а вторая - способ вычисления правильного ответа. Но я верю, что есть кое-что, чего я не могу понять здесь. Может кто-нибудь пролить свет на это для меня?

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

vallative_error: float = -1.66533453693773481e-16

Answer 2

Проблема не в формуле, а в том, как вы ее используете.

Вы звоните 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.

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

Рекурсивный вызов должен оцениваться только один раз, поскольку он чистый.

Answer 4

Но я верю, что здесь есть кое-что, чего я не могу понять

В вашей логике нет ничего плохого c в общем, сама формула, я думаю, является источником путаницы.

Совершенно очевидно, что множитель (n - 1) в дивиденде НЕ должен превращаться в ноль во время вычисления (в противном случае вы «отбрасываете» ранее накопленное значение - что на самом деле произошло с вашей первой попыткой), и единственный способ чтобы убедиться, что это установить n > 0. Итак, первое уравнение (случай по умолчанию) должно быть проиндексировано 1, а не 0.

Итак, у вас есть n = 1 для базового случая, n = 2 для следующей итерации et c. который соответствует вашему второму (правильному) выражению, а не первому ...

Answer 5

Я попробовал вашу формулу в 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 6

Зачем делать это так сложно? Почему бы просто не вычислить сумму и не считать?

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

Теперь у вас есть количество элементов и сумма элементов.