-
关于java中List的removeAll()方法删除大量数据时的效率问题10
现在遇到一个关于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[]>
问题补充：<div class="quote_title">chen_yongkai 写道</div><div class="quote_div"><pre name="code" class="java">
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;
}
</pre> <br />随手敲的，没编译过，估计内存开销挺大的</div> <br /> <br />您好，代码我试过了，效率是惊人的快！呵呵，之前从来没有想过用到LinkedList，只要是出现List，就习惯性的用ArrayList，但这次遇到大数据量时，才发现弊端，对于java这一块，平时也没有深入的理解，就是简单的应用。本来是想着问问大家本质原因是什么，但我还是觉着自己先看看，理解消化一下，到了真正的难点的时候再向大家请教，谢谢！2012年3月14日 11:07
添加评论
关注(0)11个答案 按时间排序 按投票排序
-
采纳的答案
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; }
随手敲的，没编译过，估计内存开销挺大的2012年3月14日 22:41
-
引用集合元素是Integer数组：List<Integer[]>
集合里居然放的是数组，比较集合元素又要增加复杂度了。
数组是否有序？比较两个数组相等的条件有要求吗？（所有下标对应的数组元素都相同，还是只要求数组包含相同元素）。2012年3月15日 11:03
-
我建议把
Integer[]
封装为一个对象class Compare{ private int[] data; //get set public 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(){ //最好将数据散列开 //... } }2012年3月15日 10:50
-
刚才测试了一下效果还不错：
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()); }2012年3月14日 11:32
-
很早以前研究过，我的方案是先把listA和listB用快速排序算法排好序，然后再比较删除，这样的时间复杂度就是O(n)(不算快速排序的时间），空间复杂度是O(n+m)，牺牲内存换时间。
2012年3月14日 11:22
-
分析源码：
引用
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)。
2012年3月14日 11:18
相关推荐
在Java编程语言中，`List.removeAll()`方法是一个非常实用的函数，它允许我们从列表中一次性移除所有指定元素。这个方法是集合框架的一部分，它提供了高效的方式来进行元素的删除操作。本文将深入探讨`removeAll()`...
通常，我们使用`remove()`或`removeAll()`方法删除单个元素或集合。要删除一个区间，可以使用迭代器来实现。以下是一个示例： ```java List<Integer> list = new ArrayList(); // 填充列表... int start = .....
Java接口API是Java编程中非常重要的组成部分，它提供了一系列预定义的方法，使得开发者能够方便地进行应用程序开发。...在处理大量数据或需要进行复杂操作时，理解并熟练使用集合框架是Java程序员必备的技能。
`putAll()`方法虽然可以批量插入键值对，但如果Map没有预先调整大小，可能会在添加大量元素时不如逐个`put()`高效。不过，`putAll()`会在添加元素前调整Map的容量，这在某些情况下可能比预期更有效。 9. **选择...
但是，插入和删除元素时，特别是当元素不在末尾时，效率相对较低，因为可能需要移动大量元素来保持顺序。 2. LinkedList实现类： LinkedList是另一个List接口的实现，它以双向链表的形式存储元素。这使得在链表的...
- ArrayList在查询元素时速度快，但插入和删除元素（尤其是中间位置）时需要移动大量元素，效率较低。 - LinkedList在插入和删除元素时速度快，但查询元素（特别是随机访问）时效率较低，因为需要遍历链表。 5. *...
- `void removeAll(Collection c)`：从当前集合中移除另一个集合中的所有元素。 - `boolean retainAll(Collection c)`：保留当前集合中也存在于另一个集合中的元素。 #### 总结 Java集合框架为开发者提供了一套...
数组是最基本的容器，可以存储多个对象，但它有很多缺点，如长度必须在初始化时指定，数组采用连续存储空间，删除和添加效率低下，数组无法直接保存映射关系，数组缺乏封装，操作繁琐。因此，我们需要一种更强大、更...
但插入和删除元素时，可能需要移动大量元素，效率较低。 顺序表的接口`LList<T>`定义了如下操作： - `isEmpty()`：检查线性表是否为空。 - `size()`：返回线性表的长度。 - `get(int i)`：获取指定索引位置的元素。...
15. **利用Java集合类的批量操作**：如List的addAll、removeAll等，它们通常比循环删除或添加元素更高效。 16. **使用并发工具类**：如ConcurrentHashMap、CopyOnWriteArrayList等，它们为多线程环境提供了更好的...
`removeAll(E e)`方法移除所有出现的指定元素，需要遍历顺序表并删除匹配的元素。这个操作的时间复杂度为O(n)，因为可能需要遍历整个数组。 总的来说，这个Java实现的顺序表展示了如何使用数组来高效地存储和操作...
在PHP开发中，尤其是在处理大量数据或需要进行复杂操作时，CollectionsPHP集合库能够大大提高开发效率。 首先，让我们了解一下什么是集合。在编程中，集合是一种可以存储多个元素的数据结构，这些元素可以是同一种...
在开发过程中，当需要处理大量相同数据类型的数据时，集合比数组更具优势。数组虽然简单，但存在一些局限性，如方法有限、数据类型单一、容量固定等。集合则针对这些问题进行了优化，提供了丰富的操作方法，支持多种...
11. **性能分析**：讨论不同数据结构在不同场景下的性能差异，例如在大量数据操作时，哪种数据结构更适合。 通过对这个项目的学习，开发者将能熟练掌握Java中Maps和Sets的使用，提升代码质量和效率。无论是在面试中...
ArrayList是Java集合框架中的一个重要类，属于List接口的实现，它提供了动态数组的功能，允许我们在运行时添加、删除和修改元素。本篇文章将深入讲解如何使用ArrayList对字符串进行存储和管理。 一、ArrayList简介 ...
总结，zip4j库为Java开发者提供了全面且高效的ZIP文件处理方案，无论是在日常开发还是在处理大量数据时，都能显著提升工作效率。其丰富的API和对密码保护的支持，使得在安全性上也有保障。正确理解和运用zip4j，无疑...
每当用户输入、删除或修改文本时，都会触发`updateList()`方法。在这个方法中，我们会根据当前输入的文本过滤出匹配的建议，并更新`JComboBox`的内容，同时显示下拉列表。 ```java txtInput.getDocument()....
在Java编程中，`retainAll`方法是集合类（如ArrayList、LinkedList或HashSet）中一个重要的成员函数。这个方法用于保留集合中与指定集合交集的所有元素，即删除所有不在指定集合中的元素。然而，标题提到"避免使用...