时间：   |   阅读： 1012 字 ~3分钟

前言

NSArray 获取指定 元素 的位置 或者 判断是否存在指定的 元素 的时间复杂度是 O(n/2)(如果不包含，耗时是 O(n))。

当我们需要频繁进行该操作时，可能会存在较大的性能问题。

该问题背后的原因很简单：官方文档明确指出 NSArray 从第 0 位开始依次判断是否相等，所以平均的判断次数是 n/2 （n 等于数组长度）

image

image

本文会介绍一个特别的方案：通过将数组转为字典，我们可以将时间复杂度降低到 O(1) 级别。

php 中的数组

首先，我们先对 php 的数组进行一些了解

在 php 中，数组提供了一种特殊的用法：关联键的数组。

关联键的数组 非常类似于其它语言的 map 或者 字典

1
2
3
4
5
6
7

// 普通数组
$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

将普通的 NSArray 转换为 NSDictionary

下面，我们按照以下规则设计两个转换方法：

  1. 字典的 键 是数组存储的 元素

    该设计方式可以保证后续通过 objectForKey: 判断是否存在指定的 元素

  2. 字典的 值 是 数组的 索引值

    该规则保证字典可以恢复为数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 将数组转为字典
+ (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: 进行性能测试：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

+ (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) 级别

0%