Abstract - Memoizer.md

(Sparse) Memoizer

Initialization

let fibonacci = memoize { x, op in x < 2 ? x : op(x-1) + op(x-2) }
let fibonacciSparse = sparseMemoize(when: { $0 % 3 != 0 }) { x, op in x < 2 ? x : op(x-1) + op(x-2) }

Use

let fib10 = fibonacci(10)
let fibSparse10 = fibonacciSparse(10)

Tests

Performance Test:

var totalFibTime = 0.0
var totalSpaTime = 0.0

func test(_ count: Int) {
    
    let fibTime = measure {
        for _ in 0..<count {
            let fib = memoize { x, op in x < 2 ? x : op(x-1) + op(x-2) }
            _ = fib(90)
        }
    }
    
    let spaTime = measure {
        for _ in 0..<count {
            let sparseFib = sparseMemoize(when: { ($0 + 1) % 3 != 0 }) { x, op in x < 2 ? x : op(x-1) + op(x-2) }
            _ = sparseFib(90)
        }
    }
    
    totalFibTime += fibTime
    totalSpaTime += spaTime
    
    print("Regular:", fibTime, "\tSparse:", spaTime, "\tRatio (regular/sparse):", fibTime / spaTime)
}

func measure(_ f: () -> ()) -> Double {
    let start = Date()
    f()
    return -start.timeIntervalSinceNow
}

for _ in 0..<10 {
    test(50_000)
}

print("TOTAL - Regular:", totalFibTime, "- Sparse:", totalSpaTime)

results in

Regular: 1.18163102865219 	Sparse: 1.44286596775055 	Ratio (regular/sparse): 0.818947189179583
Regular: 1.19898700714111 	Sparse: 1.45090401172638 	Ratio (regular/sparse): 0.826372384010767
Regular: 1.15271997451782 	Sparse: 1.42640602588654 	Ratio (regular/sparse): 0.808128929349823
Regular: 1.12670803070068 	Sparse: 1.40854495763779 	Ratio (regular/sparse): 0.799909171937429
Regular: 1.1258339881897 	Sparse: 1.40661597251892 	Ratio (regular/sparse): 0.800384760435779
Regular: 1.19773703813553 	Sparse: 1.40450495481491 	Ratio (regular/sparse): 0.852782351553448
Regular: 1.13253104686737 	Sparse: 1.40245896577835 	Ratio (regular/sparse): 0.807532394531648
Regular: 1.15904998779297 	Sparse: 1.43797796964645 	Ratio (regular/sparse): 0.806027638989446
Regular: 1.15362799167633 	Sparse: 1.41204297542572 	Ratio (regular/sparse): 0.816992125419214
Regular: 1.1202210187912 	Sparse: 1.40167397260666 	Ratio (regular/sparse): 0.799202268633091
TOTAL - Regular: 11.5490471124649 - Sparse: 14.1939957737923

Memoizer.swift

protocol MemoizerProtocol {
    associatedtype T: Hashable
    associatedtype U
    func run(_:T) -> U
}

class Memoizer<T : Hashable, U>: MemoizerProtocol {
    private(set) var memo = [T:U]()
    private      var op: ((T) -> U)!
    
    init(_ operation: @escaping (T, (T) -> U) -> U) {
        self.op = { [unowned self]
            x in
            if let q = self.memo[x] { return q }
            let r = operation(x, self.op)
            self.memo[x] = r
            return r
        }
    }
    
    func run(_ input: T) -> U {
        return self.op(input)
    }
}

class SparseMemoizer<Input: Hashable, Output>: MemoizerProtocol {
    
    // MARK: Stored Properties
    
    private(set) var cache = [T:U]()
    private      var operation: ((T) -> U)!
    
    // MARK: Initialization
    
    init(when shouldBeCached: @escaping (Input) -> Bool, operation: @escaping (Input, (Input) -> Output) -> Output) {
        self.operation = { [unowned self] input in
            if let cached = self.cache[input] { return cached }
            let output = operation(input, self.operation)
            if shouldBeCached(input) { self.cache[input] = output }
            return output
        }
    }
    
    // MARK: Methods
    
    func run(_ input: Input) -> Output {
        operation(input)
    }
    
}

func memoize<Input: Hashable, Output>(operation: @escaping (Input, (Input) -> Output) -> Output) -> (Input) -> Output {
    Memoizer<Input, Output>(operation).run
}

func sparseMemoize<Input: Hashable, Output>(when: @escaping (Input) -> Bool, operation: @escaping (Input, (Input) -> Output) -> Output) -> (Input) -> Output {
    SparseMemoizer<Input, Output>(when: when, operation: operation).run
}