我正在处理一个大数据问题:我有一些大量的数组(~1M)，它们分布在大量文件(~1k)。数据经过组织，使得第 i 个文件包含所有数组的第 i 个条目。如果我的算法的总体成本由我需要打开的文件数量决定(假设一次只能打开一个文件)，是否有一种策略可以同时对所有数组进行就地排序，以便最小化总体成本？
请注意，数据太大，无法将所有内容存储在内存中，但将所有数组中的 ~10 条目存储在内存 中(即 10x1M 值)应该没有问题。
最佳答案
这个问题缺乏信息。没有提及数组是否已经自行排序。我将假设数组本身没有排序来回答。
The data is organized so that the ith file contains the ith entry of all arrays.
据此，我可以假设 -
file i
------------
arr1[i]
arr2[i]
arr3[i]
...
...
arrN[i] # N = ~1M
您提到数组的数量是
1M和文件数量1K，所以根据这个，没有数组将包含超过1K元素，否则将需要更多文件。每个文件包含
1M元素。
....but there should be no problem storing ~10 entries from all arrays in memory (i.e. 10x1M values).
因此，我们应该能够将文件的所有元素加载到内存中，因为它不会超过 1M元素。
因此将每个文件加载到内存中并对文件的元素进行排序。
然后申请K-Way Merge Algorithms使用 minheap 对 1K 进行排序保存已排序元素的文件。这一步需要c * 1M c 时加载到内存中的元素是小常数( c < 3 )。
如果您在理解 K-way 合并时遇到任何困难，请告诉我。
希望对你有帮助!
关于arrays - 对分布在多个文件中的 "slices"多个向量进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43245584/