提问人:Usman 提问时间:9/11/2023 更新时间:9/11/2023 访问量:29
外部合并排序的正确 SplitSize (Chunk) 应该是什么?
What should be the right SplitSize (Chunk) for a external merge sort?
问:
我正在使用外部合并排序算法的现有代码。
该算法必须能够处理大文件(即 10GB、20 GB 甚至更多) 可用内存可以是 15 GB 或 10GB(因为它必须在任何现代计算机上运行。所以我没有任何拥有 1 GB 或 2 GB RAM 的限制。
现有的 Snippet 代码如下。
public class ExternalMergeSortSplitOptions
{
/// Size of unsorted file (chunk) (in bytes)
public int FileSize { get; init; } = 2 * 1024 * 1024;
public char NewLineSeparator { get; init; } = '\n';
}
以下代码用于将整个大文件拆分为多个块。但是这个块的数量(将转换为未排序的文件)的数量太大,仅在拆分过程中就需要近 30-40 分钟。因此,使用指定的 Split.FileSize 拆分文件的现有策略是不合适的。
private async Task<IReadOnlyCollection<string>> SplitFile(
Stream sourceStream,
CancellationToken cancellationToken)
{
var fileSize = _options.Split.FileSize;
var buffer = new byte[fileSize];
var extraBuffer = new List<byte>();
var filenames = new List<string>();
var totalFiles = Math.Ceiling(sourceStream.Length / (double)_options.Split.FileSize); /// -> This line could generate 6K files if the provided size of the original file is 20 GB or similar....
await using (sourceStream)
{
var currentFile = 0L;
while (sourceStream.Position < sourceStream.Length)
{
...................
................................................
}
}
问:我们是否可以转换策略,以便代码可以计算合理范围内的文件数?(即通过要求 RAM 中的可用空间,然后相应地要求每个块的大小与可用 RAM 相当)。 谢谢
答:
0赞
rcgldr
9/11/2023
#1
2 MB 太小。文本文件的 GNU 排序默认为可用物理内存的 75% 左右。它是 C 代码,用于对指向记录的指针数组进行排序,用于创建一组排序的临时文件,对于指向记录的第二个指针数组,这不需要太多内存,因此 75% 的大部分内存用于文件缓冲区。我不知道是否可以在 C# 中做一些与此类似的事情,因此需要调整用于文件缓冲区的内存量。
GNU sort 对临时文件使用 K-way 合并,默认 K 为 16,用于硬盘驱动器。如果使用更快的 SSD 驱动器,K 可能应该更小。
由于所有选项,源代码很大(超过 4000 行)。
https://github.com/coreutils/coreutils/blob/master/src/sort.c
评论
Array.MaxLength