前言
- 由于项目更新迭代，原有的分类采用的是层级递增并且跳转选择的模式，样式单一，且不方便用户快速选择定位类别。所以有了更新和改版的需求。采用一个界面展示一二三级目录的方式，既直观也好看，也是各大电商App青睐的方式，如京东，淘宝等App分类模块。
- 由于公司业务比较广，类别目录有上千个，如何能够快速解析数据，构建适用的数据结构并展示，成为前端开发的一个难点，而此次实践着重解决该问题。
业务分析
-
采用一，二，三级目录展示方式呈现界面。（如图）
分类页.jpg
- 后台一次返回所有的分类JSON数据信息，存放在一个数组中。
{
"category": [
{
"cat_id": "11241",
"cat_name": "Earbud Headphones",
"parent_id": "11994",
"level": "3",
"mobile_cat_pic": "http:\/\/uidesign.gearbest.com\/GB\/images\/banner\/others\/ios\/.jpg",
"cat_url": "\/earphones-c_11241\/"
},
{
"cat_id": "11249",
"cat_name": "Car DVR",
"parent_id": "11247",
"level": "2",
"mobile_cat_pic": "http:\/\/uidesign.gearbest.com\/GB\/images\/banner\/others\/ios\/.jpg",
"cat_url": "\/car-dvr-c_11249\/"
},
{
"cat_id": "11578",
"cat_name": "Gifts",
"parent_id": "0", //一级列表默认父目录节点ID 返回 0.
"level": "1",
"mobile_cat_pic": "https:\/\/uidesign.gearbest.com\/GB\/app\/2016\/ios_category\/Gift.png",
"cat_url": "\/gifts-c_11578\/",
},
//...
}
- 请求并解析数据，然后做缓存处理。由于公司分类信息改动频率较低，若有更新，另通过其他接口字段进行判断更新缓存。
JSON数据分析
- 上千个类目信息一并返回。那么数据的数量级若为N, N则为1000，即10^3级别。
- 构建成类似系统目录方式的一个树形结构，又或者称之为一个图，并且图是保证联通的，即目录数据完整。
- 解析数据并转化为我们可用于展示的数据结构的过程，称之为构图的过程。相当于，解析数据的时间复杂度，即为构图的时间复杂度。接下来介绍的是根据特定JSON数据源进行构图的O(N)算法。
选择合适的数据结构作为数据查询和存储
- 为了快速根据父级目录ID获取子目录信息，查询最优便是采用Hash表，即对应OC中的NSMutableDictionary，查询时间复杂度为O(1)。
- key作为该目录节点的分类ID。
- value对应该目录节点下的子目录集合，可用一个NSMutableArray进行存储。
- 默认构建目录根节点为ID == 0
- 全局声明如下：
NSString *_categoryRootKey; //根节点ID
NSMutableDictionary *_categoryMap; //图存储Hash表
构图思路
- 第一种思路 ： 由于数据是一并返回，通过解析框架解析后，每个Model节点记录了当前分类的ID，以及父级分类ID和类目信息。大多数人很容易想到的一种方式便是从上往下进行构图，即从根节点开始，到一级目录，再到二级目录，最后三级目录的方式。那么每次需要查询level对应的所有子目录信息，这个查找过程，每次都是O(N)的查询，再结合构图的外层循环，时间复杂度达到了O(N^2)。对应手机端的处理能力，N为1000的话，数据处理量将是百万级别的。初略时间统计，大概要耗时近1s才能解析成方便展示和查询使用的数据结构。对于App用户而言，显然太慢了。
- 第二种思路：根据第一种思路进行改良，可先对所有的分类信息，根据level进行排序，再依次递归处理，时间复杂度会略微下降，但是仍然不够理想，代码可自行YY。
- 第三种思路: 从下往上构图，由于目录完整，那么任何一个目录节点一定会有对应的父级目录节点。那么遍历分类信息数组，先判断对应的父节点是否已经生成，如果生成了，则将当前的目录节点加到Hash表对应的孩子数组中，若当前父级目录节点还未创建并存在于Hash表中，则生成一个父节点，再将当前的分类节点添加到新创建的父目录节点的子目录数组中。通过这种构建方式，则可以遍历一次分类数组就可完成，时间复杂度为O(N)。代码如下：
- (void)dealCategoryData:(NSArray *)categoryArray {
//防止缓存数据导致显示重复。
[_categoryMap removeAllObjects];
[categoryArray enumerateObjectsUsingBlock:^(GBCategoryModel * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
@autoreleasepool {
/*
* 先扫描获取到的Model 分类数据
* 获取到当前 model的父节点, 判断_categoryMap是否存在对应子节点数组
* 如果_categoryMap中父节点key值不存在，创建一个父节点，key值为model.parentId, value为子节点数组
* 如果父节点存在，那么直接将model的值添加到数组里面。
* 最后，将所有第一层的节点连接到 _categoryRootKey 节点对应的数组中，完成此次数据解析。
*/
if ([_categoryMap objectForKey:obj.parentId]) {
//存在对应的key值
NSMutableArray *childArray = [_categoryMap objectForKey:obj.parentId];
[childArray addObject:obj];
[_categoryMap setObject:childArray forKey:obj.parentId];
} else {
//不存在对应父节点key值
NSMutableArray *newChildArray = [NSMutableArray array];
[newChildArray addObject:obj];
[_categoryMap setObject:newChildArray forKey:obj.parentId];
}
}
}];
//最后遍历一次数组，将对应的节点是否存在子节点进行标记
[categoryArray enumerateObjectsUsingBlock:^(GBCategoryModel * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
if ([_categoryMap objectForKey:obj.catId]) {
NSMutableArray *childArray = [_categoryMap objectForKey:obj.catId];
obj.hasNext = (childArray != nil && childArray.count > 0) ? YES : NO;
}
}];
_categoryRootKey = @"0";
}
UI实现
- 结构上分类顶部搜索栏，左边一级列表模块，右边二三级列表模块。
- 左边实现一个UITableView，右边使用UICollectionView。
- 通过点击UITableView中的cell，回调更新UICollectionView的数据源并显示。
- UICollectionView可实现HearderView展示二级列表信息，cell布局排版显示三级列表信息。
重构心得
- 本次重构该分类模块，通过算法的优化，在App端做到快速解析。自己并不想争论算法数据结构对于前端开发是否有用的问题，更多的对于自己而言只是一种尝试。当然也见过大多数App采用点击第一级分类再进行刷新请求的做法，这些均可根据实际业务场景进行选择，例如京东和淘宝貌似也是采用这种方式，当然服务器得足够快，那么也是完美的。对于服务器优化并不够完善的场景下，也可以采用这种将数据解析一步到位，并缓存和展示，或许只是牵强地提升那么一点性能吧。编码本该是种脑力思考的产物，而非体力劳动的成果，仁者见仁，智者见智。
