Commit: 11b06680b1e995070318ab534081c7cd1598e21d - flitter-nix (git)

A Nix-friendly SQLite-enhanced fork of Flitter, a speedrunning split timer for Unix-style terminals

Commit MetaInfo

• Révision: 11b06680b1e995070318ab534081c7cd1598e21d (tree)
• l'heure: 2022-12-21 08:06:10
• Auteur: Corbin <cds@corb...>
• Commiter: Corbin

Message de Log

Factor out Welford's algorithm.

Change Summary

• modified: src/summary.ml
• add: src/welford.ml
• add: src/welford.mli

Modification

--- a/src/summary.ml
+++ b/src/summary.ml
@@ -7,33 +7,16 @@ type t = {
   splits : (string * Duration.t list) array;
 }
 
-type welford = { n : int; m1 : float; m2 : float }
-
-let do_welford =
-  List.fold
-    ~f:(fun { n; m1; m2 } d ->
-      let delta = Float.of_int d -. m1 in
-      let dn = delta /. Float.of_int (n + 1) in
-      let t = delta *. dn *. Float.of_int n in
-      { n = n + 1; m1 = m1 +. dn; m2 = m2 +. t })
-    ~init:{ n = 0; m1 = 0.0; m2 = 0.0 }
-
-let mean { m1; _ } = m1
-
-let variance { n; m2; _ } =
-  if n < 2 then None else Some (m2 /. Float.of_int (n - 1))
-
-let stddev s = Option.value_map (variance s) ~default:0.0 ~f:Float.sqrt
 let best = List.fold ~f:Int.min ~init:Int.max_value
 
 let print_summary_segment width segment times =
-  let w = do_welford times in
+  let w = Welford.summarize_list times in
   (* NB: 12 digits is a reasonable width for durations; it would take over a
      week for a segment to surpass it! *)
   Printf.printf "%*s: %12s %12s %12s (best/mean/stddev)\n" (width + 2) segment
     (Duration.to_string (best times) 3)
-    (Duration.to_string (Float.to_int (mean w)) 3)
-    (Duration.to_string (Float.to_int (stddev w)) 3)
+    (Duration.to_string (Float.to_int (Welford.mean w)) 3)
+    (Duration.to_string (Float.to_int (Welford.stddev w)) 3)
 
 let print_route (route : Route.t) =
   Printf.printf "Title: %s  Category: %s" route.title route.category;

--- /dev/null
+++ b/src/welford.ml
@@ -0,0 +1,20 @@
+open Core
+
+type t = { n : int; m1 : float; m2 : float }
+
+let empty = { n = 0; m1 = 0.0; m2 = 0.0 }
+
+let observe { n; m1; m2 } d =
+  let delta = Float.of_int d -. m1 in
+  let dn = delta /. Float.of_int (n + 1) in
+  let t = delta *. dn *. Float.of_int n in
+  { n = n + 1; m1 = m1 +. dn; m2 = m2 +. t }
+
+let summarize_list = List.fold ~f:observe ~init:empty
+let summarize_array = Array.fold ~f:observe ~init:empty
+let mean { m1 } = m1
+
+let variance { n; m2 } =
+  if n < 2 then None else Some (m2 /. Float.of_int (n - 1))
+
+let stddev s = Option.value_map (variance s) ~default:0.0 ~f:Float.sqrt

--- /dev/null
+++ b/src/welford.mli
@@ -0,0 +1,28 @@
+(* Welford's algorithm takes the mean and variance of a stream of inputs. This
+   type holds a summary of observed inputs. *)
+type t
+
+(* A summary with no observations. *)
+val empty : t
+
+(* Observe an input. *)
+val observe : t -> int -> t
+
+(* Observe a list of inputs. *)
+val summarize_list : int list -> t
+
+(* Observe an array of inputs. *)
+val summarize_array : int array -> t
+
+(* The mean value, or expected value, or average, of a stream. *)
+val mean : t -> float
+
+(* The variance of a stream. Note that streams with very few samples do not
+   have a meaningful variance. *)
+val variance : t -> float option
+
+(* The standard deviation of a stream. When a stream is normally distributed,
+   or as enough samples are taken for the Central Limit Theorem to apply, then
+   this indicates how samples are distributed around the mean. When variance is
+   undefined, the standard deviation is zero. *)
+val stddev : t -> float