高效的找出两个List中的不同元素
List 高效 元素 不同 两个 找出
2023-09-11 14:18:37 时间
转自同名博文,未知真正出处,望作者见谅
如题:有List<String> list1和List<String> list2,两个集合各有上万个元素,怎样取出两个集合中不同的元素?
方法1:遍历两个集合:
package com.czp.test; import java.util.ArrayList; import java.util.List; public class TestList { public static void main(String[] args) { List<String> list1 = new ArrayList<String>(); List<String> list2 = new ArrayList<String>(); for (int i = 0; i < 10000; i++) { list1.add("test"+i); list2.add("test"+i*2); } getDiffrent(list1,list2); //输出:total times 2566454675 } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent(List<String> list1, List<String> list2) { long st = System.nanoTime(); List<String> diff = new ArrayList<String>(); for(String str:list1) { if(!list2.contains(str)) { diff.add(str); } } System.out.println("total times "+(System.nanoTime()-st)); return diff; } }
千万不要采用这种方法,总共要循环的次数是两个List的size相乘的积,从输出看耗时也是比较长的,那么我们有没有其他的方法呢?当然有.
方法2:采用List提供的retainAll()方法:
package com.czp.test; import java.util.ArrayList; import java.util.List; public class TestList { public static void main(String[] args) { List<String> list1 = new ArrayList<String>(); List<String> list2 = new ArrayList<String>(); for (int i = 0; i < 10000; i++) { list1.add("test"+i); list2.add("test"+i*2); } getDiffrent(list1,list2); //输出:total times 2566454675 getDiffrent2(list1,list2); //输出:getDiffrent2 total times 2787800964 } /** * 获取连个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent2(List<String> list1, List<String> list2) { long st = System.nanoTime(); list1.retainAll(list2); System.out.println("getDiffrent2 total times "+(System.nanoTime()-st)); return list1; } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent(List<String> list1, List<String> list2) { long st = System.nanoTime(); List<String> diff = new ArrayList<String>(); for(String str:list1) { if(!list2.contains(str)) { diff.add(str); } } System.out.println("getDiffrent total times "+(System.nanoTime()-st)); return diff; } } 很遗憾,这种方式虽然只要几行代码就搞定,但是这个却更耗时,查看retainAll()的源码: public boolean retainAll(Collection<?> c) { boolean modified = false; Iterator<E> e = iterator(); while (e.hasNext()) { if (!c.contains(e.next())) { e.remove(); modified = true; } } return modified; }
无需解释这个耗时是必然的,那么我们还有没有更好的办法呢?仔细分析以上两个方法中我都做了mXn次循环,其实完全没有必要循环这么多次,我们的需求是找出两个List中的不同元素,那么我可以这样考虑:用一个map存放lsit的所有元素,
其中的key为lsit1的各个元素,value为该元素出现的次数,接着把list2的所有元素也放到map里,如果已经存在则value加1,最后我们只要取出map里value为1的元素即可,这样我们只需循环m+n次,大大减少了循环的次数。
package com.czp.test; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class TestList { public static void main(String[] args) { List<String> list1 = new ArrayList<String>(); List<String> list2 = new ArrayList<String>(); for (int i = 0; i < 10000; i++) { list1.add("test"+i); list2.add("test"+i*2); } getDiffrent(list1,list2); //输出:total times 2566454675 getDiffrent2(list1,list2); //输出:getDiffrent2 total times 2787800964 getDiffrent3(list1,list2); //输出:getDiffrent3 total times 61763995 } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent3(List<String> list1, List<String> list2) { long st = System.nanoTime(); Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size()); List<String> diff = new ArrayList<String>(); for (String string : list1) { map.put(string, 1); } for (String string : list2) { Integer cc = map.get(string); if(cc!=null) { map.put(string, ++cc); continue; } map.put(string, 1); } for(Map.Entry<String, Integer> entry:map.entrySet()) { if(entry.getValue()==1) { diff.add(entry.getKey()); } } System.out.println("getDiffrent3 total times "+(System.nanoTime()-st)); return list1; } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent2(List<String> list1, List<String> list2) { long st = System.nanoTime(); list1.retainAll(list2); System.out.println("getDiffrent2 total times "+(System.nanoTime()-st)); return list1; } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent(List<String> list1, List<String> list2) { long st = System.nanoTime(); List<String> diff = new ArrayList<String>(); for(String str:list1) { if(!list2.contains(str)) { diff.add(str); } } System.out.println("getDiffrent total times "+(System.nanoTime()-st)); return diff; } }
显然,这种方法大大减少耗时,是方法1的1/4,是方法2的1/40,这个性能的提升时相当可观的,但是,这不是最佳的解决方法,观察方法3我们只是随机取了一个list作为首次添加的标准,这样一旦我们的list2比list1的size大,则我们
第二次put时的if判断也会耗时,做如下改进:
package com.czp.test; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class TestList { public static void main(String[] args) { List<String> list1 = new ArrayList<String>(); List<String> list2 = new ArrayList<String>(); for (int i = 0; i < 10000; i++) { list1.add("test"+i); list2.add("test"+i*2); } getDiffrent(list1,list2); getDiffrent2(list1,list2); getDiffrent3(list1,list2); getDiffrent4(list1,list2); // getDiffrent total times 2789492240 // getDiffrent2 total times 3324502695 // getDiffrent3 total times 24710682 // getDiffrent4 total times 15627685 } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent4(List<String> list1, List<String> list2) { long st = System.nanoTime(); Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size()); List<String> diff = new ArrayList<String>(); List<String> maxList = list1; List<String> minList = list2; if(list2.size()>list1.size()) { maxList = list2; minList = list1; } for (String string : maxList) { map.put(string, 1); } for (String string : minList) { Integer cc = map.get(string); if(cc!=null) { map.put(string, ++cc); continue; } map.put(string, 1); } for(Map.Entry<String, Integer> entry:map.entrySet()) { if(entry.getValue()==1) { diff.add(entry.getKey()); } } System.out.println("getDiffrent4 total times "+(System.nanoTime()-st)); return diff; } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent3(List<String> list1, List<String> list2) { long st = System.nanoTime(); Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size()); List<String> diff = new ArrayList<String>(); for (String string : list1) { map.put(string, 1); } for (String string : list2) { Integer cc = map.get(string); if(cc!=null) { map.put(string, ++cc); continue; } map.put(string, 1); } for(Map.Entry<String, Integer> entry:map.entrySet()) { if(entry.getValue()==1) { diff.add(entry.getKey()); } } System.out.println("getDiffrent3 total times "+(System.nanoTime()-st)); return diff; } /** * 获取连个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent2(List<String> list1, List<String> list2) { long st = System.nanoTime(); list1.retainAll(list2); System.out.println("getDiffrent2 total times "+(System.nanoTime()-st)); return list1; } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent(List<String> list1, List<String> list2) { long st = System.nanoTime(); List<String> diff = new ArrayList<String>(); for(String str:list1) { if(!list2.contains(str)) { diff.add(str); } } System.out.println("getDiffrent total times "+(System.nanoTime()-st)); return diff; } }
这里对连个list的大小进行了判断,小的在最后添加,这样会减少循环里的判断,性能又有了一定的提升,正如一位朋友所说,编程是无止境的,只要你认真去思考了,总会找到更好的方法!
非常感谢binglian的指正,针对List有重复元素的问题,做以下修正,首先明确一点,两个List不管有多少个重复,只要重复的元素在两个List都能找到,则不应该包含在返回值里面,所以在做第二次循环时,这样判断:如果当前元素在map中找不到,则肯定需要添加到返回值中,如果能找到则value++,遍历完之后diff里面已经包含了只在list2里而没在list2里的元素,剩下的工作就是找到list1里有list2里没有的元素,遍历map取value为1的即可:
package com.czp.test; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class TestList { public static void main(String[] args) { List<String> list1 = new ArrayList<String>(); List<String> list2 = new ArrayList<String>(); for (int i = 0; i < 10000; i++) { list1.add("test"+i); list2.add("test"+i*2); } getDiffrent(list1,list2); getDiffrent3(list1,list2); getDiffrent5(list1,list2); getDiffrent4(list1,list2); getDiffrent2(list1,list2); // getDiffrent3 total times 32271699 // getDiffrent5 total times 12239545 // getDiffrent4 total times 16786491 // getDiffrent2 total times 2438731459 } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent5(List<String> list1, List<String> list2) { long st = System.nanoTime(); List<String> diff = new ArrayList<String>(); List<String> maxList = list1; List<String> minList = list2; if(list2.size()>list1.size()) { maxList = list2; minList = list1; } Map<String,Integer> map = new HashMap<String,Integer>(maxList.size()); for (String string : maxList) { map.put(string, 1); } for (String string : minList) { if(map.get(string)!=null) { map.put(string, 2); continue; } diff.add(string); } for(Map.Entry<String, Integer> entry:map.entrySet()) { if(entry.getValue()==1) { diff.add(entry.getKey()); } } System.out.println("getDiffrent5 total times "+(System.nanoTime()-st)); return diff; } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent4(List<String> list1, List<String> list2) { long st = System.nanoTime(); Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size()); List<String> diff = new ArrayList<String>(); List<String> maxList = list1; List<String> minList = list2; if(list2.size()>list1.size()) { maxList = list2; minList = list1; } for (String string : maxList) { map.put(string, 1); } for (String string : minList) { Integer cc = map.get(string); if(cc!=null) { map.put(string, ++cc); continue; } map.put(string, 1); } for(Map.Entry<String, Integer> entry:map.entrySet()) { if(entry.getValue()==1) { diff.add(entry.getKey()); } } System.out.println("getDiffrent4 total times "+(System.nanoTime()-st)); return diff; } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent3(List<String> list1, List<String> list2) { long st = System.nanoTime(); Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size()); List<String> diff = new ArrayList<String>(); for (String string : list1) { map.put(string, 1); } for (String string : list2) { Integer cc = map.get(string); if(cc!=null) { map.put(string, ++cc); continue; } map.put(string, 1); } for(Map.Entry<String, Integer> entry:map.entrySet()) { if(entry.getValue()==1) { diff.add(entry.getKey()); } } System.out.println("getDiffrent3 total times "+(System.nanoTime()-st)); return diff; } /** * 获取连个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent2(List<String> list1, List<String> list2) { long st = System.nanoTime(); list1.retainAll(list2); System.out.println("getDiffrent2 total times "+(System.nanoTime()-st)); return list1; } /** * 获取两个List的不同元素 * @param list1 * @param list2 * @return */ private static List<String> getDiffrent(List<String> list1, List<String> list2) { long st = System.nanoTime(); List<String> diff = new ArrayList<String>(); for(String str:list1) { if(!list2.contains(str)) { diff.add(str); } } System.out.println("getDiffrent total times "+(System.nanoTime()-st)); return diff; } }
相关文章
- 02-线性结构3 Reversing Linked List (25分)
- Scala中List(Map1,Map2,Map3 ....) 转成一个Map
- 解决At least one JAR was scanned for TLDs yet contained no TLDs. Enable debug logging for this logger for a complete list of JARs that were scanned but no TLDs were found in them. Skipping unneeded JAR
- python list中append()与extend()用法
- [Algorithm] 234. Palindrome Linked List / Reverse linked list
- mysql 8.0下的SELECT list is not in GROUP BY clause and contains nonaggregated column
- Python中实现对list做减法操作介绍
- 打印系统里所有不包含任何错误的order list
- Atitit sumdoc t5 final file list sumdoc t5 finalsumdoc t511 sumdoc t5 finalsumdoc t511.zip sum
- JavaWeb课程复习资料(三)——将【resultSet】形式的数据转为List<T>的形式
- 关于Copy On Write Array List,你会安全使用么
- java - List取差集时报错 Method threw 'java.lang.UnsupportedOperationException' exception. 解决
- 【Spring】 注入 Bean 到 List / Map 中
- 【LeetCode】Partition List
- List、Map和Set实现类
- LVGL 8.2 List
- 【C++要笑着学】list 核心框架接口的模拟实现 | 运算符重载实现list迭代器 | 妙用模板实现const迭代器
- 瞬间教你学会使用java中list的retainAll方法