🌚

Kam's Online Notebook

🏠

线性搜索内存数据的业务优化

最近简单优化了下项目内一些数据搜索功能。

背景是用户的关注列表和群聊成员都太多了，项目早期的搜索逻辑完全不顶用。搜索的内容包括三大块：

  1. 最近联系会话；
  2. 关注列表；
  3. 群列表（包括群成员）。

命中的逻辑比较粗暴，目标字符串对搜索词的精准匹配和拼音模糊匹配，具体而言：

  1. 当搜索词的包含中文，这意味着使用精准匹配。比如输入「米」将命中「米饭」；
  2. 当搜索词为非中文时，则对目标字符串「米饭」、每个字符首字母「MF」、所有字符的拼音「MIFAN」进行精准匹配；

命中后需要将对应的字符高亮，比如输入「M」命中「米饭」后，「米」字需要高亮。具体实现算法，网路上已经有很多讨论，这里只聊下比较通用的、充分利用资源的搜索逻辑优化。

缓存中间结果

缓存结果其实很好理解，比如面对如下 4 条数据的时候：

Dinesh Carlos
Earl Fletcher
Dash Marnie
Finbar Alastair

输入「D」可以命中到两条结果：

_D_inesh Carlos
_D_ash Marnie

然后就输入「a」，那么只从刚才到两条结果中继续搜索两次即可，命中：

_Da_sh Marnie

针对顺序输入字符串的情况写了简陋的搜索类实现这个功能 —— CIRSearcher。里面维护缓存的时候呢，没有直接采用数组存储对象的方式，而是使用了 bit array 记录命中索引的结果。比如 2000 个数据，输入第一个字符后命中 1000 个，如果使用 NSArray 存储对象，那么则需要：

  1. 至少 64 bit * 1000 = 64000 bit 的内存空间；
  2. 至少对 1000 个对象发送 retain 消息；

相比较而言，bit array 记录索引：

  1. 固定至少 2000 bit 存储；
  2. 不需要 retain 对象，命中的对象只要在 bit array 中的对应 bit 位置 1；

当然这是优势情况下的描述，毕竟 bit array 的空间是固定的，如果结果较少，bit array 反而会占用太多空间。当然这些都是可以根据业务性质去衡量、决策。缓存中间结果也会带来问题：在业务中，通常会在搜索逻辑的执行时，记录高亮字符串，那么当用户回退输入时，直接返回上一次结果的话，那么此时的高亮字符依然是回退前的。解决这个问题，可以把搜索逻辑再执行一次，或者让匹配逻辑自己保存都行。

CPU 使用率是可以超过 100% 的！

大量的数据处理，其实可以通过拆分任务，然后并发执行，最后统一组装结果返回。给 NSArray 加一个扩展：


- (NSArray *)kt_perform:(NSArray *(^)(NSArray *))execute {
    
    NSAssert(execute, @"no execute block");
    
    static NSInteger processorCount = 0;
    if (processorCount == 0) {
        processorCount = [NSProcessInfo processInfo].processorCount;
    }

    NSInteger preset = processorCount / 2 + 1;
    NSInteger numberOfExecution = MIN(self.count, preset);
    
    NSInteger groupCount = self.count / numberOfExecution;
    NSInteger remain = self.count % numberOfExecution;
    NSMutableArray<NSArray *> *resultArrayToReplace = [[NSMutableArray alloc] initWithCapacity:numberOfExecution];
    NSArray *placeholder = [NSArray new];
    for (int i = 0; i < numberOfExecution; i++) {
        [resultArrayToReplace addObject:placeholder];
    }
    
    __block NSInteger totoalResultCount = 0;
    
    dispatch_apply(numberOfExecution, DISPATCH_APPLY_AUTO, ^(size_t i) {
        NSInteger startLoc = i * groupCount;
        NSInteger length = groupCount;
        if (i == (numberOfExecution - 1)) {
            length += remain;
        }
        NSArray *result = execute([self subarrayWithRange:NSMakeRange(startLoc, length)]);
        totoalResultCount += result.count;
        [resultArrayToReplace replaceObjectAtIndex:i withObject:result];
    });
    
    NSMutableArray *finalResult = [[NSMutableArray alloc] initWithCapacity:totoalResultCount];
    [resultArrayToReplace enumerateObjectsUsingBlock:^(NSArray * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        [finalResult addObjectsFromArray:obj];
    }];
    
    return finalResult;
}

上面的代码其实很简单，根据设备的状况，决定将这个数据分成多少子数组，然后用 libdispatch 提供的并发 API 执行 execute block。注意 resultArrayToReplace 采用占位替换的方式存储数据，而不是空数组添加，一个是为了保证顺序，更重要的是保证线程安全，因为 backend storage 不再需要 realloc/free 空间。这点上，前文提到的 bit array 也是一样的，同样是线程安全的。

EOF

— Jul 11, 2021

GitHub