问题描述
现在遇到一个关于List的removeAll()方法的效率问题，现在有一个数据量很大的List A,目前数据量是186万多，要删除一个子的List B,数据量是6万多，现在想到的只有A.removeAll(B);但是整个过程要花15分钟左右，电脑配置也不错，DELL商务机。 在网上也搜了不少，找到最符合条件的一条信息(06年的贴) http://topic.csdn.net/t/20060904/18/4998018.html ，大体内容跟我遇到的情况差不多，最后那位大拿把问题解决了，但是不太理解，就是简单的说“native method”方法。我对C这一块不熟，大家有没有遇到过这类问题，交流一下吧... 问题补充：<div class="quote_title">wangqj 写道</div><div class="quote_div">你最好把你存入list的数据是什么特点的贴出来，可以根据你的数据的特点重写removeAll方法</div><br />集合元素是Integer数组：List<Integer[]>
解决方案
public static List removeAll(List a,List b){LinkedList c=new LinkedList(a);//大集合用LinkedList HashSet s=new HashSet(b);//小集合用HashSet Iterator iter=c.iter;while(iter.hasNext()){if(s.contains(iter.next()){iter.remove();}}return c;}随手敲的，没编译过，估计内存开销挺大的
解决方案二：
引用集合元素是Integer数组：List<Integer[]> 集合里居然放的是数组，比较集合元素又要增加复杂度了。数组是否有序？比较两个数组相等的条件有要求吗？（所有下标对应的数组元素都相同，还是只要求数组包含相同元素）。
解决方案三：
我建议把Integer[]封装为一个对象class Compare{private int[] data;//get setpublic Compare(int[] n){ this.data =n; //jdk默认使用归并，根据数据的特性做出优化 Arrays.sort(data); } //重写equals @override public boolean(Compare c){ if(c.getData.length!=this.data.length) return false; for(int i=0;i<data.length;i++){ if(c.getData[i]!=data[i]) return fasle; } return true; } //重写hashcode public int hashcode(){ //最好将数据散列开 //... }}
解决方案四：
而且有可能慢不是慢在你remove上，而是gc上建议加大XMX
解决方案五：
为什么不用hashset呢
解决方案六：
方法重写
解决方案七：
你最好把你存入list的数据是什么特点的贴出来，可以根据你的数据的特点重写removeAll方法
解决方案八：
刚才测试了一下效果还不错：public static void main(String[] args) {int n = 1000000;int m = 10000;ArrayList<Integer> a = new ArrayList<Integer>(n);ArrayList<Integer> b = new ArrayList<Integer>(m);for (int i = 0; i < n; i++) {a.add(RandomUtils.randInt(n));//随机数}for (int i = 0; i < m; i++) {b.add(RandomUtils.randInt(n));}long time = System.currentTimeMillis();ArrayList<Integer> c = removeAll(a, b);time = System.currentTimeMillis() - time;System.out.println(time);//31044ms,31秒System.out.println(c.size());}
解决方案：
这个需要根据你自己的业务逻辑，自己实现一个算法，写一个集合类，覆盖arraylist的remove方法
解决方案：
很早以前研究过，我的方案是先把listA和listB用快速排序算法排好序，然后再比较删除，这样的时间复杂度就是O(n)(不算快速排序的时间），空间复杂度是O(n+m)，牺牲内存换时间。
解决方案：
分析源码：引用 public boolean removeAll(Collection<?> c) {boolean modified = false;Iterator<?> e = iterator();while (e.hasNext()) { if (c.contains(e.next())) {e.remove();//如果是LinkedList，这步删除操作会快很多modified = true; }}return modified; }如果listA是LinkedList它的时间复杂度最差情况是O(n*m),n和m分别是listA和listB的size。如果是ArrayList它的时间复杂度最差情况就是O(n*n*m)。