[iOS] Masonry 算法之最近公共父视图

客户端经常被吐槽是堆页面的, 不用处理复杂逻辑, 就只需要展示就可以, 没什么难度. 今天在某个群里还听到有人吐槽公司是按照每个人写了多少页面来进行考核 😭 , 过于真实.
很多人做了两三年 iOS 后就会发现, 写页面翻来覆去的没啥意思, 最开始我也有这种想法, 后面幡然醒悟, 自己轮子都不会造, 有啥好抱怨的.
最近闲来无事, 学了会算法, 同时也看些源码, 巩固经验值, 加点蓝. 然后发现常用的 Masonry 中有一个算法和二叉树最近公共祖先很像.
下面是 Masonry 的 mas_closestCommonSuperview 方法, 作用是查找两个视图的最近公共父视图.

- (instancetype)mas_closestCommonSuperview:(MAS_VIEW *)view {
    MAS_VIEW *closestCommonSuperview = nil;

    MAS_VIEW *secondViewSuperview = view;
    while (!closestCommonSuperview && secondViewSuperview) {
        MAS_VIEW *firstViewSuperview = self;
        while (!closestCommonSuperview && firstViewSuperview) {
            if (secondViewSuperview == firstViewSuperview) {
                closestCommonSuperview = secondViewSuperview;
            }
            firstViewSuperview = firstViewSuperview.superview;
        }
        secondViewSuperview = secondViewSuperview.superview;
    }
    return closestCommonSuperview;
}

它的作用是用来查找布局子视图的最近公共子视图, 这样才能进行有效的约束计算. 它是用在做类似流式布局 FlexBox, 同时布局多个子视图在一个容器中的. 非常高效. iOS中有 UIStackView

- (MAS_VIEW *)mas_commonSuperviewOfViews
{
    MAS_VIEW *commonSuperview = nil;
    MAS_VIEW *previousView = nil;
    for (id object in self) {
        if ([object isKindOfClass:[MAS_VIEW class]]) {
            MAS_VIEW *view = (MAS_VIEW *)object;
            if (previousView) {
                commonSuperview = [view mas_closestCommonSuperview:commonSuperview];
            } else {
                commonSuperview = view;
            }
            previousView = view;
        }
    }
    NSAssert(commonSuperview, @"Can't constrain views that do not share a common superview. Make sure that all the views in this array have been added into the same view hierarchy.");
    return commonSuperview;
}

好啦不说废话了, 还是看 mas_closestCommonSuperview 方法, 它采用的是两个 while 循环嵌套迭代来查询最近的公共父视图, 这种是类似两个 for 循环嵌套, 也就是时间复杂度 O(n²) . 复杂度确实是高了不少.

那优化方式呢
利用空间换时间的思想, 先将视图1的所有父视图保存到集合中, 然后再迭代视图2的父视图,判断是否存在集合中.

父指针迭代法

typedef UIView MNJ_View;

- (MNJ_View *)mnj_closestCommonSuperView:(MNJ_View *)view {
    MNJ_View *closestCommonSuperview = nil;
    NSMutableSet *cacheViews = [NSMutableSet set];
    MNJ_View *secondViewSuperview = view;
    while (secondViewSuperview) {
        [cacheViews addObject:secondViewSuperview];
        secondViewSuperview = secondViewSuperview.superview;
    }
    MNJ_View *firstViewSuperview = self;
    while (!closestCommonSuperview && firstViewSuperview) {
        if ([cacheViews containsObject:firstViewSuperview]) {
            closestCommonSuperview = firstViewSuperview;
        }
        firstViewSuperview = firstViewSuperview.superview;
    }
    return closestCommonSuperview;
}

写个测试用例


- (void)viewDidLoad {
    [super viewDidLoad];
    UIView *level1_0 = [self creatView];
    UIView *level2_0 = [self creatView];
    UIView *level2_1 = [self creatView];

    UIView *level3_0 = [self creatView];
    UIView *level3_1 = [self creatView];

    UIView *level3_2 = [self creatView];
    UIView *level3_3 = [self creatView];
    
    [level1_0 addSubview:level2_0];
    [level1_0 addSubview:level2_1];

    [level2_0 addSubview:level3_0];
    [level2_0 addSubview:level3_1];
    
    [level2_1 addSubview:level3_2];
    [level2_1 addSubview:level3_3];
    
    MNJ_View *closestCommonSuperview = [level3_1 mnj_closestCommonSuperView:level3_2];
    NSAssert(closestCommonSuperview == level1_0, @"查找最近公共父视图错误");
    NSLog(@"查找最近公共父视图 closestCommonSuperview: %@ \n 预设答案: %@",closestCommonSuperview,level1_0);
}

- (UIView *)creatView {
    return ( {
        UIView *view = [UIView new];
        view.tag = arc4random_uniform(200);
        int r = arc4random_uniform(255);
        int g = arc4random_uniform(255);
        int b = arc4random_uniform(255);
        view.backgroundColor = [UIColor colorWithRed:r/255.0 green:g/255.0 blue:b/255.0 alpha:1.0];
        view;
    });
}

这是经典 LCA 问题 LeetCode 236. 二叉树的最近公共祖先

解法有

递归
迭代
无父指针迭代
RMQ 常用于频繁查询的场景

算法需要理解内涵还有就是常常练习. 利用碎片化时间, 慢慢补充.