Efficiency and memoization

Lesson 8’s fib(20) made 21,891 calls to compute one number, and each step up in n makes that worse. A correct program that takes a year to answer is not much use. This lesson is about measuring how much work a program does, and about the most useful trick for doing less.

Counting work

Timing a program depends on the machine, the load, and luck. CS61A measures something steadier: how the number of steps grows with the size of the input. Count the operations, not the seconds.

var comparisons = 0

func hasDuplicates(_ values: [Int]) -> Bool {
    for i in values.indices {
        for j in values.indices where j > i {
            comparisons += 1
            if values[i] == values[j] {
                return true
            }
        }
    }
    return false
}

_ = hasDuplicates(Array(1...100))
print(comparisons)   // 4950

With 100 distinct values, every pair is compared once: 100 × 99 / 2 = 4,950. With 1,000 values it would be 499,500. Multiplying the input by 10 multiplies the work by about 100.

Orders of growth

The order of growth describes that relationship while ignoring constant factors. The common ones, from best to worst:

var steps = 0
var k = 1024
while k > 1 {
    k /= 2
    steps += 1
}
print(steps)

Memoization

Tree-recursive fib is exponential because it recomputes the same values over and over; fib(2) alone is computed thousands of times for fib(20). Memoization remembers each result the first time it is computed, in a dictionary, and looks it up after that:

var calls = 0
var memo: [Int: Int] = [:]

func fib(_ n: Int) -> Int {
    calls += 1
    if let known = memo[n] {
        return known
    }
    let result = n < 2 ? n : fib(n - 2) + fib(n - 1)
    memo[n] = result
    return result
}

print(fib(90), calls)   // 2880067194370816120 179

Each value from 0 to 90 is computed once; the other calls are instant lookups. The same definition, the same tree-shaped reasoning, and linear work instead of exponential.

var calls = 0
var memo: [Int: Int] = [:]
func fib(_ n: Int) -> Int {
    calls += 1
    if let known = memo[n] {
        return known
    }
    let result = n < 2 ? n : fib(n - 2) + fib(n - 1)
    memo[n] = result
    return result
}
_ = fib(10)
print(calls)

Global variables for the memo are fine in a lab, but a memo is better kept private. A nested function can use a dictionary from its enclosing function, as Lesson 5 showed, so each top-level call gets a fresh, hidden memo; the lab does it that way.

Fast exponentiation

Computing bⁿ by multiplying b together n times is linear. Squaring does better: b¹⁰ is (b⁵)², so half the problem answers the whole thing.

func power(_ base: Int, _ n: Int) -> Int {
    if n == 0 {
        return 1
    }
    if n % 2 == 0 {
        let half = power(base, n / 2)
        return half * half
    }
    return base * power(base, n - 1)
}
print(power(2, 10))

Even exponents halve; odd ones take one step to become even. Either way, at most two calls halve n, so the work is logarithmic: 2⁶² takes 11 calls instead of 62 multiplications.

var calls = 0
func power(_ base: Int, _ n: Int) -> Int {
    calls += 1
    if n == 0 {
        return 1
    }
    if n % 2 == 0 {
        let half = power(base, n / 2)
        return half * half
    }
    return base * power(base, n - 1)
}
print(power(2, 10), calls)

Choosing the data structure

The same question can have very different costs depending on where the data lives. contains on an array checks elements one by one, which is linear. On a Set or a dictionary’s keys it takes about the same time regardless of size, because the value’s hash says where to look. Replacing the pairwise loop at the top of this lesson with a set makes it linear:

func hasDuplicates(_ values: [Int]) -> Bool {
    var seen: Set<Int> = []
    for value in values {
        if seen.contains(value) {
            return true
        }
        seen.insert(value)
    }
    return false
}

print(hasDuplicates([3, 1, 4, 1]), hasDuplicates(Array(1...100_000)))   // true false

Lab 17: Efficiency

Q1: Faster partitions

Lesson 8’s countPartitions(100, 100) takes a very long time. Memoize it with a dictionary kept inside the function, keyed by the pair of arguments. An array [n, m] is Hashable, so it can be a key.

func countPartitions(_ n: Int, _ m: Int) -> Int {
    // your code here
}

func countPartitions(_ n: Int, _ m: Int) -> Int {
    var memo: [[Int]: Int] = [:]

    func count(_ n: Int, _ m: Int) -> Int {
        if n == 0 {
            return 1
        } else if n < 0 || m == 0 {
            return 0
        }
        if let known = memo[[n, m]] {
            return known
        }
        let result = count(n - m, m) + count(n, m - 1)
        memo[[n, m]] = result
        return result
    }

    return count(n, m)
}

assert(countPartitions(6, 4) == 9)
assert(countPartitions(100, 100) == 190_569_292)

Q2: Orders of growth

Give the order of growth of each function in terms of n.

func a(_ n: Int) -> Int {
    var total = 0
    for i in 1...n {
        for _ in i...n {
            total += 1
        }
    }
    return total
}

func b(_ n: Int) -> Int {
    var k = n
    var steps = 0
    while k > 0 {
        k /= 3
        steps += 1
    }
    return steps
}

func c(_ n: Int) -> Int {
    n <= 1 ? 1 : c(n - 1) + c(n - 1)
}

assert(a(8) == 36)
assert(b(27) == 4)
assert(c(10) == 512)

Q3: Two numbers that sum to a target

Write hasPairSum(_:target:), which returns true if two different elements of the array add up to target. Make it linear using a set.

func hasPairSum(_ values: [Int], target: Int) -> Bool {
    // your code here
}

func hasPairSum(_ values: [Int], target: Int) -> Bool {
    var seen: Set<Int> = []
    for value in values {
        if seen.contains(target - value) {
            return true
        }
        seen.insert(value)
    }
    return false
}

assert(hasPairSum([3, 9, 5, 1], target: 10))    // 9 + 1
assert(!hasPairSum([3, 9, 5, 1], target: 7))
assert(!hasPairSum([5], target: 10))            // needs two different elements
assert(hasPairSum([5, 5], target: 10))

What’s next

That ends Unit 2. Unit 3 starts with algebraic data types and pattern matching, the Swift counterpart of CS61A’s functional programming weeks.