Memoizer for e.g. recursive mathematical functions like fibonacci, factorial, etc, inspired by "Advanced Swift" - WWDC 15

Abstract - Memoizer.md

Memoizer

Memoizer is a struct, that can be used to calculate different recursive functions with repeatingly the same values.

To do that it saves every single calculated result in a Dictionary and can then, if repeatedly called, just take a already calcualted result from the dictionnary instead of recalculating it.

Use cases

Fibonacci numbers, factorial, see MemoizerExamples.swift

Memoizer.swift

struct Memoizer<T : Hashable, U> {
    private(set) var memo = [T:U]()
    private(set) var op: ((T) -> U)!
    
    init(operation: (T, (T) -> U) -> U) {
        self.op = {
            x in
            if let q = self.memo[x] { return q }
            let r = operation(x, self.op)
            self.memo[x] = r
            return r
        }
    }
}
// partially from source: https://developer.apple.com/videos/play/wwdc2014/404/

MemoizerExamples.swift

// max n: 20
let factorialMemoizer = Memoizer<Int, Int>(operation: { n, op in return n <= 1 ? 1 : op(n - 1) * n })
// max n: > 100
let factorialMemoizerDouble = Memoizer<Double, Double>(operation: { n, op in return n <= 1 ? 1 : op(n - 1) * n })

let fibonacciMemoizer = Memoizer<Int, Int>(operation: {
  (n: Int, op: (Int) -> Int) -> Int in
  return (n < 2 ? n : (op(n - 1) + op(n - 2)))
})

let fibonacciMemoizerDouble = Memoizer<Double, Double>(operation: {
  (n: Double, op: (Double) -> Double) -> Double in
  return (n < 2 ? n : (op(n - 1) + op(n - 2)))
})

MemoizerTest.swift

let fibonacci = memoize {
    (n: Int, fibonacci: (Int) -> Int) -> Int in
    return n < 2 ? n : (fibonacci(n - 1) + fibonacci(n - 2))
}

let t1 = measure {
    let f1 = Double(fibonacci(4))
    let f2 = Double(fibonacci(5))
    print(f1 / f2)
    }.time

let fibonacciMemoizer = Memoizer<Int, Int>(operation: {
    (n: Int, op: (Int) -> Int) -> Int in
    return (n < 2 ? n : (op(n - 1) + op(n - 2)))
})

let t2 = measure {
    let f1 = Double(fibonacciMemoizer.op(91))
    let f2 = Double(fibonacciMemoizer.op(92))
    print(f1 / f2)
    }.time

let fibonacciMemoizerDouble = Memoizer<Double, Double>(operation: {
    (n: Double, op: (Double) -> Double) -> Double in
    return (n < 2 ? n : (op(n - 1) + op(n - 2)))
})

let t3 = measure {
    let f1 = fibonacciMemoizerDouble.op(130)
    let f2 = fibonacciMemoizerDouble.op(131)
    print(f1 / f2)
    }.time

print(t1, t2, t3)

/*
example output:

0.6
0.618033988749895
0.618033988749895
0.0023500919342041 0.000549077987670898 0.000695943832397461
*/

func measure<U>(_ block: () throws -> U) rethrows -> (result: U, time: Double) {
    var start : NSDate = NSDate()
    var end   : NSDate = NSDate()
    var res   : U
    start = NSDate()
    res = try block()
    end = NSDate()
    return (result: res, time: end.timeIntervalSince1970 - start.timeIntervalSince1970)
}

doesn't seem to work with newest Swift toolchain snapshot (2016-06-06-a)
I get the error that was introduced here: swiftlang/swift@8f955dc
tried to fix it using @NoEscape for op and in the initializer, then it compiles but crashes when first using self.whatEver at runtime.