NSArray
获取指定 元素 的位置 或者 判断是否存在指定的 元素 的时间复杂度是 O(n)
(包含特定元素时,平均耗时是 O(n/2)
,如果不包含特定元素,耗时是 O(n)
)。
当我们需要频繁进行该操作时,可能会存在较大的性能问题。
该问题背后的原因很简单。官方文档明确指出 NSArray
从第 0
位开始依次判断是否相等,所以判断次数是 n
(n
等于数组长度)
image
image
本文会介绍一个特别的方案,通过将数组转为字典,我们可以将时间复杂度降低到 O(1)
级别。
首先,我们先对 php
的数组进行一些了解
在 php
中,数组提供了一种特殊的用法:关联键的数组。
关联键的数组 非常类似于其它语言的 map 或者 字典
// 普通数组
$cars = array("Volvo", "BMW", "Toyota");
var_dump($cars);
// 关联键的数组
$age = array("Peter" => "35", "Ben" => "37", "Joe" => "43");
var_dump($age);
通过 var_dump
,我们可以发现:普通数组会自动分配 ID 键(ID 键总是从 0 开始)。所以,普通数组可以转为 关联键的数组 的写法
image
通过类似的思想,我们同样可以 将普通的 NSArray 转换为 NSDictionary
下面,我们按照以下规则设计两个转换方法:
键
是数组存储的 元素
该设计方式可以保证后续通过 objectForKey:
判断是否存在指定的 元素值
是 数组的 索引值
该规则保证字典可以恢复为数组// 将数组转为字典
+ (NSDictionary<NSNumber *, id> *)arr2Dic:(NSArray *)arr {
// 注意,如果数组可能存在相同的元素,请将 `NSValue` 切换到自定义类型
NSMutableDictionary *mutableDic = [NSMutableDictionary dictionary];
[arr enumerateObjectsUsingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
mutableDic[[NSValue valueWithPointer:(__bridge const void * _Nullable)(obj)]] = @(idx);
}];
return [mutableDic copy];
}
// 将字典转为数组
+ (NSArray*)dic2Arr:(NSDictionary<NSValue *, NSNumber *> *)dic {
NSInteger length = dic.count;
NSMutableArray *mutableArr = [NSMutableArray arrayWithCapacity:100];
// 先占位
for (int i=0; i<length; i++) {
[mutableArr addObject:[NSNull null]];
}
[dic enumerateKeysAndObjectsUsingBlock:^(NSValue * _Nonnull key, NSNumber * _Nonnull obj, BOOL * _Nonnull stop) {
NSInteger idx = obj.intValue;
mutableArr[idx] = (__bridge id _Nonnull)(key.pointerValue);
}];
return [mutableArr copy];
}
通过数组的 containsObject:
和字典的 objectForKey:
进行性能测试:
+ (void)load {
NSMutableArray *arr = [NSMutableArray array];
// 填充数组
for (int i=0; i<5; i++) {
[arr addObject:[ViewController new]];
}
// targetObj 在数组中间
NSObject *targetObj = [ViewController new];
[arr addObject:targetObj];
// 填充数组
for (int i=0; i<5; i++) {
[arr addObject:[ViewController new]];
}
NSLog(@"方案一:数组的 containsObject: (hash 执行次数根据位置决定)");
if ([arr containsObject:targetObj]) {
NSLog(@"key 存在");
}
NSLog(@"方案二:转为字典 (没有冲突的情况下,只需要 hash 一次)");
NSDictionary *dic = [self arr2Dic:arr];
if ([dic objectForKey:[NSValue valueWithPointer:(__bridge const void * _Nullable)(targetObj)]]) {
NSLog(@"key 存在");
}
NSLog(@"测试是否可以还原数组");
NSArray<NSValue *> *arr2 = [self dic2Arr:dic];
if ([arr isEqual:arr2]) {
NSLog(@"复原成功");
} else {
NSLog(@"复原失败");
}
NSLog(@"结束");
NSLog(@"%@", arr);
NSLog(@"%@", arr2);
}
测试日志:
image
通过测试日志,我们可以发现该方案可以成功将时间复杂度降低到 O(1)
级别