Why is Swift Dictionary MUCH Slower than Array during Memoization

Question

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?

I observed a similar effect here: https://codereview.stackexchange.com/a/157380/35991. What I *assume* is that it is due to the necessary rehashing of the keys when the dictionary capacity is increased. That can be avoided by creating the dictionary with a minimum capacity: `[Int: Int](minimumCapacity: ...)` — Martin R, May 14 '17 at 20:33
This might also be relevant: http://stackoverflow.com/a/41154903/1187415. — Martin R, May 14 '17 at 20:40
With your dictionary implementation you're also only memoizing *one* given `size` for any particular `n`, as opposed to your nested array memoization, which is memoizing all given sizes for any given `n`. — Hamish, May 14 '17 at 20:40
Why are your top-level dictionary values themselves dictionaries? They seem to ever be assigned dictionaries containing a single key value pair. This adds a level of indirection that could be removed by using a tuple or struct instead. — Alexander, May 14 '17 at 21:53
@MartinR vacawama and Hamish had the big problem, which took it from years to 0.05 seconds for the dictionary implementation. But the array version is still slightly faster at 0.04 seconds, and I think you are right, it is because of the rehashing. — mogelbuster, May 15 '17 at 11:37

vacawama · Accepted Answer · 2017-05-14T23:02:20.323

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.

You are right, thank you. I prefer the nil coalescing version since it reads easier. That mistake was taking years to process, your fix took 0.05 seconds! I suppose I was looking for a one-liner way to access a dictionary within a dictionary, but I guess that just simply isn't possible. — mogelbuster, May 15 '17 at 11:17

Why is Swift Dictionary MUCH Slower than Array during Memoization

1 Answers1