A monitoring screen shows the mean and the variance of a sensor's readings so far, updated after every new reading. The feed never stops, so the readings cannot be stored and summed again each time.
Write a generator running_spread(values) that, after each value of the stream values, yields a tuple (n, mean, variance): how many values have arrived, their mean, and their population variance (the mean squared distance from the mean, dividing by n). After the first value the variance is 0.0.
Some sensors report values near a billion that differ only in the third decimal place, so the results must stay accurate to about 1e-6 there too.
Helpers available with Run: stream(values) hands out a list one value at a time, first(gen, n) takes the first n items of a generator, at(gen, k) returns the item at position k (from 0), and sensor_feed(seed, level) is an endless feed of readings around level.
Examples
Input: first(running_spread(stream([2, 4, 4, 4, 5, 5, 7, 9])), 8)
Output: [(1, 2.0, 0.0), (2, 3.0, 1.0), (3, 3.333333, 0.888889), (4, 3.5, 0.75),
(5, 3.8, 0.96), (6, 4.0, 1.0), (7, 4.428571, 1.959184), (8, 5.0, 4.0)]
(values shown rounded to 6 decimals)
Input: first(running_spread(stream([10])), 5)
Output: [(1, 10.0, 0.0)]
Constraints
valuesmay be endless; the tests read up to2 * 10**5results.- Results are compared with a tolerance of
1e-6, so the values near10**9must not lose their small differences.
Goals
- Write a generator that transforms one stream into another
- Update a mean and a variance in constant memory as each value arrives
- Keep the result accurate when the values are large and close together