从一个数据量过多的优化说起

Author Avatar
XibHe 4月 18, 2018
  • 在其它设备中阅读本文章

前段时间遇到一个问题,程序中查询患者信息的功能,当患者数据量超过 30000 条时,会出现卡顿,APP 无响应的问题。在处理这个需求时,需要将本地数据库中的全部患者数据查询出来,然后按照从 A - Z 的患者首字母进行分组排序。对于不属于 A - Z 的数据,将其分为 # 组。

更新说明

更新记录:

  • 2018 年 04 月,第一版。
  • 2018 年 06 月,补充后续的优化方案。

卡顿问题的解决

原来的代码逻辑如下:

// 全部患者数据
_allPatients = [[LZDatabaseHelper sharedInstance] getAllPatient];
NSMutableArray *tempArray = _allPatients.mutableCopy;
    for (char a = 'A'; a <='Z'; a ++) {
        LZPatientListSectionModel *sectionModel = [[LZPatientListSectionModel alloc] init];
        sectionModel.sectionTitle = [NSString stringWithFormat:@"%c",a];
        for (int i = 0; i < _allPatients.count; i++) {
            PationMoedl *pationModel = _allPatients[i];
            if (pationModel.userShortName.length > 0) {
                char temp = [pationModel.userShortName characterAtIndex:0];
                if (a == temp) {
                    [sectionModel.patientList addObject:pationModel];
                    [tempArray removeObject:pationModel];
                }
            }
        }
        if (sectionModel.patientList.count >0) {
            [self.patientArray addObject:sectionModel];
        }
    }
    LZPatientListSectionModel *sectionModel = [[LZPatientListSectionModel alloc] init];
    sectionModel.sectionTitle = @"#";
    if (tempArray.count > 0) {
        [sectionModel.patientList addObjectsFromArray:tempArray];
        [self.patientArray insertObject:sectionModel atIndex:0];
    }
    [_patientTableView reloadData];

从上面的代码可以计算出排序的时间复杂度,第一个 for 循环执行 26 次,嵌套在内的第二个 for 循环会执行 30000 次。时间复杂度用大写字母 O 来表示,因此该排序的时间复杂度是:

O(26 * 30000)

也就是说当点击对应的按钮查看患者后,会执行 780000for 去遍历全部患者,并将符合首字母符合 A - Z 的患者添加到 sectionModel.patientList 数组中,然后刷新列表展示排好序的数据。这也是为什么会出现患者量少时没有问题,一但患者量达到上万条时就会出现点击对应按钮后,就会出现卡顿的问题。要解决这样的问题,需要从如何降低时间复杂度着手。

尝试了 4 种不同的方案,如下:

方案一:

算法角度上,以空间换时间,一下子就创建好 26 个存放 A - Z 首字母排序的数组,以减少循环次数为目的,循环一次,找到对应首字母序列的数据,从数据源中移除这些数据;然后,继续开始下一次遍历,以此类推,直到查询出所有排序数组。(时间复杂度,空间复杂度)

  • 桶排序算法

  • 快速排序算法

方案二:

几种不同遍历方式的比较,试图通过比较查询效率,找到最快的遍历方式。

  • 经典 for 循环
  • for in (NSFastEnumeration)
  • KVC 集合运算符
  • enumerateObjectsUsingBlock
  • enumerateObjectsWithOptions(NSEnumerationConcurrent)

初始化 100 个对象的遍历操作所消耗的时间(毫秒级):

  • 经典for循环 — 0.0023
  • for in (NSFastEnumeration) — 0.003090
  • makeObjectsPerformSelector — 0.001120
  • kvc集合运算符 — 0.004272
  • enumerateObjectsUsingBlock — 0.001145
  • enumerateObjectsWithOptions(NSEnumerationConcurrent) — 0.001605

这样并不能看出什么结论,当初始化 1000000 个对象时就会有很大差距

  • 经典for循环 — 1.246721
  • for in (NSFastEnumeration) — 0.025955
  • makeObjectsPerformSelector — 0.068234
  • kvc集合运算符 — 21.677246
  • enumerateObjectsUsingBlock — 0.586034
  • enumerateObjectsWithOptions(NSEnumerationConcurrent) — 0.722548

可以看出当数据量少时,for in 的速度并不突出,但当数量达到一定量级后,for in 的遍历速度就体现出来了。

方案三:

折中方案,为了避免查询时卡死主线程,将查询方法放在 异步线程 里,然后在 主线程 中刷新数据源。如下:

dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0), ^{

        for (char a = 'A'; a <='Z'; a ++) {
            LZPatientListSectionModel *sectionModel = [[LZPatientListSectionModel alloc] init];
            sectionModel.sectionTitle = [NSString stringWithFormat:@"%c",a];

            for (PationMoedl *pationModel in _allPatients) {
                // 根据数据库中的患者简称,将对应简称的model存入sectionModel.patientList中
                if (pationModel.userShortName.length > 0) {
                    char temp = [pationModel.userShortName characterAtIndex:0];
                    if (a == temp) {
                        [sectionModel.patientList addObject:pationModel];
                        [tempArray removeObject:pationModel];
                    }
                }
            }
            if (sectionModel.patientList.count >0) {
                [self.patientArray addObject:sectionModel];
            }
        }

        LZPatientListSectionModel *sectionModel = [[LZPatientListSectionModel alloc] init];
        sectionModel.sectionTitle = @"#";
        if (tempArray.count > 0) {
            [sectionModel.patientList addObjectsFromArray:tempArray];
            [self.patientArray insertObject:sectionModel atIndex:0];
        }

        dispatch_async(dispatch_get_main_queue(), ^{
            [_patientTableView reloadData];
            [MBProgressHUD hideHUDForView:self];
        });

});

方案四

方案4也是最终采用的方案,主要时间排序的功能用 SQL 语句去实现,在每次遍历时,传入一个当前的序列,通过执行数据库查询语句得到一个分好的序列数组,这样就大大减少了 for 循环的次数,提高了速度。但为了不卡死线程,仍然需要与 GCD 结合起来使用。如下:

[MBProgressHUD showMessag:@"加载中" toView:self];
// 1. 将整个查询的耗时操作放到 GCD 中
dispatch_sync(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
//  查询出所有患者数据,为搜索功能提供数据源
     _allPatients = [[LZDatabaseHelper sharedInstance] getAllPatientForIndexes];
     // 2. 从 A - Z 进行 26 次遍历
    for (char a = 'A'; a <='Z'; a ++) {
        NSString *orderNumber = [NSString stringWithFormat:@"%c",a];
        // 3. 通过 SQL 语句查出对应首字母序列的返回的数组
        NSArray *patientRankArray = [[LZDatabaseHelper sharedInstance] getPatientGroup:orderNumber];
        // 4. 将查询到的某一序列数组与分组名称进行绑定
        if (patientRankArray && patientRankArray.count > 0) {
            LZPatientListSectionModel *sectionModel = [[LZPatientListSectionModel alloc] init];
            sectionModel.sectionTitle = orderNumber;
            [sectionModel.patientList addObjectsFromArray:patientRankArray];
            [self.patientArray addObject:sectionModel];
        }
    }

        // 5. 通过 SQL 语句查出其他非 A-Z 的数据
        NSArray *otherArray = [[LZDatabaseHelper sharedInstance] getPatientMistakeGroup];

        // 6. 将查询到的非 A-Z 插入到患者数据源中
        if (otherArray && otherArray.count > 0) {
            LZPatientListSectionModel *sectionModel = [[LZPatientListSectionModel alloc] init];
            sectionModel.sectionTitle = @"#";
            [sectionModel.patientList addObjectsFromArray:otherArray];
            [self.patientArray insertObject:sectionModel atIndex:0];
        }

        // 7. 主线程中刷新列表
        dispatch_async(dispatch_get_main_queue(), ^{
            [_patientTableView reloadData];
            [MBProgressHUD hideHUDForView:self];
        });

    });

具体步骤如下:

  1. 将整个查询的耗时操作放到 GCD 中;
  2. 从 A - Z 进行 26 次遍历;
  3. 通过 SQL 语句查出对应首字母序列的返回的数组;
  4. 将查询到的某一序列数组与分组名称进行绑定;
  5. 通过 SQL 语句查出其他非 A-Z 的数据;
  6. 将查询到的非 A-Z 插入到患者数据源中;
  7. 主线程中刷新列表。

这里将最为耗时的对应首字母遍历数据操作,通过 SQL 查询语句来实现。那么 SQL 语句的查询速度究竟如何呢?可以在处理 SQL 查询的方法里增加计算方法执行耗时的代码:

// 记录开始时间,放在方法执行的最前面
NSDate *startDate = [NSDate date];

// 记录结束时间,放到方法执行结束的位置
NSDate *finishDate = [NSDate date];
NSTimeInterval interval = [finishDate timeIntervalSinceDate:startDate];
NSLog(@"查询全部患者数据耗时: %f",interval);

返回的时间戳大概为 0.45 毫秒。

关于数据库查询语句的优化

  1. 建立索引
  2. 不要把SQL语句写得太复杂
  3. 避免过度使用 Select * 查询所有数据 (实际使用时只需要某一个或几个字段)
  4. 统一 SQL 语句的写法 (主要区分大小写)
  5. REPLACE INTO 语句的使用
    • REPLACE 作用与 INSERT 完全一致,但如果旧表中的行具有相同的值作为一个新行 PRIMARY KEYUNIQUE 索引,旧行插入新行之前删除。
    • REPLACE 是一个 MySQL 扩展 SQL 标准。它要么插入要么先删除再插入。
    • 注意,除非表有一个 PRIMARY KEYUNIQUE 索引,否则使用 REPLACE 语句是没有意义的。
  6. SQL 语句的拓展

    • sqlite 截取字符串前几位后再进行查询
    • sqlite 中使用 regex 进行查询
    • SUBSTR(),SQL 中的 substring 函数是用来抓出一个栏位资料中的其中一部分。这个函数的名称在不同的数据库中不完全一样:

      MySQL: SUBSTR( ), SUBSTRING( )
      Oracle: SUBSTR( )
      SQL Server: SUBSTRING( )

    • upper()函数,将小写转化为大写;lower()函数,将大写转化为小写。

// 根据 A - Z 进行分组查询
NSString *sql = [NSString stringWithFormat:@"SELECT id, userName, userShortName, birthday, sex, phone, address FROM table_sickPerson WHERE clinicId = '%@' AND status like '0' AND isDelete like '0' AND SUBSTR(upper(userShortName),1,1) = '%@' ",clinkId,orderNumber];
  • GLOB 用来连接正则表达式的关键字
// 查询非 A - Z 的数据
NSString *sql = [NSString stringWithFormat:@"SELECT id, userName, userShortName, birthday, sex, phone, address FROM table_sickPerson WHERE clinicId = '%@' AND status like '0' AND isDelete like '0' AND SUBSTR(upper(userShortName),1,1) GLOB '[^A-Z]' ",clinkId];

之前没有在 SQLite 中使用过 regex 还以为不支持呢,最后几经波折,在官网上找到了对应的文档!

SQLite官网

ONE PIECE

一个关于 CoreData 的问题

Core DataiOS5 之后才出现的一个框架,本质上是对 SQLite 的一个封装,它允许按照实体-属性-值模型组织数据,并以 XML,二进制文件或SQLite 数据文件的格式将其序列化。Core Data 允许用户使用代表实体和实体间关系的高层对象来操作数据。它也可以管理序列化的数据,提供对象生存期管理与 object graph 管理,包括存储。Core Data 直接与 SQLite 交互,避免开发者使用原本的 SQL 语句。

这里在尝试使用 Core Data 时遇到一个问题,在获取模型路径,创建模型对象时,一直报错:

    NSURL *modelURL = [[NSBundle mainBundle] URLForResource:@"testModel" withExtension:@"momd"];
    _managedObjectModel = [[NSManagedObjectModel alloc] initWithContentsOfURL:modelURL];
    return _managedObjectModel;
 *** Terminating app due to uncaught exception 'NSInvalidArgumentException', reason: 'CoreData: Cannot load NSManagedObjectModel.  nil is an illegal URL parameter'

Core Data 数据库的名字和封装类里的名字是一致的。

使用Blob存储NSData遇到的问题

先通过 UPDATE 语句更新数据,

// 更新faceFeatureData
+ (void)updateFaceFeatureData:(NSData *)faceFeatureData
{
    FMDatabase *dataBase = [ConfigurateDB open];
    [dataBase beginTransaction];

    NSString *sql = [NSString stringWithFormat:@"UPDATE Register SET faceFeatureData = '%@' WHERE id = '1'",faceFeatureData];
    [dataBase executeUpdate:sql];

    [dataBase commit];
}

再通过 SELECT 获取更新的值。

// 获取个人信息
+ (AFRPerson *)getInformationWithUserID:(NSInteger)Id
{
    FMDatabase *dataBase = [ConfigurateDB open];
    NSString *sql = [NSString stringWithFormat:@"SELECT * FROM Register WHERE id = '%ld'",Id];
    FMResultSet * resultSet = [dataBase executeQuery:sql];
    AFRPerson *person = nil;
    while ([resultSet next]) {
        person = [[AFRPerson alloc] init];

        person.Id = [resultSet intForColumn:@"id"];
        person.faceID  = [resultSet intForColumn:@"faceID"];
        person.faceFeatureData = [resultSet dataForColumn:@"faceFeatureData"];
        person.name = [resultSet stringForColumn:@"name"];
        person.attendanceStatus = [resultSet stringForColumn:@"attendanceStatus"];
    }

    [resultSet close];

    return person;
}

发现 person.faceFeatureData 这个 NSData 类型的属性值,更新前与更新后再次获取的字节长度不一致,前者为:22020 bytes,后者为:48096 bytes。正常结果二者应是一致的。

小结

  • 第一手资料永远是官方文档!!!
  • 算法真的真的很重要! ! !
  • 很多性能问题,首先可以先从算法角度进行思考;
  • 使用 GCD 多线程技术来处理耗时任务;
  • 算法,不同遍历方式进行比较,SQL查询语句的优化,GCD 这几种方式相结合总能给人意想不到的惊喜,没有一种解决方案是孤立存在的。

对症下药吧!将提高查询效率和减少遍历次数二者相结合。做完这次优化后,还是想问一句:这是最优的方案吗?还可以进一步优化吗?

后记

最后,这种方式虽然可以缓解数据量达到 30000 条时的卡顿状况。但打开列表页面时,仍然会 loading 两三秒, 最终处理方案是:当数据量大于 5000 条时,进行分页加载,一次加载 200 条,此时就没有必要将数据按首字母缩写排序了,可通过搜索框搜索出对应患者;当数据量小于 5000 时,仍保持之前的逻辑。

参考资料

sqlite.org Documentation

w3cschool SQL

13.2.9 REPLACE Syntax

Regex in SQLite and ObjectiveC

Core Data

–EOF–

若无特别说明,本站文章均为原创,转载请保留链接,谢谢