比较两个大型对象数组的最有效方法

Question

比较两个大型对象数组的最有效方法

javascriptarraysalgorithmdata-structures

3

我想比较两个巨大的数组，我会分批次读取这两个数组（每次从每个数组中获取10个对象）。在完全读取这两个数组之后，我想得到以下数据（两个巨大数组之间的交集 - 仅存在于第一个数组中的对象 - 仅存在于第二个数组中的对象）。最佳实践是什么？

小规模示例： let arr1 = [obj1，obj2，obj3，obj4，obj5，obj6，obj7]; let arr2 = [obj7，obj2，obj5，obj1，obj9，obj8];

然后我会分批次读取这两个数组（每次读取两个元素）：

第一轮循环

-> obj2是相同的

-> obj1仅存在于arr1中

-> obj7仅存在于arr2中

问题在于，直到我完成对整个数组的循环以获得正确的结果之前，这并不是最终结果，即：

共同对象是obj1、obj2、obj5、obj7

仅存在于arr1中的对象是obj3、obj4、obj6

仅存在于arr2中的对象是obj8、obj9

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

- Walid Ahmed

换句话说，您想要交集（即您不想要仅出现在两个集合中之一的对象已经包含在交集的定义中 = “留在两个集合中的对象”）。 - Alberto Sinigaglia

什么类型的对象？ - Mister Jojo

常规 JSON 对象 - Walid Ahmed

查看类似 lodash 的方法：https://dev59.com/sF0b5IYBdhLWcg3wUP4X - 4givN

它无法将数组分批读取。 - Walid Ahmed

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- comingstorm · Accepted Answer

为了高效比较数组，您需要以某种方式对其进行排序。无论这些数组是否过大而无法放入内存，这都是必要的。

传统方法有两种选择：将每个数组中的对象排序并按顺序进行比较，或者将每个数组中的对象哈希并使用哈希映射进行比较。

每种方法都有处理过大数据的技巧。对于排序，有“外部”排序算法不受内存大小限制，并且可以使用简单的数据流进行比较。对于哈希，可以将数据（根据哈希）划分为足够小以在内存中处理的容器。

例如，考虑以下类似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)