为什么 Swift 字典在记忆过程中比数组慢得多

Question

我正在做算法挑战，并使用记忆来加速重复的递归调用。最快的记忆方法是使用散列 table（当值的范围很大，但输入在整个范围内稀疏时）。我读到 Dictionary 是 swift 的散列 table。所以我像这样实现了我的记忆class：

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]
    }
}

我发现这实际上比蛮力还慢！！！我知道这不是我的算法，也不是代码其他地方的错误，因为我将记忆 class 更改为：

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
    }
}

而且算法快如闪电！！第二种方法的唯一问题是它比散列 table 需要更多 space 复杂性，因为并非范围内的所有值都被记忆。

我的大问题是：为什么 Dictionary 实施比 Array 实施慢这么多？

Answer 1

您的部分问题是，每次您添加具有该数量的新值时，您的字典实现都会清除给定数量存在的先前值 n。您应该将值添加到内部字典，而不是用仅包含新值的新字典替换内部字典。

试试这个：

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
}

或者，您可以这样做：

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

留给 reader 作为练习，找出哪个更快。

为什么 Swift 字典在记忆过程中比数组慢得多

Why is Swift Dictionary MUCH Slower than Array during Memoization

arrays

dictionary

hashtable

memoization

swift