外部合并排序的正确 SplitSize（块）应该是多少？

Question

我正在使用外部合并排序算法的现有代码。

该算法必须能够处理大文件（即 10GB、20GB 甚至更多） 可用内存可以是 15 GB 或 10GB（因为它必须在任何现代计算机上运行。所以我没有 1 GB 或 2 GB RAM 的任何限制）。

现有的代码片段如下。

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 的大小相同）。 谢谢

Answer 1

2 MB 太小了。 GNU 对文本文件的排序默认使用可用物理内存的 75% 左右。它是 C 代码，用于在初始阶段对指向记录的指针数组进行排序，从而创建一组已排序的临时文件，第二个指向记录的指针数组不需要太多内存，因此 75% 的内存中的大部分是用于文件缓冲区。我不知道是否可以在 C# 中执行与此等效的操作，因此需要调整文件缓冲区使用的内存量。

GNU 排序对临时文件使用 K 路合并，默认 K 为 16，适用于硬盘驱动器。如果使用更快的 SSD 驱动器，K 可能应该更小。

由于选项较多，源代码很大（超过 4000 行）。

https://github.com/coreutils/coreutils/blob/master/src/sort.c