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

Question

我正在尝试在 Swift 中构建一个数据结构，将一个整数映射到一个对象数组（一个以 int 作为键，以数组作为值的字典）。这些对象非常小，它们只是包装了一个 UIColor 和一个 Int。我有两个实现，一个使用 Swift 数组作为 Dictionary 的值类型，而另一个使用 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

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

Answer 1

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

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

这正在生成一个临时值，该值被修改并放回字典中。由于两个 "things" 正在查看相同的底层数据结构（字典和 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

Answer 2

在 swift 4.2 出现之前我有一些解决方法

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

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

速度快且可读

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

Dictionary in Swift with Mutable Array as value is performing very slow? How to optimize or construct properly?

algorithm

value-type

nsmutablearray

swift

swift-dictionary