以可变数组为值的Swift字典执行很慢？如何正确优化或构建？

Question

我正在尝试在Swift中构建一个数据结构，将一个整数映射到一个对象数组（一个以int为键、数组为值的字典）。这些对象非常小，它们只包装了一个UIColor和一个Int。我有两个实现，一个使用Swift数组作为字典的值类型，而另一个使用NSMutableArray作为值类型。我的Objective-C代码运行速度非常快，但我的Swift代码运行速度非常慢。理想情况下，我不想使用NSMutableArray，而是希望将其保留为Swift数组。原因是我正在编写一个算法和性能很重要，我注意到objC_msgSend有一些开销。有人能帮我优化我的Swift代码吗？我做错了什么还是这只是swift将数组视为值类型的副产品？如果是，我想了解为什么值类型在这种情况下表现如此缓慢，我的选择是什么，以及这种情况如何扩展？下面我发布了一个代码片段和由此产生的基准测试：

Swift数组代码：

let numColors = colorCount(filter: filter, colorInfoCount: colorInfo.count)
var colorCountsArray: [Int] = [Int]()
var countToColorMap: [Int:[CountedColor]] = [Int:[CountedColor]](minimumCapacity: capacity)
var topColors = [CountedColor]()

var startTime = CACurrentMediaTime()
for (color, colorCount) in colorInfo {
    colorCountsArray.append(colorCount)
    if countToColorMap[colorCount] != nil {
        countToColorMap[colorCount]?.append(CountedColor(color: color, colorCount: colorCount))
    } else {
        countToColorMap[colorCount] = [CountedColor(color: color, colorCount: colorCount)]
    }
}
var endTime = CACurrentMediaTime()
print("Time after mapping: \(endTime - startTime)")

Swift性能：

Time after mapping: 45.0881789259997

NSMutableArray代码：

let numColors = colorCount(filter: filter, colorInfoCount: colorInfo.count)
var colorCountsArray: [Int] = [Int]()
var countToColorMap: [Int:NSMutableArray] = [Int:NSMutableArray](minimumCapacity: capacity)
var topColors = [CountedColor]()


var startTime = CACurrentMediaTime()
for (color, colorCount) in colorInfo {
    colorCountsArray.append(colorCount)
    if countToColorMap[colorCount] != nil {
        countToColorMap[colorCount]?.add(CountedColor(color: color, colorCount: colorCount))
    } else {
        countToColorMap[colorCount] = NSMutableArray(object: CountedColor(color: color, colorCount: colorCount))
    }
}
var endTime = CACurrentMediaTime()
print("Time after mapping: \(endTime - startTime)")

NSMutableArray性能：

Time after mapping: 0.367132211999888

colyInfo对象是将UIColor对象映射到表示计数的整数值的字典。代码本质上是反向映射，将整数映射到UIColor数组（它是一个数组，因为多个颜色可以具有相同的计数）。colyInfo内部有60,000个UIColor、Int键值对。

Answer 1

在swift 4.2出现之前我有一些工作要做

var countToColorMap = [Int: [CountedColor]]()

for (color, colorCount) in colorInfo {
    countToColorMap[colorCount, default: [CountedColor]()].append(CountedColor(color: color as! UIColor, colorCount: colorCount))
}

它速度快，可读性强

Answer 2

写时复制是一件棘手的事情，您需要仔细考虑有多少东西共享您试图修改的结构。罪魁祸首在这里。

countToColorMap[colorCount]?.append(CountedColor(color: color as! UIColor, colorCount: colorCount))

这将生成一个临时值，该值将被修改并放回字典中。由于两个“东西”正在查看相同的底层数据结构（字典和append），因此它强制写入副本。

解决这个问题的秘诀是确保修改时只有一个副本。怎么做？把它从字典中拿出来。替换这个：

if countToColorMap[colorCount] != nil {
    countToColorMap[colorCount]?.append(CountedColor(color: color as! UIColor, colorCount: colorCount))
} else {
    countToColorMap[colorCount] = [CountedColor(color: color as! UIColor, colorCount: colorCount)]
}

其运行时为：

Elapsed Time: 74.2517465990022
53217

有了这个：

var countForColor = countToColorMap.removeValue(forKey: colorCount) ?? []
countForColor.append(CountedColor(color: color as! UIColor, colorCount: colorCount))
countToColorMap[colorCount] = countForColor

其运行时为：

Elapsed Time: 0.370953808000195
53217