Swift Memoization

CachedClassifier.swift

class CachedClassifier {
    
    private var sumCache = [Int: Int]()
    
    func sumOfFactors(_ number: Int) -> Int {
        if let cachedValue = sumCache[number] {
            return cachedValue
        }
        
        let sum = aliquotSum(factors(number))
        sumCache[number] = sum
        return sum
    }
    
    func isFactor(candidate: Int, number: Int) -> Bool {
        return number % candidate == 0
    }
    
    func factors(_ number: Int) -> Set<Int> {
        guard number > 1 else {
            return Set<Int>(arrayLiteral: 1)
        }
        
        var factors = Set<Int>()
        factors.insert(1)
        factors.insert(number)
        (2..<number).forEach {
            if isFactor(candidate: $0, number: number) {
                factors.insert($0)
            }
        }
        return factors
    }
    
    func aliquotSum(_ factors: Set<Int>) -> Int {
        let sum = factors.reduce(0, +)
        let targetNumber = factors.max() ?? 0
        return sum - targetNumber
    }
    
    func isPerfect(_ number: Int) -> Bool {
        return sumOfFactors(number) == number
    }
}

Classifier.swift

class Classifier {
    static func isFactor(candidate: Int, number: Int) -> Bool {
        return number % candidate == 0
    }
    
    static func factors(_ number: Int) -> Set<Int> {
        guard number > 1 else {
            return Set<Int>(arrayLiteral: 1)
        }
        
        var factors = Set<Int>()
        factors.insert(1)
        factors.insert(number)
        (2..<number).forEach {
            if isFactor(candidate: $0, number: number) {
                factors.insert($0)
            }
        }
        return factors
    }
    
    static func aliquotSum(_ factors: Set<Int>) -> Int {
        let sum = factors.reduce(0, +)
        let targetNumber = factors.max() ?? 0
        return sum - targetNumber
    }
    
    static func isPerfect(_ number: Int) -> Bool {
        return aliquotSum(factors(number)) == number
    }
}

memoize.swift

func memoize<T: Hashable, U>(_ function: @escaping (T) -> U) -> (T) -> U {
    var cache = [T: U]()
    
    func memoizedFunction(x: T) -> U {
        if let cachedValue = cache[x] {
            return cachedValue
        }
        
        let value = function(x)
        cache[x] = value
        return value
    }
    
    return memoizedFunction
}

let memoizedClassfier = memoize(Classifier.isPerfect)

processTime.swift

// http://kka7.tistory.com/67

func processTime(blockFunction: () -> Void) {
    let startTime = CFAbsoluteTimeGetCurrent()
    blockFunction()
    let processTime = CFAbsoluteTimeGetCurrent() - startTime
    print("수행 시간 = \(processTime)")
}

test.swift

let cachedClassifier = CachedClassifier()
let memoizedClassfier = memoize(Classifier.isPerfect)

print("최적화하지 않은 예")
processTime {
    (0...999).forEach {
        _ = Classifier.isPerfect($0)
    }
}

print("최적화하지 않은 예(두 번째 실행)")
processTime {
    (0...999).forEach {
        _ = Classifier.isPerfect($0)
    }
}

print("합을 캐시한 예")
processTime {
    (0...999).forEach {
        _ = cachedClassifier.isPerfect($0)
    }
}

print("합을 캐시한 예(두 번째 실행)")
processTime {
    (0...999).forEach {
        _ = cachedClassifier.isPerfect($0)
    }
}

print("부분적 메모이제이션")
processTime {
    (0...999).forEach {
        _ = memoizedClassfier($0)
    }
}

print("부분적 메모이제이션(두 번째 실행)")
processTime {
    (0...999).forEach {
        _ = memoizedClassfier($0)
    }
}

WWDCMemoize.swift

func memoize<T: Hashable, U>(_ body: @escaping ((T) -> U, T) -> U) -> (T) -> U {
    var memo = [T: U]()
    var result: ((T) -> U)!
    result = { x in
        if let q = memo[x] { return q }
        let r = body(result, x)
        memo[x] = r
        return r
    }
    return result
}

let factorial = memoize { factorial, x in x == 0 ? 1 : x * factorial(x - 1) }