CODEWITHSUNDEEP
arraysswiftdictionaryhashtablememoization
mogelbuster
mogelbuster

Reputation: 1076

Why is Swift Dictionary MUCH Slower than Array during Memoization

I am doing algorithm challenges, and using memoization to speed up repeated recursive calls. The fastest way to memoize is to use a hash table (when the range of values is large, but input is sparse across the range). I have read that Dictionary is swift's hash table. So I implemented my memoization class like this:

fileprivate class MemoizationSlow { //Why is this so much slower?
    private var memDict = Dictionary<Int,Dictionary<Int,Int>>()
    func getResult(forAmount n:Int, numberOfCoins size:Int) -> Int? {
        return memDict[n]?[size];
    }
    func memoize(result:Int, amount n:Int, numberOfCoins size:Int) {
        memDict[n] = [size:result]
    }
}

And what I found is that this is actually SLOWER than brute force!!! I know it is not my algorithm, nor a mistake elsewhere in the code, because I changed my memoization class to this:

fileprivate class Memoization {
    private var memArr:Array<Array<Int?>>
    init(totalAmount:Int, coinsCount:Int) {
        memArr = Array<Array<Int?>>(repeating: Array<Int?>(repeating: nil, count: coinsCount), count: totalAmount+1)
    }
    func getResult(forAmount n:Int, numberOfCoins size:Int) -> Int? {
        return memArr[n][size]
    }
    func memoize(result:Int, amount n:Int, numberOfCoins size:Int) {
        memArr[n][size] = result
    }
}

And the algorithm was lightning fast!! The only problem with the second approach is that it requires more space complexity than a hash table, since not all values in the range are memoized.

My big question is: Why is the Dictionary implementation so much slower than the Array implementation?

Upvotes: 1

Views: 265

Answers (1)

vacawama
vacawama

Reputation: 154613

Part of your problem is that your dictionary implementation wipes out previous values that exist for a given amount n every time you add a new value with that amount. You should be adding the value to the inner dictionary instead of replacing the inner dictionary with a new one containing only the new value.

Try this:

func memoize(result:Int, amount n:Int, numberOfCoins size:Int) {
    // Get inner dictionary or use an empty one if there isn't one yet
    var inner = memDict[n] ?? [:]

    // Add the value to the inner dictionary
    inner[size] = result

    // Replace inner dictionary with the updated one
    memDict[n] = inner
}

Alternatively, you can do it like this:

func memoize(result:Int, amount n:Int, numberOfCoins size:Int) {
    if memDict[n] != nil {
        memDict[n]![size] = result
    } else {
        memDict[n] = [size : result]
    }
}

It is left as an exercise to the reader to figure out which one is faster.

Upvotes: 1

Related Questions