code improvement when collecting elements for add and removal-CodePudding

I made a little program for testing, where I collect elements for add and removal. Below is a list of the test cases, where "current" and "new" are given parameters, and sign "=>" is expected result of add and remove collection:

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]

Below is my code which works fine with expected results above:

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("......................................");
    }
}

Reason why I am writing, is that I am under impression that this code when iterating and adding to collections add and remove, could be written better (eg. perform faster). Any suggestions?

CodePudding user response：

A simple solution would be

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

but, like your original approach, it has a high time complexity, O(n×m), which means, it will be very inefficient when both lists are very large. But it may run with reasonable performance for a lot of scenarios.

If you have to consider the possibility that both lists can be large, a solution running in linear time would be

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);
}

If you really need the maximum performance for all scenarios, you may set a threshold for currentCodes.size() * newCodes.size(), use the short-cut for zero, the plain ArrayList operation when the product is below the threshold and the HashSet based solution otherwise.