algorithm - 在不访问键值计数的情况下将键值对分成相等的列表

Question

我的问题简要说明:如果先验不知道任何键包含的值的数量，并且不能保存所有键(或它们的值的计数)同时存在于 RAM 中？

我的上下文问题:我有多个包含键/值对的文件，其中键是散列，值是出现给定散列的对象 ID 列表。相同的 key 在每个文件中出现零次或一次，并且给定的 key 经常出现在许多文件中。

我正在将这些文件读取到在计算集群中运行的多个工作程序中。每个 worker 都被分配了一个 key 子集。对于分配给工作人员的每个键，工作人员会累积出现在前面提到的任何键/值文件中的键的所有值。然后每个工作人员读取所有前面提到的文件，找到每个键的所有值，并将单个输出文件写入磁盘。

我面临的问题是，工作人员在分配给他们的键中累积的值数量大相径庭，因此他们的 RAM 要求非常不同(从低端的 33GB 到高端的 139GB)。现在，为了将 key 分配给 worker ，我对每个 key 进行了 sha1 哈希，如果 sha1(key) % total_number_of_workers == worker_id (其中 worker ID 是给定 worker 在所有 worker 中的索引位置)然后为工作人员分配给定的 key 。

有没有一种方法可以将 key 分配给工作人员，以帮助确保在节点之间更公平地分配 RAM 需求？其他人可以就此问题提供的任何建议将不胜感激!

---

如果其他人可能感兴趣，我将 Jim Mischel 在 Python 中描述的 k 向合并的简单实现放在一起 [ gist ].此实现不需要将所有文本文件同时保存在内存中，这对于大型数据集来说可能是不可能的。

Answer 1

这是一个简单的k-way merge .假设您有三个文件:

File 1     File 2     File 3
A=3        B=7        C=22
X=9        B=4        D=19
Q=33       Z=26       A=2
X=47       X=12       D=13

现在，您对这些文件进行排序:

Sorted1    Sorted2    Sorted3
A=3        B=7        A=2
Q=33       B=4        C=22
X=9        X=12       D=19
X=47       Z=26       D=13

您可以执行合并步骤并以单个文件结束:

A=3
A=2
B=7
B=4
C=22
D=19
D=13
Q=33
X=9
X=47
X=12
Z=26

然后扫描该文件，累积和写入值。

但是您可以一步完成合并和累加。毕竟，当您进行合并时，您是以排序的键顺序输出内容，因此您所要做的就是在输出步骤之前插入累积代码。

单个进程启动并创建一个优先级队列，其中包含每个文件的第一项。所以优先级队列将包含[A=3, B=7, A=2]。该程序从优先级队列中取出最小的键 A=3，并用第一个排序文件中的下一项刷新队列。队列现在包含 [Q=33,B=7,A=2]。

程序创建一个新数组，键为 A，包含值 [3]。然后它再次进入队列并读取最小值:A=2。它发现 key 等于它正在处理的 key ，因此它将数组更新为 [3,2]。队列从排序后的文件中刷新，因此现在它包含 [Q=33,B=7,C=22]。

程序再次从队列中获取最小的键值。这次是B，B不等于A，所以程序输出A,[3,2]，将当前key替换为B，将累加数组替换为[7] 。

这一直持续到没有更多项目要合并为止。

处理重新填充优先级队列的代码有点繁琐，但并不难。

另一种方法是使用操作系统的排序实用程序对文件进行排序和合并，然后编写一个简单的循环，线性遍历单个排序文件以累积值。