将 1000 个文件合并为一个具有内存限制的排序文件 - 堆排序与桶排序
Merging 1000s of files into one sorted file with memory constraints - heap vs bucket sort
每个文件中以及所有文件中的编号都是唯一的。这是一种流行的方法（外部排序），当我们的计算机无法存储所有数据时，将 n 个文件合并为一个排序的文件：
- 对每个较小的文件进行排序
- 从每个文件中读取第一个元素
- 创建堆
- 当堆不为空时：
- 将最小元素写入最终文件
- 将较小文件（其元素已在上述步骤中写入主文件）中的下一个元素插入堆
虽然我明白这个算法如何帮助内存使用 - 涉及很多 I/O 开销。
另一种可能的方法是使用桶排序 - 特别是当数字均匀分布时：
- 创建 n 个桶 - (max_num-min_number)/number_of_elements_in_1_bucket
- 对于每个较小的文件：
- 读取文件
- 创建批量更新字典{bucket_number:[元素列表]}
- 将上述字典中的数据附加到相应的存储桶文件
- 字典 space 有限，因此每个较小的文件一次只能处理 100 个元素。所以重复以上两个步骤，直到我们用完当前文件元素
- 对于创建的每个存储桶文件
- 对每个桶中的数据进行排序
- 将所有文件附加到一个排序文件中
现在，我相信后一种方法在时间复杂度方面可能会稍微快一些或至少相当，但会为临时文件使用更多存储 space。这两种方法在 时间复杂度 上是否具有可比性，或者即使在多次 I/O 调用之后，第一种方法总是更好？我是否在第二种方法中遗漏了一些耗时的步骤，从而使其不太理想？
我的理解是反过来。如果数字在可预测的范围内具有可预测的分布，则桶排序会更快。 （对于基于比较的排序，在 O(n) 与 O(n log(n)) 的限制下。）更好的是，桶可以彼此独立地排序。这使得它们非常适合分布式排序。
每个文件中以及所有文件中的编号都是唯一的。这是一种流行的方法（外部排序），当我们的计算机无法存储所有数据时，将 n 个文件合并为一个排序的文件：
- 对每个较小的文件进行排序
- 从每个文件中读取第一个元素
- 创建堆
- 当堆不为空时：
- 将最小元素写入最终文件
- 将较小文件（其元素已在上述步骤中写入主文件）中的下一个元素插入堆
虽然我明白这个算法如何帮助内存使用 - 涉及很多 I/O 开销。
另一种可能的方法是使用桶排序 - 特别是当数字均匀分布时：
- 创建 n 个桶 - (max_num-min_number)/number_of_elements_in_1_bucket
- 对于每个较小的文件：
- 读取文件
- 创建批量更新字典{bucket_number:[元素列表]}
- 将上述字典中的数据附加到相应的存储桶文件
- 字典 space 有限，因此每个较小的文件一次只能处理 100 个元素。所以重复以上两个步骤，直到我们用完当前文件元素
- 对于创建的每个存储桶文件
- 对每个桶中的数据进行排序
- 将所有文件附加到一个排序文件中
现在，我相信后一种方法在时间复杂度方面可能会稍微快一些或至少相当，但会为临时文件使用更多存储 space。这两种方法在 时间复杂度 上是否具有可比性，或者即使在多次 I/O 调用之后，第一种方法总是更好？我是否在第二种方法中遗漏了一些耗时的步骤，从而使其不太理想？
我的理解是反过来。如果数字在可预测的范围内具有可预测的分布，则桶排序会更快。 （对于基于比较的排序，在 O(n) 与 O(n log(n)) 的限制下。）更好的是，桶可以彼此独立地排序。这使得它们非常适合分布式排序。