javascript - 比较两个巨大对象数组的最有效方法

Question

我想比较两个巨大的数组，我正在分批读取这两个数组(每次从每个数组中获取 10 个对象)。完成读取这两个数组后，我想要以下数据(两个巨大数组之间的交集 - 对象仅存在于第一个数组中 - 对象仅存在于第二个数组中)。这样做的最佳做法是什么？

小规模的例子:

令 arr1 = [obj1, obj2, obj3, obj4, obj5, obj6, obj7];

让 arr2 = [obj7, obj2, obj5, obj1, obj9, obj8];

然后我会批量读取两个数组(每次两个元素):

第一次循环

->obj2是相互的

->obj1只存在于arr1中

->obj7只存在于arr2中

这里的问题，在我完成对整个数组的循环以获得正确结果之前，这不是最终结果:

相互对象是obj1,obj2,obj5,obj7

arr1中的对象只有obj3,obj4,obj6

arr2中的对象只有obj8,obj9

注意:我必须分批读取数组，因为它们太大了。

Answer 1

为了有效地比较数组，您需要以某种方式对它们进行排序。无论数组是否太大而无法放入内存，都是如此。

通常，有两种选择:要么对每个数组中的对象进行排序并按顺序比较它们，要么对每个数组中的对象进行散列并与散列映射进行比较。

每种方法都有处理太大而无法放入内存的数据的技术。对于排序，有不受内存大小限制的“外部”排序算法，以及用于比较的简单数据流。对于散列，您可以将数据(根据散列)划分为小到足以在内存中处理的 bin。

---

举个例子，考虑一下这个类似 Python 的伪代码，用于对数据项进行哈希分级:

// split data into bins
files = []
for i in 0 .. N-1:
    files.push_back(open_for_write("{filename}_bin{i}"))
for item in read_items(open_for_read(filename)):
    bin = item.hash() mod N
    write_item(item, files[bin])

您可以对两个输入文件执行此操作，然后通过 bin 处理它们:

// compare by bin
outfile = open_for_write(out_filename)
for i in 0 .. N-1:
    items = new_set()
    for item in read_items(open_for_read("{in_filename_1}_bin{i}")):
        items.insert(item)
    for item in read_items(open_for_read("{in_filename_2}_bin{i}")):
        if item in items:
            write_item(item, outfile)