收集添加和删除元素时的代码改进

Question

我制作了一个小程序用于测试，我在其中收集用于添加和删除的元素。下面是测试用例列表，其中“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("......................................");
    }
}

我写这篇文章的原因是，我觉得在迭代和添加到集合添加和删除时，这段代码可以写得更好（例如，执行得更快）。有什么建议吗？

Answer 1

一个简单的解决方案是

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 的解决方案，否则。

收集添加和删除元素时的代码改进

code improvement when collecting elements for add and removal

java

algorithm

collections

refactoring