收集添加和洗掉元素時的代碼改進

我制作了一個用于測驗的小程式，在那里我收集元素以進行添加和洗掉。下面是測驗用例串列，其中“current”和“new”是給定引數，符號“=>”是添加和洗掉集合的預期結果：

current[]                  ; new[code1,code2]  => add[code1,code2]
current[code1,code2]       ; new[]             => remove[code1,code2]
current[code1,code2]       ; new[code3]        => remove[code1,code2],add[code3]
current[code1,code2,code3] ; new[code1,code2]  => remove[code3]
current[code1,code2]       ; new[code1,code3]  => remove[code2],add[code3]

下面是我的代碼，它可以很好地滿足上述預期結果：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        List<String> currentList = new ArrayList<>();
        List<String> newList = new ArrayList<>();

        currentList.clear();
        newList.clear();
        newList.addAll(Arrays.asList("code1", "code2"));
        test(currentList, newList);

        currentList.clear();
        newList.clear();
        currentList.addAll(Arrays.asList("code1", "code2"));
        test(currentList, newList);

        currentList.clear();
        newList.clear();
        currentList.addAll(Arrays.asList("code1", "code2"));
        newList.addAll(Arrays.asList("code3"));
        test(currentList, newList);

        currentList.clear();
        newList.clear();
        currentList.addAll(Arrays.asList("code1", "code2", "code3"));
        newList.addAll(Arrays.asList("code1", "code2"));
        test(currentList, newList);

        currentList.clear();
        newList.clear();
        currentList.addAll(Arrays.asList("code1", "code2"));
        newList.addAll(Arrays.asList("code1", "code3"));
        test(currentList, newList);
    }

    // Test cases:
    // current[]                  ; new[code1,code2]  => add[code1,code2]
    // current[code1,code2]       ; new[]             => remove[code1,code2]
    // current[code1,code2]       ; new[code3]        => remove[code1,code2],add[code3]
    // current[code1,code2,code3] ; new[code1,code2]  => remove[code3]
    // current[code1,code2]       ; new[code1,code3]  => remove[code2],add[code3]
    public static void test(List<String> currentCodes, List<String> newCodes) {
        System.out.println("current"   currentCodes   " ; new"   newCodes);

        List<String> codesToRemove = new ArrayList<>();
        for (String currentCode : currentCodes) {
            if (!newCodes.contains(currentCode)) {
                // just a note: call some service
                codesToRemove.add(currentCode);
            }
        }

        List<String> codesToAdd = new ArrayList<>();
        for (String newCode : newCodes) {
            if (!currentCodes.contains(newCode)) {
                // just a note: call some service
                codesToAdd.add(newCode);
            }
        }

        System.out.println("removeResult"   codesToRemove);
        System.out.println("addResult"   codesToAdd);
        System.out.println("......................................");
    }
}

我之所以寫作，是因為我覺得這段代碼在迭代和添加到集合添加和洗掉時可以寫得更好（例如，執行得更快）。有什么建議？

uj5u.com熱心網友回復：

一個簡單的解決方案是

List<String> codesToRemove = new ArrayList<>(currentCodes);
codesToRemove.removeAll(newCodes);
List<String> codesToAdd = new ArrayList<>(newCodes);
codesToAdd.removeAll(currentCodes);

但是，就像您原來的方法一樣，它具有很高的時間復雜度 O(n×m)，這意味著當兩個串列都非常大時，它的效率會非常低。但它可能會在很多場景下以合理的性能運行。

如果您必須考慮兩個串列都可能很大的可能性，則在線性時間內運行的解決方案將是

List<String> codesToRemove, codesToAdd;

if(currentCodes.isEmpty() || newCodes.isEmpty()) { // short-cut
    codesToRemove = currentCodes;
    codesToAdd = newCodes;
}
else {
    HashSet<String> set = new LinkedHashSet<>(currentCodes);
    codesToAdd = new ArrayList<>();
    for(String newObj: newCodes) if(!set.remove(newObj)) codesToAdd.add(newObj);
    codesToRemove = new ArrayList<>(set);
}

如果你真的需要所有場景的最大性能，你可以設定一個閾值currentCodes.size() * newCodes.size()，使用捷徑為零，ArrayList產品低于閾值時使用普通操作，HashSet否則使用基于解決方案。

標籤：爪哇 算法 收藏 重构

上一篇：數一數漂亮的數字

下一篇：求鏈表第一個和最后一個元素的最大和