两个数据量很大的集合求差集的高效方法

Question

如题，两个集合如 List<String>，每个集合的数据量可能在 50-100w之间，如何 高效的计算出 list-1 diff list-2 的结果，耗时 以及内存占用 尽可能优

可以使用任何一切手段，如 调用脚本等

Answer 1

在一楼的基础上 用多线程 对集合分块剔除 最后在合并结果 只要线程够多 快到你无法想象
其次 用底层语言 机器指令最好
硬件方面 如果一台不行 加机器 加内存 加cpu 还不行 考虑大数据方面吧 终极方案 干掉出问题的人

Answer 2

方法一

如果你内存足够大，那可以先将一个列表读入集合s1中，遍历第二个列表，准备一个空集合s2，对于每一个元素，判断是否在s1，不在则加入s2，在则从s1中删除该元素。遍历结束后，s1中的元素和s2中的元素分别是两个列表独立存在的元素，也就是两个列表之差异。

方法二

如果不想占用太多内存，假设数据存在文件中每次只能同时去除一小部分放到内存，那就得牺牲一点时间复杂度。
首先归并升序排序两个列表，可以只需要很小内存即可完成。
然后双指针读取文件，有序情况下很容易判断出两个列表的差异。

假设两个列表长度分别为m、n，方法一时间复杂度是 O(m + n)，但是占用了大量内存。
方法二时间复杂度主要是排序的复杂度，O(m log m) + O(n log n), 占用内存可以非常小。

Answer 3

不知道你的目标性能是多少？如果是10毫秒以下，估计你可能要寻找某个独门秘籍。如果是100毫秒左右，看字符串的大小，一般情况下，如果用set去过滤，100毫秒内应该可以处理完，下面是在我自己笔记本的性能测试结果：

@Test
public void test_1010000038638664() {
    int size = 1000_000;
    List<String> list1 = new ArrayList<>(1000_000);
    List<String> list2 = new ArrayList<>(1000_000);

    // 准备测试数据
    String str = "kdajfoeiajflsajf3ijfalsjfa;lsdlfkjioawjlsdf";

    for (int i = 0; i < size; i++) {
        if (i % 3 == 0) {
            list1.add(str + i);
            list2.add(str + i);
        } else {
            list1.add(str + i);
            list2.add(i + str + i);
        }
    }

    // 用Set来过滤和测试性能
    final Set<String> set = new HashSet<>(list2);
    List<String> result = new ArrayList<>();
    long startTime = System.currentTimeMillis();

    for (String v : list1) {
        if (!set.contains(v)) {
            result.add(v);
        }
    }

    System.out.println("Took: " + (System.currentTimeMillis() - startTime) + "ms. size: " + result.size());
    // Took: 96ms. size: 666666
    
    // 如果还想更快，可以试一下parallel stream
    startTime = System.currentTimeMillis();
    result = list1.parallelStream().filter(it -> !set.contains(it)).collect(Collectors.toList());

    System.out.println("Took: " + (System.currentTimeMillis() - startTime) + "ms. size: " + result.size());
    // Took: 64ms. size: 666666
}

Answer 4

不管怎么样你已经得到两个 List 对象了，它们再怎么大都已经在内存里了，所以直接用 removeAll() 就好。

Answer 5

public List<String> complement(List<String> l1, List<String> l2) {
    HashSet<String> s2 = new HashSet<>(l2);
    l1.forEach(s2::remove);
    return new ArrayList<>(s2);
}

Answer 6

推荐google的guava,Sets.difference(set1,set2)即可，既然是求差集，应该优先排除重复元素

Answer 7

如果对于结果的准确性要求不是很高的话，可以使用布隆过滤器。
布隆过滤器-维基百科

Answer 8

首先必须用到的思想肯定是比较，在这个基础上考虑怎么比较。参考数据库左右连接的实现，可以取长度小的集合作为驱动表，然后遍历驱动表中的每个元素去判断在另一个集合中是否存在，而另一个元素则可以使用索引提高查询效率，可以考虑将这个集合转换为HashSet

Answer 9

可以试试使用 MapReduce 的思想。