查找两个view最近公共祖先那段逻辑算法复杂度是O(n²)，可以优化

hopestar90 commented 4 years ago

New Issue Checklist

Issue Info

如下代码:

(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; }

上述代码意图为寻找两个View最近的公共父View，时间复杂度是O(n²)，其实可以优化成O(n)。

将两个view作为两个链表的头结点，最顶层的superview作为尾结点，这样问题就转化为寻找两个链表的第一个相交节点的问题，从而变为一个复杂度为O(n)的问题。不知道这么考虑是否是正确的？

Issue Description

⚠️ Replace this with the description of your issue. ⚠️

Jake-Chiu commented 3 years ago

有想法是好的，你可以把你的优化方案写出来，验证一下不就ok了吗

cntrump commented 3 years ago

这样？

- (__kindof MAS_VIEW *)mas_closestCommonSuperview:(MAS_VIEW *)view {
    MAS_VIEW *closestCommonSuperview = self;
    MAS_VIEW *secondViewSuperview = view;

    while (closestCommonSuperview != secondViewSuperview) {
        closestCommonSuperview = closestCommonSuperview == nil ? view : closestCommonSuperview.superview;
        secondViewSuperview = secondViewSuperview == nil ? self : secondViewSuperview.superview;
    }

    return closestCommonSuperview;
}

hopestar90 commented 3 years ago

这么写感觉在某些case会陷入死循环，如果self的superview是nil,view也是nil的情况

cntrump commented 3 years ago

这么写感觉在某些case会陷入死循环，如果self的superview是nil,view也是nil的情况

返回 nil。理论上不会死循环，因为不会形成环。这里有别人做的动画演示。 https://zhuanlan.zhihu.com/p/357611418

hopestar90 commented 3 years ago

我给一个写法~ 但可能没有那么优雅:

MAS_VIEW firstView = self; MAS_VIEW secondView = view; NSInteger firstLength = 0; NSInteger secondLength = 0; while (firstView) { firstLength++; firstView = firstView.superview; } while (secondView) { secondLength++; secondView = secondView.superview; } NSInteger diff = 0; if (firstLength > secondLength) { diff = firstLength - secondLength; firstView = self; secondView = view; } else { diff = secondLength - firstLength; firstView = view; secondView = self; }

while (diff > 0) {
    diff--;
    firstView = firstView.superview;
}
while (firstView && secondView && firstView != secondView) {
    firstView = firstView.superview;
    secondView = secondView.superview;
}
if (firstView != secondView) {
    return nil;
} else {
    return firstView;
}

hopestar90 commented 3 years ago

这样？

- (__kindof MAS_VIEW *)mas_closestCommonSuperview:(MAS_VIEW *)view {
    MAS_VIEW *closestCommonSuperview = self;
    MAS_VIEW *secondViewSuperview = view;

    while (closestCommonSuperview != secondViewSuperview) {
        closestCommonSuperview = closestCommonSuperview == nil ? view : closestCommonSuperview.superview;
        secondViewSuperview = secondViewSuperview == nil ? self : secondViewSuperview.superview;
    }

    return closestCommonSuperview;
}

刚又分析了下看了下这样确实可以返回正确的结果

OPTJoker commented 11 months ago

楼上都搞的太复杂了，只需要几个简单的if-else就可以优化95%的遍历次数。毕竟firstView与secondView，在大多数场景下都是父子关系 or 兄弟关系。

优化代码如下：


#pragma mark - heirachy

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

    // 一般约束关联的两个view要么是父子关系，要么是兄弟关系，碰运气可以大大优化链表遍历的时间
    closestCommonSuperview = [self take_a_chance:view];
    if (closestCommonSuperview)
        return closestCommonSuperview;

    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;
}

/// 碰运气 快速找到common super view
- (MAS_VIEW *)take_a_chance:(MAS_VIEW *)secondView {
    if (!secondView) return nil;
    if (self == secondView) return self;

    if (secondView.superview == self.superview && self.superview) {
        return self.superview; // 兄弟关系
    } else if (self.superview == secondView) {
        return self.superview; // first 是 second 的子view
    } else if (self == secondView.superview) {
        return secondView.superview; // first 是 second 的父view
    }
    return nil;
}

优化结果如下：（某日活百万app启动，到首页不再layout）

优化前：查找公共viev:323次查找父view遍历：1656次

优化后：查找公共view：10次查找父view遍历：84次

cntrump commented 11 months ago

楼上都搞的太复杂了，只需要几个简单的if-else就可以优化95%的遍历次数。毕竟firstView与secondView，在大多数场景下都是父子关系 or 兄弟关系。

优化代码如下：

#pragma mark - heirachy

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

    // 一般约束关联的两个view要么是父子关系，要么是兄弟关系，碰运气可以大大优化链表遍历的时间
    closestCommonSuperview = [self take_a_chance:view];
    if (closestCommonSuperview)
        return closestCommonSuperview;

    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;
}

/// 碰运气 快速找到common super view
- (MAS_VIEW *)take_a_chance:(MAS_VIEW *)secondView {
    if (!secondView) return nil;
    if (self == secondView) return self;

    if (secondView.superview == self.superview && self.superview) {
        return self.superview; // 兄弟关系
    } else if (self.superview == secondView) {
        return self.superview; // first 是 second 的子view
    } else if (self == secondView.superview) {
        return secondView.superview; // first 是 second 的父view
    }
    return nil;
}

优化结果如下：（某日活百万app启动，到首页不再layout）

优化前：查找公共viev:323次查找父view遍历：1656次

优化后：查找公共view：10次查找父view遍历：84次

LGTM，搬走抄到我的 Fork 里

SnapKit / Masonry