Back to course

Streaming Statistics in Constant Memory

"Compute the rolling mean and variance of a stream, in constant time per update" is a question research and developer interviews ask almost word for word. The obvious answer recomputes the statistics over the whole window for every new value, and on a tick stream that is far too slow: a window of 20,000 prices recomputed on every tick is 20,000 operations per tick. The answer interviewers want keeps a few running numbers and updates them as values enter and leave.

A growing window: running sums

When every value stays in the window, keep the count nn, the sum S=∑xiS = \sum x_i and the sum of squares Q=∑xi2Q = \sum x_i^2. Each new value adds to all three in O(1)O(1), and the statistics follow from them:

xˉ=Sn,s2=nQ−S2n(n−1)\bar{x} = \frac{S}{n}, \qquad s^2 = \frac{nQ - S^2}{n(n - 1)}

The rest of this lesson is for subscribers

Unlock every lesson in Programming for Quantitative Developers, and every other premium course.

Subscribe to continue

Test your knowledge

Questions are only available to subscribers.
Continue

Keep reading Programming for Quantitative Developers

33 lessons in this course, and every other premium course, on one subscription.

Subscribe now
  • Every lesson in every course, with the worked examples and interactive simulators
  • Graded questions on every lesson, with explanations for the wrong answers as well as the right one
  • The trainers, timed assessments and brainteaser library that go with them