时间戳

首页 > 解决方案 > 如何以高性能的方式将可变数组用作字典值？

swift - 如何以高性能的方式将可变数组用作字典值？

问题描述

有没有办法将可变数组作为 Swift 字典的值而不损失性能？当我四处搜索时，大多数方法似乎建议从字典中获取数组作为 var，添加到它，然后将其设置回字典（示例）。然而，这似乎是非常低效的。

我使用 NSMutableArrays 将这种方法与 Objective-C 和 Swift 进行了基准测试，并且在 1M 条目的情况下，它似乎慢了 180 倍，并且似乎表现出非线性增长，这表明编译器也无法充分优化这一点。

import Foundation
 
let startDate = Date()
var dict = [Int:[Int]]()
for i in 0..<1_000_000 {
    let key = i % 7
    var arr = dict[key] ?? [Int]()
    arr.append(i)
    dict[key] = arr
}
print("Time spent: \(Date().timeIntervalSinceReferenceDate - startDate.timeIntervalSinceReferenceDate)")
 
// $ swiftc MutableDictionary.swift -o MutableDictionarySwift -framework Foundation -O
// $ ./MutableDictionarySwift
// Time spent: 18.316431999206543

目标-C：

#import <Foundation/Foundation.h>
 
int main(int argc, char *argv[]) {
    @autoreleasepool {
        NSDate *startDate = [NSDate date];
        NSMutableDictionary *dict = [NSMutableDictionary new];
        for (int i = 0; i < 1000000; ++i) {
            NSNumber *key = @(i % 7);
            NSMutableArray *arr = dict[key] ?: [NSMutableArray new];
            [arr addObject:@(i)];
            dict[key] = arr;
        }
        NSLog(@"Number of elements: %lu", dict.count);
        NSLog(@"Time spent: %f", [NSDate date].timeIntervalSinceReferenceDate - startDate.timeIntervalSinceReferenceDate);
    }
}
 
// $ clang MutableDictionary.m -o MutableDictionaryObjc -framework Foundation -O3
// $ ./MutableDictionaryObjc
// 2020-11-26 17:41:17.686 MutableDictionaryObjc[12012:775366] Number of elements: 7
// 2020-11-26 17:41:17.686 MutableDictionaryObjc[12012:775366] Time spent: 0.098124

Swift 与 NSMutableArray：

import Foundation
 
let startDate = Date()
var dict = [Int:NSMutableArray]()
for i in 0..<1_000_000 {
    let key = i % 7
    let arr = dict[key] ?? NSMutableArray()
    arr.add(i)
    dict[key] = arr
}
print("Time spent: \(Date().timeIntervalSinceReferenceDate - startDate.timeIntervalSinceReferenceDate)")
 
// $ swiftc MutableDictionary2.swift -o MutableDictionarySwift2 -framework Foundation -O  
// $ ./MutableDictionarySwift2 
// Time spent: 0.10528397560119629

标签： swift

解决方案

请注意，Swift 数组和NSMutableArray引擎盖下都做了同样的事情：当它们没有更多空间用于新项目时，它们会分配一个新缓冲区。新的缓冲区分配逻辑在 Swift 和 Objective-C 中应该非常相似。

正如 Alexander 在他的评论中指出的那样，您的 Swift 数组代码的问题在于您创建了存储到字典中的数组的本地副本。一旦你改变了本地数组，写时复制机制就会触发数组缓冲区的副本，这会导致另一个堆分配。数组越大，复制缓冲区所需的时间就越多。

您看到的非线性增长是由于数组缓冲区的增加并不经常发生，因为数组实现对容量增加有很好的启发式，以避免每次添加新元素时分配。然而，由于写时复制导致的缓冲区重复发生在每次迭代中。

如果您对 Swift 数组进行适当的变异，您将获得更好的结果：

for i in 0..<1_000_000 {
    let key = i % 7
    dict[key, default: [Int]()].append(i)
}

通过上述更改，测量和仪器都显示出显着提高的性能，Swift 代码比 Objective-C 代码更快。

推荐阅读