将判断 NSArray 数组是否包含指定元素的时间复杂度从 O(n) 降为 O(1)

酷酷的哀殿

发布于 2021-04-26 10:35:53

2.2K00

代码可运行

文章被收录于专栏：酷酷的哀殿酷酷的哀殿

运行总次数：0

代码可运行

前言

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

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

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

image

image

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

php 中的数组

首先，我们先对 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

将普通的 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);
}

测试日志：