探索数据操作的功率是软件开发中的一项重要任务。开发中遇到了Java中的ArrayList和removeAll办法，意外发现当面对大量数据时，其履行功率可能会让人瞠目结舌，高达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));
上述代码成果：
这样看来并不是什么耗时的操作，可是结合上面的运用场景，是在更新RV时进行的数据处理，那157ms 足以导致掉帧卡顿，毕竟咱们有16.6ms 的刷新机制限制，在事务中数据较大时，咱们测验直接呈现出来了900多ms
二、剖析一下removeAll 为什么会有这么多的耗时？
要是有不知道怎样剖析时刻复杂度的能够看下我之前的一个文章 # 算法-时刻复杂度剖析 。
在此处，咱们要剖析removeAll 的时刻复杂度，第一步先看下办法的签名
boolean removeAll(Collection<?> c)
经过这个办法签名咱们大致能够推断出影响removeAll 办法的时刻复杂度的因素主要有两个：
- 要移除的元素数量
- 底层数据结构的完结
底层数据结构是基于数组完结的动态数组
假设要移除的元素数量为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 处理
上面的耗时基本是来自两个方面
- 遍历
- 遍历 + 移动元素
那咱们能够优先从遍历入手，咱们都知道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列表中相同的元素，并将移除后的成果存储在一个新的列表中回来,以达到咱们想要的作用，
在当时的事务中也是优化到了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));
}
在咱们事务中，从900ms 优化到5ms, 作用是十分不错的，而且复杂数据测验的规划是10万中删去3000，基本满意大型列表删去场景了。
六、总结
为什么要写这个记载，都是一个十分简略的场景及运用方法，可是从发现这个问题到思考怎样处理却是一次算法学习的实践应用。咱们在开发中，不会常常运用算法，可是像这种问题，咱们能够用算法的角度去剖析优化，这大概便是算法学习的含义
