{adamcoding}
← The Machine and the Market
Part II
08
Chapter 8

The Sliding Window

The problem

Chapter 4 showed that recomputing a moving average from scratch each bar is O(n × window) and keeping a running sum is O(n). That's the right idea and the implementation was still clumsy - it needed the whole price history up front.

Live, prices arrive one at a time. You want a thing you can feed a price to, which tells you the current average, using a fixed amount of memory forever.

That thing is a ring buffer, and it's one of the genuinely elegant data structures.

The idea

A fixed-size slice plus a position that wraps around. Write to position 0, 1, 2, ... and when you reach the end, go back to 0 and overwrite the oldest value.

   window of 5, after 5 values          after the 6th value arrives
   ┌────┬────┬────┬────┬────┐          ┌────┬────┬────┬────┬────┐
   │ 100│ 101│ 102│ 103│ 104│          │ 105│ 101│ 102│ 103│ 104│
   └────┴────┴────┴────┴────┘          └────┴────┴────┴────┴────┘
     ↑                                        ↑
   pos=0 (next write)                       pos=1

Nothing shifts. Nothing is allocated. One write per value, forever.

Building it

go
package main

import "fmt"

type RingBuffer struct {
	data   []float64
	pos    int
	filled bool
}

func NewRingBuffer(size int) *RingBuffer {
	return &RingBuffer{data: make([]float64, size)}
}

// Add stores a value, overwriting the oldest if full.
// Returns the value that was evicted, and whether one was.
func (r *RingBuffer) Add(v float64) (evicted float64, wasFull bool) {
	if r.filled {
		evicted = r.data[r.pos]
		wasFull = true
	}
	r.data[r.pos] = v
	r.pos++
	if r.pos == len(r.data) {
		r.pos = 0
		r.filled = true
	}
	return evicted, wasFull
}

func (r *RingBuffer) Full() bool { return r.filled }
func (r *RingBuffer) Size() int  { return len(r.data) }

Some of this is Chapter 10's material arriving early. type RingBuffer struct { ... } defines a new kind of value with named fields. func (r *RingBuffer) Add(...) is a method - a function attached to that type, where r is the value it was called on. The * means it can modify it. Take it on trust for now; Chapters 10 and 11 explain it properly.

The moving average on top

go
type MovingAverage struct {
	buf *RingBuffer
	sum float64
}

func NewMovingAverage(window int) *MovingAverage {
	return &MovingAverage{buf: NewRingBuffer(window)}
}

// Update feeds in a new price and returns the average,
// plus whether enough data has arrived to be meaningful.
func (m *MovingAverage) Update(price float64) (float64, bool) {
	evicted, wasFull := m.buf.Add(price)
	m.sum += price
	if wasFull {
		m.sum -= evicted
	}
	if !m.buf.Full() {
		return 0, false
	}
	return m.sum / float64(m.buf.Size()), true
}

One addition, one subtraction, one division per bar. It does not care whether your window is 5 or 5,000 - the cost is identical. That is the whole point.

See It Work: watch the ring wrap

Print the internals each step and the abstraction stops being abstract:

go
func main() {
	ma := NewMovingAverage(4)
	prices := []float64{100, 102, 101, 105, 103, 107, 104}

	fmt.Printf("%-8s %-30s %-10s %s\n", "price", "buffer", "sum", "average")
	for _, p := range prices {
		avg, ready := ma.Update(p)
		status := fmt.Sprintf("%.2f", avg)
		if !ready {
			status = "(warming up)"
		}
		// Note: format the slice into a string FIRST. Writing %-30v with
		// a slice pads every *element* to 30 characters, not the whole
		// slice, and the table falls apart.
		buf := fmt.Sprintf("%v", ma.buf.data)
		fmt.Printf("%-8.0f %-30s %-10.0f %s\n", p, buf, ma.sum, status)
	}
}
price    buffer                         sum        average
100      [100 0 0 0]                    100        (warming up)
102      [100 102 0 0]                  202        (warming up)
101      [100 102 101 0]                303        (warming up)
105      [100 102 101 105]              408        102.00
103      [103 102 101 105]              411        102.75
107      [103 107 101 105]              416        104.00
104      [103 107 104 105]              419        104.75

Watch position 0 get overwritten by 103 on the fifth bar. Watch the sum stay bounded rather than growing. This is the structure working, in front of you.

See It Work: prove it's faster

go
package main

import "testing"

func naiveMA(prices []float64, window int) []float64 {
	var out []float64
	for i := window - 1; i < len(prices); i++ {
		sum := 0.0
		for j := i - window + 1; j <= i; j++ {
			sum += prices[j]
		}
		out = append(out, sum/float64(window))
	}
	return out
}

func ringMA(prices []float64, window int) []float64 {
	ma := NewMovingAverage(window)
	out := make([]float64, 0, len(prices))
	for _, p := range prices {
		if avg, ok := ma.Update(p); ok {
			out = append(out, avg)
		}
	}
	return out
}

var testPrices = makePrices(100000)

func BenchmarkNaiveMA200(b *testing.B) {
	for i := 0; i < b.N; i++ {
		naiveMA(testPrices, 200)
	}
}

func BenchmarkRingMA200(b *testing.B) {
	for i := 0; i < b.N; i++ {
		ringMA(testPrices, 200)
	}
}

Expect the ring version to be something like 100× faster at a 200-bar window. Then change the window to 1000 and run again: the naive version gets five times slower and the ring version doesn't change at all. That difference - not the raw speed, but how each one responds to a bigger problem - is what complexity analysis is actually about.

See It Work: the running sum drifts

Here's a real-world failure mode you'd never find by reading.

The running sum subtracts a float and adds a float, millions of times. From Chapter 2 you know each operation carries a tiny error. Those errors accumulate:

go
func main() {
	window := 20
	ma := NewMovingAverage(window)

	price := 100.0
	for i := 0; i < 10_000_000; i++ {
		ma.Update(price + float64(i%7)*0.01)
	}

	// The true sum of what's currently in the buffer:
	trueSum := 0.0
	for _, v := range ma.buf.data {
		trueSum += v
	}

	fmt.Printf("running sum: %.15f\n", ma.sum)
	fmt.Printf("true sum:    %.15f\n", trueSum)
	fmt.Printf("drift:       %.15f\n", ma.sum-trueSum)
}

After ten million updates the two disagree in the lower decimal places. On a price series it's cosmetic. On accumulated P&L it is not, and it's precisely the reason Chapter 2 said to keep money in integers.

The standard fix is to recompute from the buffer periodically:

go
func (m *MovingAverage) Recompute() {
	sum := 0.0
	for _, v := range m.buf.data {
		sum += v
	}
	m.sum = sum
}

Call it every few thousand updates. Cheap, and it caps the drift.

This is the kind of thing you only learn by instrumenting. No tutorial mentions it, and it's real.

Exercises

8.1 Add Values() []float64 to RingBuffer returning the contents in chronological order - oldest first - regardless of where pos currently is. Verify with the print harness above.

8.2 Build RollingMax on a ring buffer, returning the highest value in the window. The simple version scans the buffer each update. What's its complexity, and when would that matter?

8.3 Build RollingStdDev keeping running sums of both values and squared values, so it's O(1) per update. Compare its output against computing the standard deviation directly from Values(), and see how far they diverge after a million updates.

8.4 Benchmark RollingMax against a version that recomputes from scratch. Then run both at windows of 10, 100 and 1000 and tabulate. Which one's cost grows with the window?

8.5 Feed prices.csv from the interlude into a 20-bar and a 50-bar moving average simultaneously, and print every bar where the 20 crosses above the 50. Count them.

8.6 Harder. Implement Wilder's ATR from book one using a ring buffer for true range. True range is the largest of: high - low, abs(high - prevClose), abs(low - prevClose). Watch the first bar, which has no previous close.

Solutions

8.1

go
func (r *RingBuffer) Values() []float64 {
	if !r.filled {
		return append([]float64(nil), r.data[:r.pos]...)
	}
	out := make([]float64, 0, len(r.data))
	out = append(out, r.data[r.pos:]...)
	out = append(out, r.data[:r.pos]...)
	return out
}

When full, the oldest value sits at pos, so read from there to the end, then wrap. The ... spreads a slice into append.

8.2 O(window) per update, so O(n × window) overall - back to the naive shape. It matters for large windows, and there's a clever O(1) solution using a monotonic deque, which is a well-known interview problem and worth looking up once you're comfortable here.

8.3 Keep sum and sumSquares; variance is (sumSq - sum²/n) / (n-1). Fast, and numerically worse than the direct computation - the two diverge measurably, which is the same lesson as the drift demo. For serious work, look up Welford's algorithm.

8.4 RollingMax scales with the window; the scratch version scales with window too. Neither is O(1) - that's the point of the exercise, and the monotonic deque is the fix.

8.5 Around 40-60 crossovers on the generated data, depending on seed. Compare with your Chapter 4 answer: same result, different machinery.

8.6 The first bar has no previous close, so true range is just high - low. Wilder's smoothing is atr = (atr*(n-1) + tr) / n, which is an EMA in disguise and doesn't actually need a ring buffer once seeded - a good thing to notice.