[数据结构与算法]使用JProfile进行优化笛卡尔乘积运算，提高性能

利用JProfile优化笛卡尔乘积运算，提高性能

项目场景

项目需要对嵌套的集合进行笛卡尔乘积运算，具体要求为：给定一个嵌套的集合$S1=[S{1}_1,S{1}_2,...,S{1}_k]$，其中$S{1}_i$是由单元素构成的集合，另一个集合$S2$也是由单元素构成的，需要实现集合$S1$与$S2$的笛卡尔乘积。代码实现原本为：

大致思路是使用双层循环，这里cur代表上述的$S1$,next代表上述$S2$，temp代表$S{1}_i$，内层循环每次取next中一个元素，加到外层循环下的temp中,由于需要保证内层每次循环操作中拿到的temp都需要保持一致，因此需要通过对lcs进行深拷贝获取temp，这里采用的是new HashSet<>(lcs)的方式，更新temp后需要根据业务对结果做一个过滤，最后将结果保存到res集合中。

问题描述

实际运行过程中，结果没有问题，但是运行速度十分慢，一次运行过程的时间记录如下：

可以看到，在迭代收敛前有若干次运行时间都在几十秒甚至100多秒，更大的数据集下，观测到的一次运行结果里，第10次迭代更是达到了2000+s，且出现了内存不足，最后被强制终止。

问题分析

由于整个代码比较复杂，在解决bug之前，并没有意识到是上述代码出问题，最后是借助Java程序性能分析工具JProfile，检查运行时各函数调用的时间、空间开销，得到如下结果：

可以看到上述函数过程是程序运行的性能瓶颈所在，开销占比高达74.3%，因此需要对上述程序进行分析重构。分析可知，上述嵌套集合的笛卡尔乘积操作，由两个集合最终生成$K?|S2|$个的新集合，会有大量的集合创建和更新操作，分别对应由lcs深拷贝生成temp和往temp里添加一个元素，最后过滤，将满足条件的结果添加到res。

由于HashSet的底层数据结构是哈希表，需要为添加的元素计算哈希索引以保证唯一性，而此处其实只需要复制一份lcs里的元素，防止后续修改影响到lcs的内容，不需要额外的唯一性约束，完全可以用更简单的集合来拷贝，比如ArrayList，在添加新元素时，ArrayList的复杂度虽然大于HashSet，但是此处只有一次操作，影响较小。但此处用list来保存更新的结果可能违反集合元素唯一性的要求，需要对结果再次去重，考虑到后续有过滤操作，完全可以把去重操作延迟，对满足过滤条件的结果再去重，尽量减少不必要的操作。最后得到的代码如下：

运行结果

代码优化后，再次运行上述例子，运行时间减少了近90%，实现了性能优化！