空间换时间-五秒出解:从900ms到5ms的幕后优化大揭秘!

发布时间:2024年01月05日

探索数据操作的效率是软件开发中的一项重要任务。开发中遇到了Java中的ArrayListremoveAll方法,意外发现当面对大量数据时,其执行效率可能会让人瞠目结舌,高达900毫秒以上!然而,通过一系列分析和优化实验,我成功将执行时间从900ms优化到令人惊叹的5ms以内。

平时各种数据结构,各种算法优化都在储备,但是实际开发时一般情况下真的不会使用,就比如今天的这个场景:

RV 中按照折叠方式展示数据,但是数据量较大,且数据关系层级不明显,所以考虑使用RV多布局实现,然后在折叠层中进行打开关闭操作,由于折叠时的数据巨大,如果进行RV item中的折叠动作的话会发生渲染问题。所以直接简单粗暴从目标集合中删除需要折叠的 然后打开时再进行添加,在这个想法之下,引出了这个问题:

一、removeAll 导致UI卡顿

查看发现卡顿的来源就是removeAll 时的耗时,从目标集合中移除3000个元素,耗时差不多900ms.

一开始同事和同事讨论时以为是RV的渲染导致的卡顿,随即有同事指出RV的显示机制在多布局的模式下其实不会存在渲染卡顿的(这就是人多力量大的典范哈),然后测试发现是移除数据时,耗时导致的。

具体步骤大概是这样:

// 1. 测试数据,由于测试数据比较简单,耗时会比业务中的实际数据低很多
ArrayList<Demo> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    list.add(new Demo("index=", i));
}
long start = System.currentTimeMillis();
List<Demo> demos = new ArrayList<>(list.subList(1000, 4000));
list.removeAll(demos);
System.out.println("用时 " + (System.currentTimeMillis() - start));

上述代码结果:

image.png

这样看来并不是什么耗时的操作,但是结合上面的使用场景,是在更新RV时进行的数据处理,那157ms 足以导致掉帧卡顿,毕竟我们有16.6ms 的刷新机制限制,在业务中数据较大时,我们测试直接呈现出来了900多ms

二、分析一下removeAll 为什么会有这么多的耗时?

要是有不知道怎么分析时间复杂度的可以看下我之前的一个文章 # 算法-时间复杂度分析

在此处,我们要分析removeAll 的时间复杂度,第一步先看下方法的签名

boolean removeAll(Collection<?> c)

通过这个方法签名我们大致可以推断出影响removeAll 方法的时间复杂度的因素主要有两个:

  1. 要移除的元素数量
  2. 底层数据结构的实现

底层数据结构是基于数组实现的动态数组

假设要移除的元素数量为n

如果要移除的集合 c 是空集合,那么无需执行任何移除操作,直接返回,时间复杂度为 O(1)。

(1) 遍历A

   判断B.contains(A[i])

   若不包含,则 A[w] = A[i]  w从0递增

(2) 遍历完成则将 A[w]往后部分置为 null


(3) 看下上面(1)B.contains(A[i])的逻辑:

   遍历B,一个个匹配,匹配到则返回B的index

简单来讲,两层循环时间复杂度就是O(n*m),如果ArrayList的大小为m,参数c的大小为c,且c < m,则在最坏情况下(即c中的所有元素都存在于ArrayList中),总的时间复杂度为O(m^2)

这就是平方级的时间复杂度。看来要解决此问题,就需要寻找其他方案

三、使用linkeList

对于删除操作,链表肯定是具备先天优势的,但是使用后发现, 时间有提升,但是效果不大,查看代码发现:

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        if (c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

它是循环使用next 取,完后remove 的,那效果自然也不行,但是如果我们自定义链表,直接修改删除区间集合的指针,倒是一个完美的解决方案,但是自定义数据结果,在业务中使用风险太大。

四、利用hashSet 解决

上面的耗时基本是来自两个方面

  1. 遍历
  2. 遍历 + 移动元素

那我们可以优先从遍历入手,大家都知道Hash 的查询时间是O(1), 这样的话用hash和LinkedList 就能更进一步优化耗时了

看下代码:

public static <T> List<T> removeAll(List<T> source, List<T> target) {
    LinkedList<T> result = new LinkedList<>();
    HashSet<T> hashSet = new HashSet<>(source);
    for (T t : source) {
        if (!hashSet.contains(t)) {
            result.add(t);
        }
    }
    return result;
}

source列表中移除与target列表中相同的元素,并将移除后的结果存储在一个新的列表中返回,以达到我们想要的效果,

image.png

在当时的业务中也是优化到了100ms 以内。

但是这个方式还存在一个弊端,当source非常大,target 又比较小时、或者都非常大时,还是会存在耗时。

五、利用空间换时间

我们在学习算法的时候,大家都听过一句话,算法优化基本就是时间换空间或者空间换时间,当我们需要确定一个参数优化到极致时,我们就可以在另一个方向上做优化。

我们验证一下:

思路是这样的,我们直接反取目标数据,

比如,从10万条数据中删除第1000到3000 的数据,那我们可以反取数据,取出0到999生成一个新集合,再取3001到10万为一个集合,最后再将二者的数据合并,加到目标集合中。

public static void main(String[] args) {
        ArrayList<Demo> list = new ArrayList<>();
        for (int i = 0; i < 100000; i++) {
            list.add(new Demo("index=", i));
        }
        long start = System.currentTimeMillis();
        // 创建集合
        ArrayList<Demo> demos1 = new ArrayList<>(list.subList(0, 999));
        ArrayList<Demo> demos2 = new ArrayList<>(list.subList(1000, list.size() - 1));
//        removeAll(list, demos);
        list.clear();
        list.addAll(demos1);
        list.addAll(demos2);
        System.out.println("用时 " + (System.currentTimeMillis() - start));
    }

image.png

在我们业务中,从900ms 优化到5ms, 效果是非常不错的,并且复杂数据测试的规模是10万中删除3000,基本满足大型列表删除场景了。

六、总结

为什么要写这个记录,都是一个非常简单的场景及使用方式,但是从发现这个问题到思考怎么解决却是一次算法学习的实际应用。我们在开发中,不会经常使用算法,但是像这种问题,我们可以用算法的角度去分析优化,这大概就是算法学习的意义

文章来源:https://blog.csdn.net/qq_32648731/article/details/135402926
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。