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

kute
  • 471

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

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

回复
阅读 1.3k
9 个回答

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

方法一

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

方法二

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

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

不知道你的目标性能是多少?如果是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
}

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

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

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

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

可以试试使用 MapReduce 的思想。

你知道吗?

宣传栏