首页 > 代码库 > 两个list取不同值

两个list取不同值

2024-08-28 13:31:57   220人阅读

转自同名博文，未知真正出处，望作者见谅

如题：有List<String> list1和List<String> list2,两个集合各有上万个元素，怎样取出两个集合中不同的元素?

方法1：遍历两个集合：

[java] view plain copy
 
 print?技术分享技术分享
  1. package com.czp.test;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.List;  
  5.   
  6. public class TestList {  
  7.   
  8.     public static void main(String[] args) {  
  9.         List<String> list1 = new ArrayList<String>();  
  10.         List<String> list2 = new ArrayList<String>();  
  11.         for (int i = 0; i < 10000; i++) {  
  12.             list1.add("test"+i);  
  13.             list2.add("test"+i*2);  
  14.         }  
  15.         getDiffrent(list1,list2);  
  16.         //输出：total times 2566454675  
  17.     }  
  18.   
  19.     /** 
  20.      * 获取两个List的不同元素 
  21.      * @param list1 
  22.      * @param list2 
  23.      * @return 
  24.      */  
  25.     private static List<String> getDiffrent(List<String> list1, List<String> list2) {  
  26.         long st = System.nanoTime();  
  27.         List<String> diff = new ArrayList<String>();  
  28.         for(String str:list1)  
  29.         {  
  30.             if(!list2.contains(str))  
  31.             {  
  32.                 diff.add(str);  
  33.             }  
  34.         }  
  35.         System.out.println("total times "+(System.nanoTime()-st));  
  36.         return diff;  
  37.     }  
  38. }  
千万不要采用这种方法，总共要循环的次数是两个List的size相乘的积，从输出看耗时也是比较长的，那么我们有没有其他的方法呢？当然有.

方法2：采用List提供的retainAll（）方法：

[java] view plain copy
 
 print?技术分享技术分享
  1. package com.czp.test;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.List;  
  5.   
  6. public class TestList {  
  7.   
  8.     public static void main(String[] args) {  
  9.         List<String> list1 = new ArrayList<String>();  
  10.         List<String> list2 = new ArrayList<String>();  
  11.         for (int i = 0; i < 10000; i++) {  
  12.             list1.add("test"+i);  
  13.             list2.add("test"+i*2);  
  14.         }  
  15.         getDiffrent(list1,list2);  
  16.         //输出：total times 2566454675  
  17.         getDiffrent2(list1,list2);  
  18.         //输出：getDiffrent2 total times 2787800964  
  19.     }  
  20.       
  21.     /** 
  22.      * 获取连个List的不同元素 
  23.      * @param list1 
  24.      * @param list2 
  25.      * @return 
  26.      */  
  27.     private static List<String> getDiffrent2(List<String> list1, List<String> list2) {  
  28.         long st = System.nanoTime();  
  29.         list1.retainAll(list2);  
  30.         System.out.println("getDiffrent2 total times "+(System.nanoTime()-st));  
  31.         return list1;  
  32.     }  
  33.   
  34.     /** 
  35.      * 获取两个List的不同元素 
  36.      * @param list1 
  37.      * @param list2 
  38.      * @return 
  39.      */  
  40.     private static List<String> getDiffrent(List<String> list1, List<String> list2) {  
  41.         long st = System.nanoTime();  
  42.         List<String> diff = new ArrayList<String>();  
  43.         for(String str:list1)  
  44.         {  
  45.             if(!list2.contains(str))  
  46.             {  
  47.                 diff.add(str);  
  48.             }  
  49.         }  
  50.         System.out.println("getDiffrent total times "+(System.nanoTime()-st));  
  51.         return diff;  
  52.     }  
  53. }  
  54. 很遗憾，这种方式虽然只要几行代码就搞定，但是这个却更耗时，查看retainAll（）的源码:  
  55.   
  56.  public boolean retainAll(Collection<?> c) {  
  57.     boolean modified = false;  
  58.     Iterator<E> e = iterator();  
  59.     while (e.hasNext()) {  
  60.         if (!c.contains(e.next())) {  
  61.         e.remove();  
  62.         modified = true;  
  63.         }  
  64.     }  
  65.     return modified;  
  66.     }  
无需解释这个耗时是必然的，那么我们还有没有更好的办法呢？仔细分析以上两个方法中我都做了mXn次循环，其实完全没有必要循环这么多次，我们的需求是找出两个List中的不同元素,那么我可以这样考虑：用一个map存放lsit的所有元素，其中的key为lsit1的各个元素，value为该元素出现的次数,接着把list2的所有元素也放到map里，如果已经存在则value加1，最后我们只要取出map里value为1的元素即可，这样我们只需循环m+n次，大大减少了循环的次数。
[java] view plain copy
 
 print?技术分享技术分享
  1. package com.czp.test;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.HashMap;  
  5. import java.util.List;  
  6. import java.util.Map;  
  7.   
  8. public class TestList {  
  9.   
  10.     public static void main(String[] args) {  
  11.         List<String> list1 = new ArrayList<String>();  
  12.         List<String> list2 = new ArrayList<String>();  
  13.         for (int i = 0; i < 10000; i++) {  
  14.             list1.add("test"+i);  
  15.             list2.add("test"+i*2);  
  16.         }  
  17.         getDiffrent(list1,list2);  
  18.         //输出：total times 2566454675  
  19.         getDiffrent2(list1,list2);  
  20.         //输出：getDiffrent2 total times 2787800964  
  21.         getDiffrent3(list1,list2);  
  22.         //输出：getDiffrent3 total times 61763995  
  23.     }  
  24.     /** 
  25.      * 获取两个List的不同元素 
  26.      * @param list1 
  27.      * @param list2 
  28.      * @return 
  29.      */  
  30.     private static List<String> getDiffrent3(List<String> list1, List<String> list2) {  
  31.         long st = System.nanoTime();  
  32.         Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size());  
  33.         List<String> diff = new ArrayList<String>();  
  34.         for (String string : list1) {  
  35.             map.put(string, 1);  
  36.         }  
  37.         for (String string : list2) {  
  38.             Integer cc = map.get(string);  
  39.             if(cc!=null)  
  40.             {  
  41.                 map.put(string, ++cc);  
  42.                 continue;  
  43.             }  
  44.             map.put(string, 1);  
  45.         }  
  46.         for(Map.Entry<String, Integer> entry:map.entrySet())  
  47.         {  
  48.             if(entry.getValue()==1)  
  49.             {  
  50.                 diff.add(entry.getKey());  
  51.             }  
  52.         }  
  53.         System.out.println("getDiffrent3 total times "+(System.nanoTime()-st));  
  54.         return list1;  
  55.     }  
  56.   
  57.     /** 
  58.      * 获取两个List的不同元素 
  59.      * @param list1 
  60.      * @param list2 
  61.      * @return 
  62.      */  
  63.     private static List<String> getDiffrent2(List<String> list1, List<String> list2) {  
  64.         long st = System.nanoTime();  
  65.         list1.retainAll(list2);  
  66.         System.out.println("getDiffrent2 total times "+(System.nanoTime()-st));  
  67.         return list1;  
  68.     }  
  69.   
  70.     /** 
  71.      * 获取两个List的不同元素 
  72.      * @param list1 
  73.      * @param list2 
  74.      * @return 
  75.      */  
  76.     private static List<String> getDiffrent(List<String> list1, List<String> list2) {  
  77.         long st = System.nanoTime();  
  78.         List<String> diff = new ArrayList<String>();  
  79.         for(String str:list1)  
  80.         {  
  81.             if(!list2.contains(str))  
  82.             {  
  83.                 diff.add(str);  
  84.             }  
  85.         }  
  86.         System.out.println("getDiffrent total times "+(System.nanoTime()-st));  
  87.         return diff;  
  88.     }  
  89. }  
显然，这种方法大大减少耗时，是方法1的1/4，是方法2的1/40，这个性能的提升时相当可观的，但是，这不是最佳的解决方法，观察方法3我们只是随机取了一个list作为首次添加的标准，这样一旦我们的list2比list1的size大，则我们第二次put时的if判断也会耗时，做如下改进：
[java] view plain copy
 
 print?技术分享技术分享
  1. package com.czp.test;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.HashMap;  
  5. import java.util.List;  
  6. import java.util.Map;  
  7.   
  8. public class TestList {  
  9.   
  10.     public static void main(String[] args) {  
  11.         List<String> list1 = new ArrayList<String>();  
  12.         List<String> list2 = new ArrayList<String>();  
  13.         for (int i = 0; i < 10000; i++) {  
  14.             list1.add("test"+i);  
  15.             list2.add("test"+i*2);  
  16.         }  
  17.         getDiffrent(list1,list2);  
  18.         getDiffrent2(list1,list2);  
  19.         getDiffrent3(list1,list2);  
  20.         getDiffrent4(list1,list2);  
  21. //        getDiffrent total times 2789492240  
  22. //        getDiffrent2 total times 3324502695  
  23. //        getDiffrent3 total times 24710682  
  24. //        getDiffrent4 total times 15627685  
  25.     }  
  26.     /** 
  27.      * 获取两个List的不同元素 
  28.      * @param list1 
  29.      * @param list2 
  30.      * @return 
  31.      */  
  32.     private static List<String> getDiffrent4(List<String> list1, List<String> list2) {  
  33.         long st = System.nanoTime();  
  34.         Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size());  
  35.         List<String> diff = new ArrayList<String>();  
  36.         List<String> maxList = list1;  
  37.         List<String> minList = list2;  
  38.         if(list2.size()>list1.size())  
  39.         {  
  40.             maxList = list2;  
  41.             minList = list1;  
  42.         }  
  43.         for (String string : maxList) {  
  44.             map.put(string, 1);  
  45.         }  
  46.         for (String string : minList) {  
  47.             Integer cc = map.get(string);  
  48.             if(cc!=null)  
  49.             {  
  50.                 map.put(string, ++cc);  
  51.                 continue;  
  52.             }  
  53.             map.put(string, 1);  
  54.         }  
  55.         for(Map.Entry<String, Integer> entry:map.entrySet())  
  56.         {  
  57.             if(entry.getValue()==1)  
  58.             {  
  59.                 diff.add(entry.getKey());  
  60.             }  
  61.         }  
  62.         System.out.println("getDiffrent4 total times "+(System.nanoTime()-st));  
  63.         return diff;  
  64.           
  65.     }  
  66.     /** 
  67.      * 获取两个List的不同元素 
  68.      * @param list1 
  69.      * @param list2 
  70.      * @return 
  71.      */  
  72.     private static List<String> getDiffrent3(List<String> list1, List<String> list2) {  
  73.         long st = System.nanoTime();  
  74.         Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size());  
  75.         List<String> diff = new ArrayList<String>();  
  76.         for (String string : list1) {  
  77.             map.put(string, 1);  
  78.         }  
  79.         for (String string : list2) {  
  80.             Integer cc = map.get(string);  
  81.             if(cc!=null)  
  82.             {  
  83.                 map.put(string, ++cc);  
  84.                 continue;  
  85.             }  
  86.             map.put(string, 1);  
  87.         }  
  88.         for(Map.Entry<String, Integer> entry:map.entrySet())  
  89.         {  
  90.             if(entry.getValue()==1)  
  91.             {  
  92.                 diff.add(entry.getKey());  
  93.             }  
  94.         }  
  95.         System.out.println("getDiffrent3 total times "+(System.nanoTime()-st));  
  96.         return diff;  
  97.     }  
  98.   
  99.     /** 
  100.      * 获取连个List的不同元素 
  101.      * @param list1 
  102.      * @param list2 
  103.      * @return 
  104.      */  
  105.     private static List<String> getDiffrent2(List<String> list1, List<String> list2) {  
  106.         long st = System.nanoTime();  
  107.         list1.retainAll(list2);  
  108.         System.out.println("getDiffrent2 total times "+(System.nanoTime()-st));  
  109.         return list1;  
  110.     }  
  111.   
  112.     /** 
  113.      * 获取两个List的不同元素 
  114.      * @param list1 
  115.      * @param list2 
  116.      * @return 
  117.      */  
  118.     private static List<String> getDiffrent(List<String> list1, List<String> list2) {  
  119.         long st = System.nanoTime();  
  120.         List<String> diff = new ArrayList<String>();  
  121.         for(String str:list1)  
  122.         {  
  123.             if(!list2.contains(str))  
  124.             {  
  125.                 diff.add(str);  
  126.             }  
  127.         }  
  128.         System.out.println("getDiffrent total times "+(System.nanoTime()-st));  
  129.         return diff;  
  130.     }  
  131. }  
这里对连个list的大小进行了判断，小的在最后添加，这样会减少循环里的判断，性能又有了一定的提升，正如一位朋友所说，编程是无止境的，只要你认真去思考了，总会找到更好的方法！

非常感谢binglian的指正，针对List有重复元素的问题，做以下修正，首先明确一点，两个List不管有多少个重复，只要重复的元素在两个List都能找到，则不应该包含在返回值里面，所以在做第二次循环时，这样判断：如果当前元素在map中找不到，则肯定需要添加到返回值中，如果能找到则value++，遍历完之后diff里面已经包含了只在list2里而没在list2里的元素，剩下的工作就是找到list1里有list2里没有的元素，遍历map取value为1的即可：

[java] view plain copy
 
 print?技术分享技术分享
  1. package com.czp.test;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.HashMap;  
  5. import java.util.List;  
  6. import java.util.Map;  
  7.   
  8. public class TestList {  
  9.   
  10.     public static void main(String[] args) {  
  11.         List<String> list1 = new ArrayList<String>();  
  12.         List<String> list2 = new ArrayList<String>();  
  13.         for (int i = 0; i < 10000; i++) {  
  14.             list1.add("test"+i);  
  15.             list2.add("test"+i*2);  
  16.         }  
  17.         getDiffrent(list1,list2);  
  18.         getDiffrent3(list1,list2);  
  19.         getDiffrent5(list1,list2);  
  20.         getDiffrent4(list1,list2);  
  21.         getDiffrent2(list1,list2);  
  22.   
  23. //        getDiffrent3 total times 32271699  
  24. //        getDiffrent5 total times 12239545  
  25. //        getDiffrent4 total times 16786491  
  26. //        getDiffrent2 total times 2438731459  
  27.           
  28.     }  
  29.     /** 
  30.      * 获取两个List的不同元素 
  31.      * @param list1 
  32.      * @param list2 
  33.      * @return 
  34.      */  
  35.     private static List<String> getDiffrent5(List<String> list1, List<String> list2) {  
  36.         long st = System.nanoTime();  
  37.          List<String> diff = new ArrayList<String>();  
  38.          List<String> maxList = list1;  
  39.          List<String> minList = list2;  
  40.          if(list2.size()>list1.size())  
  41.          {  
  42.              maxList = list2;  
  43.              minList = list1;  
  44.          }  
  45.          Map<String,Integer> map = new HashMap<String,Integer>(maxList.size());  
  46.          for (String string : maxList) {  
  47.              map.put(string, 1);  
  48.          }  
  49.          for (String string : minList) {  
  50.              if(map.get(string)!=null)  
  51.              {  
  52.                  map.put(string, 2);  
  53.                  continue;  
  54.              }  
  55.              diff.add(string);  
  56.          }  
  57.          for(Map.Entry<String, Integer> entry:map.entrySet())  
  58.          {  
  59.              if(entry.getValue()==1)  
  60.              {  
  61.                  diff.add(entry.getKey());  
  62.              }  
  63.          }  
  64.         System.out.println("getDiffrent5 total times "+(System.nanoTime()-st));  
  65.         return diff;  
  66.           
  67.     }  
  68.     /** 
  69.      * 获取两个List的不同元素 
  70.      * @param list1 
  71.      * @param list2 
  72.      * @return 
  73.      */  
  74.     private static List<String> getDiffrent4(List<String> list1, List<String> list2) {  
  75.         long st = System.nanoTime();  
  76.         Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size());  
  77.         List<String> diff = new ArrayList<String>();  
  78.         List<String> maxList = list1;  
  79.         List<String> minList = list2;  
  80.         if(list2.size()>list1.size())  
  81.         {  
  82.             maxList = list2;  
  83.             minList = list1;  
  84.         }  
  85.         for (String string : maxList) {  
  86.             map.put(string, 1);  
  87.         }  
  88.         for (String string : minList) {  
  89.             Integer cc = map.get(string);  
  90.             if(cc!=null)  
  91.             {  
  92.                 map.put(string, ++cc);  
  93.                 continue;  
  94.             }  
  95.             map.put(string, 1);  
  96.         }  
  97.         for(Map.Entry<String, Integer> entry:map.entrySet())  
  98.         {  
  99.             if(entry.getValue()==1)  
  100.             {  
  101.                 diff.add(entry.getKey());  
  102.             }  
  103.         }  
  104.         System.out.println("getDiffrent4 total times "+(System.nanoTime()-st));  
  105.         return diff;  
  106.           
  107.     }  
  108.     /** 
  109.      * 获取两个List的不同元素 
  110.      * @param list1 
  111.      * @param list2 
  112.      * @return 
  113.      */  
  114.     private static List<String> getDiffrent3(List<String> list1, List<String> list2) {  
  115.         long st = System.nanoTime();  
  116.         Map<String,Integer> map = new HashMap<String,Integer>(list1.size()+list2.size());  
  117.         List<String> diff = new ArrayList<String>();  
  118.         for (String string : list1) {  
  119.             map.put(string, 1);  
  120.         }  
  121.         for (String string : list2) {  
  122.             Integer cc = map.get(string);  
  123.             if(cc!=null)  
  124.             {  
  125.                 map.put(string, ++cc);  
  126.                 continue;  
  127.             }  
  128.             map.put(string, 1);  
  129.         }  
  130.         for(Map.Entry<String, Integer> entry:map.entrySet())  
  131.         {  
  132.             if(entry.getValue()==1)  
  133.             {  
  134.                 diff.add(entry.getKey());  
  135.             }  
  136.         }  
  137.         System.out.println("getDiffrent3 total times "+(System.nanoTime()-st));  
  138.         return diff;  
  139.     }  
  140.   
  141.     /** 
  142.      * 获取连个List的不同元素 
  143.      * @param list1 
  144.      * @param list2 
  145.      * @return 
  146.      */  
  147.     private static List<String> getDiffrent2(List<String> list1, List<String> list2) {  
  148.         long st = System.nanoTime();  
  149.         list1.retainAll(list2);  
  150.         System.out.println("getDiffrent2 total times "+(System.nanoTime()-st));  
  151.         return list1;  
  152.     }  
  153.   
  154.     /** 
  155.      * 获取两个List的不同元素 
  156.      * @param list1 
  157.      * @param list2 
  158.      * @return 
  159.      */  
  160.     private static List<String> getDiffrent(List<String> list1, List<String> list2) {  
  161.         long st = System.nanoTime();  
  162.         List<String> diff = new ArrayList<String>();  
  163.         for(String str:list1)  
  164.         {  
  165.             if(!list2.contains(str))  
  166.             {  
  167.                 diff.add(str);  
  168.             }  
  169.         }  
  170.         System.out.println("getDiffrent total times "+(System.nanoTime()-st));  
  171.         return diff;  
  172.     }  
  173. }  

两个list取不同值


联系
我们