Part I

Chapter 4

Doing It Again

The problem

You have 5,000 daily closing prices. You want the average. You are not going to type 5,000 additions.

Go has one loop

Most languages have for, while, do-while, foreach. Go has for. It just wears different hats.

The counting loop

for i := 0; i < 5; i++ {
	fmt.Println(i)          // 0 1 2 3 4
}

Three parts, separated by semicolons:

i := 0 - run once, before anything
i < 5 - checked before each pass; when false, the loop ends
i++ - run after each pass (i++ means i = i + 1)

Loops count from 0. This is universal in programming and it trips up everyone at first. Five items are numbered 0, 1, 2, 3, 4. The condition is i < 5, not i <= 5. Writing <= gives you six passes and, once we get to slices in Chapter 7, a crash.

The while-style loop

Drop the first and third parts:

balance := 1000.0
years := 0

for balance < 2000.0 {
	balance = balance * 1.07
	years++
}

fmt.Printf("Doubled after %d years\n", years)

Go doesn't have a while keyword - for with just a condition is while.

The forever loop

Drop everything:

for {
	// runs until something breaks out
}

You'll use this in Part IV for a program that processes live prices until told to stop.

range: looping over a collection

The one you'll use most:

prices := []float64{67410.50, 67520.00, 67380.25, 67610.75}

for i, price := range prices {
	fmt.Printf("Bar %d: %.2f\n", i, price)
}

range hands you two things each pass: the position and the value. If you don't need the position, use _:

for _, price := range prices {
	fmt.Println(price)
}

_ is the blank identifier - Go's way of saying "give me this and I'll throw it away." You need it because Go refuses to compile if you declare a variable and never use it. That rule sounds fussy and turns out to catch a lot of half-finished edits.

([]float64{...} is a slice - a list of float64s. Chapter 7 is entirely about them. For now: it's a list, and range walks it.)

Building an average

package main

import "fmt"

func main() {
	prices := []float64{67410.50, 67520.00, 67380.25, 67610.75, 67290.00}

	sum := 0.0
	for _, price := range prices {
		sum = sum + price
	}
	average := sum / float64(len(prices))

	fmt.Printf("Sum:     %.2f\n", sum)
	fmt.Printf("Count:   %d\n", len(prices))
	fmt.Printf("Average: %.2f\n", average)
}

Two things worth noticing.

The accumulator pattern. Start a variable at zero outside the loop, add to it inside. This shape - sum := 0.0, loop, sum += x - appears constantly. (sum += price is shorthand for sum = sum + price.)

`float64(len(prices))`. len returns an int, and dividing a float by an int doesn't compile. Chapter 1's conversion rule, doing real work again.

break and continue

break leaves the loop immediately:

for i, price := range prices {
	if price < stopLoss {
		fmt.Printf("Stopped out at bar %d\n", i)
		break
	}
}

continue skips to the next pass:

for _, price := range prices {
	if price == 0 {
		continue        // skip bad data
	}
	sum += price
}

Nested loops, and why they're expensive

A loop inside a loop:

for i := 0; i < 3; i++ {
	for j := 0; j < 3; j++ {
		fmt.Printf("%d,%d ", i, j)
	}
	fmt.Println()
}

Nine passes from two loops of three. That multiplication is the whole point, and it's where performance goes to die.

Here's the moving average, written badly:

// Recomputes the sum from scratch for every bar. Don't do this.
func movingAverageSlow(prices []float64, window int) []float64 {
	result := []float64{}
	for i := window - 1; i < len(prices); i++ {
		sum := 0.0
		for j := i - window + 1; j <= i; j++ {
			sum += prices[j]
		}
		result = append(result, sum/float64(window))
	}
	return result
}

For 5,000 prices and a 200-bar window, that's about a million additions. For a 200-bar window on a million prices, it's 200 million.

The insight that fixes it: moving from one bar to the next only changes two values - one price leaves the window, one enters. So keep a running total:

// Keeps a running sum. One addition and one subtraction per bar.
func movingAverageFast(prices []float64, window int) []float64 {
	result := []float64{}

	sum := 0.0
	for i := 0; i < window; i++ {
		sum += prices[i]
	}
	result = append(result, sum/float64(window))

	for i := window; i < len(prices); i++ {
		sum += prices[i]            // new value enters
		sum -= prices[i-window]     // old value leaves
		result = append(result, sum/float64(window))
	}
	return result
}

Same answers. But the slow one does roughly n × window additions and the fast one does roughly n, regardless of window size.

This is the difference between O(n × w) and O(n), and it's your first taste of complexity analysis. You don't need the formal machinery yet - just the instinct: when the work per item grows with the size of the problem, look for what you're recomputing. Chapter 8 builds this into a proper ring buffer.

Run It Yourself

This one measures the difference rather than asserting it. Save as loops.go.

package main

import (
	"fmt"
	"math/rand"
	"time"
)

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

func movingAverageFast(prices []float64, window int) []float64 {
	if window > len(prices) {
		return nil
	}
	result := make([]float64, 0, len(prices)-window+1)

	sum := 0.0
	for i := 0; i < window; i++ {
		sum += prices[i]
	}
	result = append(result, sum/float64(window))

	for i := window; i < len(prices); i++ {
		sum += prices[i]          // new value enters
		sum -= prices[i-window]   // old value leaves
		result = append(result, sum/float64(window))
	}
	return result
}

func randomWalk(n int, seed int64) []float64 {
	rng := rand.New(rand.NewSource(seed))
	prices := make([]float64, n)
	price := 100.0
	for i := range prices {
		price *= 1 + rng.NormFloat64()*0.01
		prices[i] = price
	}
	return prices
}

func main() {
	fmt.Println("=== 1. equity curve walk: running max and drawdown ===")
	small := []float64{100, 105, 103, 110, 95, 98, 115}
	runningMax, maxDD := small[0], 0.0

	fmt.Printf("%-8s %-12s %-12s\n", "price", "max so far", "drawdown")
	for _, p := range small {
		if p > runningMax {
			runningMax = p
		}
		dd := (runningMax - p) / runningMax
		if dd > maxDD {
			maxDD = dd
		}
		fmt.Printf("%-8.0f %-12.0f %-12.2f%%\n", p, runningMax, dd*100)
	}
	fmt.Printf("worst drawdown: %.2f%%\n", maxDD*100)

	fmt.Println("\n=== 2. same answer, very different cost ===")
	prices := randomWalk(100_000, 42)

	for _, window := range []int{20, 200, 1000} {
		start := time.Now()
		slow := movingAverageSlow(prices, window)
		slowTime := time.Since(start)

		start = time.Now()
		fast := movingAverageFast(prices, window)
		fastTime := time.Since(start)

		// Verify they agree before comparing speed. An "optimisation"
		// that changes the answer is not an optimisation.
		same := len(slow) == len(fast)
		if same {
			for i := range slow {
				if slow[i]-fast[i] > 1e-9 || fast[i]-slow[i] > 1e-9 {
					same = false
					break
				}
			}
		}

		fmt.Printf("window %5d | slow %10v | fast %10v | %6.1fx | match: %t\n",
			window, slowTime.Round(time.Microsecond),
			fastTime.Round(time.Microsecond),
			float64(slowTime)/float64(fastTime), same)
	}
}

Expected shape of the second table:

window    20 | slow    2.1ms | fast   380µs | 5.5x | match: true
window   200 | slow   19.4ms | fast   372µs | 52.2x | match: true
window  1000 | slow   96.8ms | fast   375µs | 258.1x | match: true

Look at the fast column. It barely moves - 380µs, 372µs, 375µs - while the slow column grows by a factor of fifty. That is the entire lesson of this chapter in three numbers: the slow version's cost depends on the window, the fast version's doesn't.

Now break it on purpose.

Push the window to 5000. Does the fast column still hold steady?
Remove the same verification and introduce a deliberate bug in movingAverageFast - subtract prices[i-window+1] instead. Confirm it gets faster and wrong, which is why the check exists.
Change randomWalk to return 1,000,000 prices. Which version can you still wait for?

Exercises

4.1 Given prices := []float64{100, 102, 101, 105, 103, 107}, use a loop to find and print the highest and lowest.

4.2 Count how many days had a higher close than the previous day. (Start at index 1 and compare with i-1.)

4.3 Compute the running maximum - for each bar, the highest price seen so far - and print it alongside the price. This is the first half of a drawdown calculation.

4.4 Extend 4.3 into a full maximum drawdown: for each bar compute (runningMax - price) / runningMax, and print the largest value found.

4.5 Implement both movingAverageSlow and movingAverageFast, verify they produce the same answers on a small input, then time both on 100,000 random prices with a 200-bar window. Use time.Now() before and time.Since(start) after.

4.6 Harder. Write a function that counts how many times a fast moving average crosses above a slow one. A crossover is when fast was at or below slow on the previous bar, and is above on this one. Watch the boundaries - you'll need both averages to exist before you can compare.

Solutions

4.1

highest := prices[0]
lowest := prices[0]
for _, p := range prices {
	if p > highest {
		highest = p
	}
	if p < lowest {
		lowest = p
	}
}

Start from prices[0], not from 0 - starting from 0 breaks the moment prices go negative, which happens in spread and return series.

4.2

up := 0
for i := 1; i < len(prices); i++ {
	if prices[i] > prices[i-1] {
		up++
	}
}

4.3

runningMax := prices[0]
for _, p := range prices {
	if p > runningMax {
		runningMax = p
	}
	fmt.Printf("%.2f  max so far: %.2f\n", p, runningMax)
}

4.4

runningMax := prices[0]
maxDD := 0.0
for _, p := range prices {
	if p > runningMax {
		runningMax = p
	}
	dd := (runningMax - p) / runningMax
	if dd > maxDD {
		maxDD = dd
	}
}
fmt.Printf("Max drawdown: %.2f%%\n", maxDD*100)

4.5 The fast version should be dramatically quicker - often 50-100× at a 200-bar window. Verify the outputs match first: an optimisation that changes the answer isn't an optimisation.

4.6

func countCrossovers(fast, slow []float64) int {
	count := 0
	for i := 1; i < len(fast) && i < len(slow); i++ {
		if fast[i-1] <= slow[i-1] && fast[i] > slow[i] {
			count++
		}
	}
	return count
}

Starting at i := 1 is essential - index 0 has no previous bar. And the two slices may differ in length if the averages have different windows, hence checking both.