java - 比较大量字符串的最有效算法是什么？

Question

让我们取 2 个字符串数组列表

List<String> namesListA = new ArrayList<>(/*50 000 strings*/);
List<String> namesListB = new ArrayList<>(/*400 000 strings*/);

removeAll 方法似乎不起作用。之后:

namesListA.removeAll(namesListB);

namesListA.size() 仍然是 50000。编辑:输入数据不正确，它确实有效，但需要很长时间。

我写了下面的暴力破解代码:

boolean match;
    for (String stringA: namesListA)
    {
        match = false;
        for (String stringB: namesListB)
        {
            if (stringA.equals(stringB))
            {
                match = true;
                break;
            }
        }
        if (!match)
        {
            finallist.add(stringA);
        }
    }

但是要执行8个小时。是否有任何已知的搜索字符串的有效算法？喜欢按字母顺序对字符串进行排序，然后逐个字母搜索或类似的东西。

Answer 1

您可以将列表 namesListB 的元素放入一个新的 Set(最好是 HashSet)。那么调用 namesListA.removeAll(setFromListB); 会更有效，因为 ArrayList.removeAll 的实现调用了 Collection.contains()这在 Set (HashSet) 中比在 ArrayList (HashSet.contains()) 中更有效常数时间性能，而 ArrayList.contains() 具有线性性能。

无论如何，namesListA.removeAll(namesListB); 应该可以工作，如果 namesListA 没有改变，那么这两个列表没有共同的元素。

时间复杂度的估计(N = namesListA.length，M = namesListB.length):
从 namesListB 创建 HashSet:O(M)
调用 namesListA.removeAll(setListB):O(N * 1) = O(N)
总计:O(M + N)(可以写成 O(M)，因为 M>N，但我不确定)