高效的找出兩個List中的不同元素

    如題有List<String> list和List<String> list兩個集合各有上萬個元素怎樣取出兩個集合中不同的元素？
   
方法:遍歷兩個集合
   
    package comczptest;import javautilArrayList;import javautilList;public class TestList {
   
    public static void main（String[] args） {
   
    List<String> list = new ArrayList<String>（）
   
    List<String> list = new ArrayList<String>（）
   
    for （int i = ; i < ; i++） {
   
    listadd（test+i）
   
    listadd（test+i*）
   
    }
   
    getDiffrent（listlist）
   
    //輸出total times
   
    }
   
    /**
   
    * 獲取連個List的不同元素
   
    * @param list
   
   
   
    * @return
   
    */
   
    private static List<String> getDiffrent（List<String> list List<String> list） {
   
    long st = SystemnanoTime（）
   
    List<String> diff = new ArrayList<String>（）
   
    for（String str:list）
   
    {
   
    if（！ntains（str））
   
    {
   
    diffadd（str）
   
    }
   
    }
   
    Systemoutprintln（total times +（SystemnanoTime（）st））
   
    return diff;
   
    }}
   
    千萬不要采用這種方法總共要循環的次數是兩個List的size相乘的積從輸出看耗時也是比較長的那麼我們有沒有其他的方法呢？當然有

   
方法:采用List提供的retainAll（）方法
   
    package comczptest;import javautilArrayList;import javautilList;public class TestList {
   
    public static void main（String[] args） {
   
    List<String> list = new ArrayList<String>（）
   
    List<String> list = new ArrayList<String>（）
   
    for （int i = ; i < ; i++） {
   
    listadd（test+i）
   
    listadd（test+i*）
   
    }
   
    getDiffrent（listlist）
   
    //輸出total times
   
    getDiffrent（listlist）
   
    //輸出getDiffrent total times
   
    }
   
    /**
   
    * 獲取連個List的不同元素
   
    * @param list
   
    * @param list
   
    * @return
   
    */
   
    private static List<String> getDiffrent（List<String> list List<String> list） {
   
    long st = SystemnanoTime（）
   
    listretainAll（list）
   
    Systemoutprintln（getDiffrent total times +（SystemnanoTime（）st））
   
    return list;
   
    }
   
    /**
   
    * 獲取連個List的不同元素
   
    * @param list
   
    * @param list
   
    * @return
   
    */
   
    private static List<String> getDiffrent（List<String> list List<String> list） {
   
    long st = SystemnanoTime（）
   
    List<String> diff = new ArrayList<String>（）
   
    for（String str:list）
   
    {
   
    if（！ntains（str））
   
    {
   
    diffadd（str）
   
    }
   
    }
   
    Systemoutprintln（getDiffrent total times +（SystemnanoTime（）st））
   
    return diff;
   
    }}
   

    很遺憾這種方式雖然只要幾行代碼就搞定但是這個卻更耗時查看retainAll（）的源碼
   
    public boolean retainAll（Collection<?> c） {
   
    boolean modified = false;
   
    Iterator<E> e = iterator（）
   
    while （ehasNext（）） {
   
    if （！ntains（enext（））） {
   
    eremove（）
   
    modified = true;
   
    }
   
    }
   
    return modified;
   
    }
   
    無需解釋這個耗時是必然的那麼我們還有沒有更好的辦法呢？仔細分析以上兩個方法中我都做了mXn次循環其實完全沒有必要循環這麼多次我們的需求是找出兩個List中的不同元素那麼我可以這樣考慮用一個map存放lsit的所有元素其中的key為lsit的各個元素value為該元素出現的次數接著把list的所有元素也放到map裡如果已經存在則value加最後我們只要取出map裡value為的元素即可這樣我們只需循環m+n次大大減少了循環的次數
   
    package comczptest;import javautilArrayList;import javautilHashMap;import javautilList;import javautilMap;public class TestList {
   
    public static void main（String[] args） {
   
    List<String> list = new ArrayList<String>（）
   
    List<String> list = new ArrayList<String>（）
   
    for （int i = ; i < ; i++） {
   
    listadd（test+i）
   
    listadd（test+i*）
   
    }
   
    getDiffrent（listlist）
   
    //輸出total times
   
    getDiffrent（listlist）
   
    //輸出getDiffrent total times
   
    getDiffrent（listlist）
   
    //輸出getDiffrent total times
   
    }
   
    /**
   
    * 獲取連個List的不同元素
   
    * @param list
   
    * @param list
   
    * @return
   
    */
   
    private static List<String> getDiffrent（List<String> list List<String> list） {
   
    long st = SystemnanoTime（）
   
    Map<StringInteger> map = new HashMap<StringInteger>（listsize（）+listsize（））
   
    List<String> diff = new ArrayList<String>（）
   
    for （String string : list） {
   
    mapput（string ）
   
    }
   
    for （String string : list） {
   
    Integer cc = mapget（string）
   
    if（cc!=null）
   
    {
   
    mapput（string ++cc）
   
    continue;
   
    }
   
    mapput（string ）
   
    }
   
    for（MapEntry<String Integer> entry:mapentrySet（））
   
    {
   
    if（entrygetValue（）==）
   
    {
   
    diffadd（entrygetKey（））
   
    }
   
    }
   
    Systemoutprintln（getDiffrent total times +（SystemnanoTime（）st））
   
    return list;
   
    }
   
    /**
   
    * 獲取連個List的不同元素
   
    * @param list
   
    * @param list
   
    * @return
   
    */
   
    private static List<String> getDiffrent（List<String> list List<String> list） {
   
    long st = SystemnanoTime（）
   
    listretainAll（list）
   
    Systemoutprintln（getDiffrent total times +（SystemnanoTime（）st））
   
    return list;
   
    }
   
    /**
   
    * 獲取連個List的不同元素
   
    * @param list
   
    * @param list
   
    * @return
   
    */
   
    private static List<String> getDiffrent（List<String> list List<String> list） {
   
    long st = SystemnanoTime（）
   
    List<String> diff = new ArrayList<String>（）
   
    for（String str:list）
   
    {
   
    if（！ntains（str））
   
    {
   
    diffadd（str）
   
    }
   
    }
   
    Systemoutprintln（getDiffrent total times +（SystemnanoTime（）st））
   
    return diff;
   
    }}
   

    顯然這種方法大大減少耗時是方法的/是方法的/這個性能的提升時相當可觀的但是這不是最佳的解決方法觀察方法我們只是隨機取了一個list作為首次添加的標准這樣一旦我們的list比list的size大則我們第二次put時的if判斷也會耗時做如下改進
   
    package comczptest;import javautilArrayList;import javautilHashMap;import javautilList;import javautilMap;public class TestList {
   
    public static void main（String[] args） {
   
    List<String> list = new ArrayList<String>（）
   
    List<String> list = new ArrayList<String>（）
   
    for （int i = ; i < ; i++） {
   
    listadd（test+i）
   
    listadd（test+i*）
   
    }
   
    getDiffrent（listlist）
   
    getDiffrent（listlist）
   
    getDiffrent（listlist）
   
    getDiffrent（listlist）//
   
    getDiffrent total times //
   
    getDiffrent total times //
   
    getDiffrent total times //
   
    getDiffrent total times
   
    }
   
    /**
   
    * 獲取連個List的不同元素
   
    * @param list
   
    * @param list
   
    * @return
   
    */
   
    private static List<String> getDiffrent（List<String> list List<String> list） {
   
    long st = SystemnanoTime（）
   
    Map<StringInteger> map = new HashMap<StringInteger>（listsize（）+listsize（））
   
    List<String> diff = new ArrayList<String>（）
   
    List<String> maxList = list;
   
    List<String> minList = list;
   
    if（listsize（）>listsize（））
   
    {
   
    maxList = list;
   
    minList = list;
   
    }
   
    for （String string : maxList） {
   
    mapput（string ）
   
    }
   
    for （String string : minList） {
   
    Integer cc = mapget（string）
   
    if（cc!=null）
   
    {
   
    mapput（string ++cc）
   
    continue;
   
    }
   
    mapput（string ）
   
    }
   
    for（MapEntry<String Integer> entry:mapentrySet（））
   
    {
   
    if（entrygetValue（）==）
   
    {
   
    diffadd（entrygetKey（））
   
    }
   
    }
   
    Systemoutprintln（getDiffrent total times +（SystemnanoTime（）st））
   
    return diff;
   
    }
   
    /**
   
    * 獲取連個List的不同元素
   
    * @param list
   
    * @param list
   
    * @return
   
    */
   
    private static List<String> getDiffrent（List<String> list List<String> list） {
   
    long st = SystemnanoTime（）
   
    Map<StringInteger> map = new HashMap<StringInteger>（listsize（）+listsize（））
   
    List<String> diff = new ArrayList<String>（）
   
    for （String string : list） {
   
    mapput（string ）
   
    }
   
    for （String string : list） {
   
    Integer cc = mapget（string）
   
    if（cc!=null）
   
    {
   
    mapput（string ++cc）
   
    continue;
   
    }
   
    mapput（string ）
   
    }
   
    for（MapEntry<String Integer> entry:mapentrySet（））
   
    {
   
    if（entrygetValue（）==）
   
    {
   
    diffadd（entrygetKey（））
   
    }
   
    }
   
    Systemoutprintln（getDiffrent total times +（SystemnanoTime（）st））
   
    return diff;
   
    }
   
    /**
   
    * 獲取連個List的不同元素
   
    * @param list
   
    * @param list
   
    * @return
   
    */
   
    private static List<String> getDiffrent（List<String> list List<String> list） {
   
    long st = SystemnanoTime（）
   
    listretainAll（list）
   
    Systemoutprintln（getDiffrent total times +（SystemnanoTime（）st））
   
    return list;
   
    }
   
    /**
   
    * 獲取連個List的不同元素
   
    * @param list
   
    * @param list
   
    * @return
   
    */
   
    private static List<String> getDiffrent（List<String> list List<String> list） {
   
    long st = SystemnanoTime（）
   
    List<String> diff = new ArrayList<String>（）
   
    for（String str:list）
   
    {
   
    if（！ntains（str））
   
    {
   
    diffadd（str）
   
    }
   
    }
   
    Systemoutprintln（getDiffrent total times +（SystemnanoTime（）st））
   
    return diff;
   
    }}
   
    這裡對連個list的大小進行了判斷小的在最後添加這樣會減少循環裡的判斷性能又有了一定的提升正如一位朋友所說編程是無止境的只要你認真去思考了總會找到更好的方法！

From:http://tw.wingwit.com/Article/program/Java/hx/201311/27046.html