Intrinsics（固有尺寸）计算：O(N^2) 性能陷阱与 `computeMinIntrinsicWidth` 的正确实现 - 智猿学院-前后端，数据库，人工智能，云计算等领域前沿技术讲座

Intrinsic Size 计算：O(N^2) 性能陷阱与 `computeMinIntrinsicWidth` 的正确实现

大家好！今天我们要深入探讨一个在自定义 UI 组件开发中经常遇到的问题：intrinsic size（固有尺寸）的计算。特别是 computeMinIntrinsicWidth 方法，它看似简单，但如果实现不当，很容易陷入 O(N^2) 的性能陷阱，导致 UI 渲染效率低下。我们将分析这种陷阱的原因，并提供几种优化方案，确保你的自定义组件在各种场景下都能流畅运行。

什么是 Intrinsic Size？

在 UI 布局系统中，intrinsic size 指的是组件在不受到外部约束的情况下，自身期望占据的最小或最大尺寸。这些尺寸对于布局引擎（例如 Android 的 ConstraintLayout 或 Flutter 的 Flex）来说至关重要，它们利用这些信息来合理分配屏幕空间。

主要涉及两个概念：

Intrinsic Width (固有宽度): 组件希望占据的宽度。
Intrinsic Height (固有高度): 组件希望占据的高度。

更进一步，Intrinsic Width 又可以分为两种：

Minimum Intrinsic Width (最小固有宽度): 组件在不裁剪内容的前提下，可以接受的最小宽度。
Maximum Intrinsic Width (最大固有宽度): 组件在保证内容完全展示的前提下，可以接受的最大宽度。

同样，Intrinsic Height 也可以分为 Minimum 和 Maximum。

在 Android 中，View 类定义了以下四个方法来获取 intrinsic size：

方法名	描述
`getMeasuredWidth()`	获取组件测量后的宽度。这个值在 `onMeasure()` 方法执行后才有效。
`getMeasuredHeight()`	获取组件测量后的高度。这个值在 `onMeasure()` 方法执行后才有效。
`getMinimumWidth()`	获取组件的最小宽度。通常由 `android:minWidth` 属性或 `setMinimumWidth()` 方法设置。
`getMinimumHeight()`	获取组件的最小高度。通常由 `android:minHeight` 属性或 `setMinimumHeight()` 方法设置。
`computeMinIntrinsicWidth(int height)`	计算组件在给定高度下的最小固有宽度。如果组件的内容可以根据高度进行调整（例如文本自动换行），则这个值会根据高度变化。
`computeMinIntrinsicHeight(int width)`	计算组件在给定宽度下的最小固有高度。如果组件的内容可以根据宽度进行调整，则这个值会根据宽度变化。
`computeMaxIntrinsicWidth(int height)`	计算组件在给定高度下的最大固有宽度。
`computeMaxIntrinsicHeight(int width)`	计算组件在给定宽度下的最大固有高度。

其中，computeMinIntrinsicWidth 和 computeMinIntrinsicHeight 是我们今天关注的重点。它们对于实现自适应布局至关重要。

O(N^2) 性能陷阱

考虑一个自定义的水平布局组件，它包含 N 个子组件。我们希望根据子组件的最小固有宽度来计算整个布局的最小固有宽度。一个常见的错误实现如下：

public class MyHorizontalLayout extends ViewGroup {

    public MyHorizontalLayout(Context context) {
        super(context);
    }

    @Override
    protected void onLayout(boolean changed, int l, int t, int r, int b) {
        // 布局子组件的逻辑，这里省略
    }

    @Override
    protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
        super.onMeasure(widthMeasureSpec, heightMeasureSpec);
        //测量子View
        for (int i = 0; i < getChildCount(); i++) {
            View child = getChildAt(i);
            measureChild(child, widthMeasureSpec, heightMeasureSpec);
        }
    }

    @Override
    public int computeMinIntrinsicWidth(int height) {
        int minWidth = 0;
        for (int i = 0; i < getChildCount(); i++) {
            View child = getChildAt(i);
            // 错误实现：每次都重新计算子组件的最小固有宽度
            minWidth += child.computeMinIntrinsicWidth(height);
        }
        return minWidth;
    }
}

这段代码的问题在于，每次调用 computeMinIntrinsicWidth 时，它都会遍历所有子组件，并调用它们的 computeMinIntrinsicWidth 方法。如果布局嵌套很深，例如 MyHorizontalLayout 内部又包含多个 MyHorizontalLayout，那么计算复杂度就会迅速上升到 O(N^2) 甚至更高。

想象一下，如果一个页面包含 10 个嵌套的 MyHorizontalLayout，每个 Layout 包含 10 个子 View，那么 computeMinIntrinsicWidth 方法将被调用 10 * 10 = 100 次，每次调用都需要遍历 10 个子 View。这会导致大量的重复计算，严重影响性能。

为什么是 O(N^2)？

假设我们有一个深度为 d 的嵌套布局，每一层有 n 个子 View。那么：

最外层布局的 computeMinIntrinsicWidth 需要计算 n 个子 View 的 intrinsic width。
每个子 View 又是一个布局，它的 computeMinIntrinsicWidth 又需要计算 n 个子 View 的 intrinsic width。
以此类推，直到最内层的叶子节点。

因此，总的计算量大约是 n + n*n + n*n*n + ... + n^d，当 d 较大时，这个值接近于 n^d。如果 d 和 n 都比较大，那么性能问题就会非常明显。在实际应用中，布局的嵌套深度通常不会太大，但如果布局结构比较复杂，或者子组件的 computeMinIntrinsicWidth 方法本身就比较耗时，那么 O(N^2) 的复杂度仍然会成为瓶颈。

正确实现 `computeMinIntrinsicWidth`

为了避免 O(N^2) 的性能陷阱，我们需要采取一些优化措施。核心思想是：避免重复计算，尽可能缓存结果。

以下是一些可行的方案：

1. 缓存子组件的 Intrinsic Width

在子组件的尺寸发生变化时，重新计算并缓存其 intrinsic width。这样，在 computeMinIntrinsicWidth 方法中，可以直接从缓存中读取，而不需要每次都重新计算。

public class MyHorizontalLayout extends ViewGroup {

    private final Map<View, Integer> childMinWidthCache = new HashMap<>();

    public MyHorizontalLayout(Context context) {
        super(context);
    }

    @Override
    protected void onLayout(boolean changed, int l, int t, int r, int b) {
        // 布局子组件的逻辑，这里省略
    }

    @Override
    protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
        super.onMeasure(widthMeasureSpec, heightMeasureSpec);
        //测量子View
        for (int i = 0; i < getChildCount(); i++) {
            View child = getChildAt(i);
            measureChild(child, widthMeasureSpec, heightMeasureSpec);
        }
    }

    @Override
    public void addView(View child, int index, ViewGroup.LayoutParams params) {
        super.addView(child, index, params);
        // 监听子组件的尺寸变化
        child.addOnLayoutChangeListener(new OnLayoutChangeListener() {
            @Override
            public void onLayoutChange(View v, int left, int top, int right, int bottom, int oldLeft, int oldTop, int oldRight, int oldBottom) {
                // 尺寸发生变化，重新计算并缓存 intrinsic width
                recalculateChildMinWidth(v);
            }
        });
    }

    private void recalculateChildMinWidth(View child) {
        childMinWidthCache.put(child, child.computeMinIntrinsicWidth(child.getMeasuredHeight()));
    }

    @Override
    public int computeMinIntrinsicWidth(int height) {
        int minWidth = 0;
        for (int i = 0; i < getChildCount(); i++) {
            View child = getChildAt(i);
            // 从缓存中读取 intrinsic width
            Integer cachedWidth = childMinWidthCache.get(child);
            if (cachedWidth == null) {
                // 如果缓存中没有，则重新计算并缓存
                recalculateChildMinWidth(child);
                cachedWidth = childMinWidthCache.get(child);
            }
            minWidth += cachedWidth;
        }
        return minWidth;
    }
}

在这个版本中，我们使用了一个 HashMap 来缓存子组件的最小固有宽度。当子组件的尺寸发生变化时（通过 OnLayoutChangeListener 监听），我们会重新计算并更新缓存。在 computeMinIntrinsicWidth 方法中，我们首先尝试从缓存中读取，如果缓存中没有，则重新计算并缓存。

2. 延迟计算 Intrinsic Width

如果 intrinsic width 的计算比较耗时，可以考虑延迟计算。例如，只在需要的时候才计算，或者使用异步任务来计算。

public class MyHorizontalLayout extends ViewGroup {

    private int minWidth = -1;
    private boolean minWidthDirty = true;

    public MyHorizontalLayout(Context context) {
        super(context);
    }

    @Override
    protected void onLayout(boolean changed, int l, int t, int r, int b) {
        // 布局子组件的逻辑，这里省略
    }

    @Override
    protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
        super.onMeasure(widthMeasureSpec, heightMeasureSpec);
        //测量子View
        for (int i = 0; i < getChildCount(); i++) {
            View child = getChildAt(i);
            measureChild(child, widthMeasureSpec, heightMeasureSpec);
        }
    }

    @Override
    public void requestLayout() {
        super.requestLayout();
        minWidthDirty = true;
    }

    @Override
    public int computeMinIntrinsicWidth(int height) {
        if (minWidthDirty || minWidth == -1) {
            minWidth = calculateMinWidth(height);
            minWidthDirty = false;
        }
        return minWidth;
    }

    private int calculateMinWidth(int height) {
        int calculatedMinWidth = 0;
        for (int i = 0; i < getChildCount(); i++) {
            View child = getChildAt(i);
            calculatedMinWidth += child.computeMinIntrinsicWidth(height);
        }
        return calculatedMinWidth;
    }
}

在这个版本中，我们使用一个 minWidthDirty 标志来表示最小固有宽度是否需要重新计算。只有当 minWidthDirty 为 true 时，才会重新计算最小固有宽度。每次调用 requestLayout 时，都会将 minWidthDirty 设置为 true，表示布局发生了变化，需要重新计算。

3. 优化子组件的 computeMinIntrinsicWidth 实现

除了优化父组件的 computeMinIntrinsicWidth 方法之外，还可以优化子组件的实现。如果子组件的 computeMinIntrinsicWidth 方法本身就比较耗时，那么即使父组件使用了缓存，性能也可能受到影响。

例如，如果子组件是一个文本组件，那么可以使用二分查找等算法来快速计算文本的最小固有宽度。

4. 使用 MeasureSpec 进行优化

在 onMeasure 方法中，我们可以通过 MeasureSpec 来了解父组件对子组件的尺寸限制。如果父组件已经指定了确定的宽度或高度，那么子组件的 computeMinIntrinsicWidth 和 computeMinIntrinsicHeight 方法可能就不需要被调用。

@Override
protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
    int widthMode = MeasureSpec.getMode(widthMeasureSpec);
    int widthSize = MeasureSpec.getSize(widthMeasureSpec);

    if (widthMode == MeasureSpec.EXACTLY) {
        // 父组件已经指定了确定的宽度，不需要计算最小固有宽度
        setMeasuredDimension(widthSize, getDefaultSize(getSuggestedMinimumHeight(), heightMeasureSpec));
    } else {
        // 需要计算最小固有宽度
        int minWidth = computeMinIntrinsicWidth(MeasureSpec.getSize(heightMeasureSpec));
        setMeasuredDimension(resolveSize(minWidth, widthMeasureSpec), getDefaultSize(getSuggestedMinimumHeight(), heightMeasureSpec));
    }
}

在这个例子中，如果父组件已经指定了确定的宽度（widthMode == MeasureSpec.EXACTLY），那么我们就不需要调用 computeMinIntrinsicWidth 方法。

总结与选择

以上我们讨论了多种优化 computeMinIntrinsicWidth 的方法，以避免 O(N^2) 性能陷阱。选择哪种方法取决于你的具体场景。

缓存子组件的 Intrinsic Width: 适用于子组件的尺寸变化不频繁的情况。这种方法简单有效，可以显著提高性能。
延迟计算 Intrinsic Width: 适用于 intrinsic width 的计算比较耗时的情况。这种方法可以避免不必要的计算，但可能会导致布局更新延迟。
优化子组件的 computeMinIntrinsicWidth 实现: 这是从根本上解决问题的方法。如果子组件的 computeMinIntrinsicWidth 方法本身就比较耗时，那么优化它的实现可以带来显著的性能提升。
使用 MeasureSpec 进行优化: 适用于父组件已经指定了确定的尺寸的情况。这种方法可以避免不必要的计算，但需要仔细分析 MeasureSpec 的值。

在实际应用中，可以将多种方法结合使用，以达到最佳的性能效果。

最后，请记住，性能优化是一个持续的过程。我们需要不断地分析和优化代码，才能确保 UI 的流畅性和响应速度。理解 intrinsic size 的计算方式，并避免 O(N^2) 的性能陷阱，是构建高性能自定义 UI 组件的关键一步。

Intrinsic Size 计算：O(N^2) 性能陷阱与 computeMinIntrinsicWidth 的正确实现

什么是 Intrinsic Size？

O(N^2) 性能陷阱

正确实现 computeMinIntrinsicWidth

总结与选择

发表回复 取消回复

Intrinsic Size 计算：O(N^2) 性能陷阱与 `computeMinIntrinsicWidth` 的正确实现

正确实现 `computeMinIntrinsicWidth`

发表回复取消回复