外部合并排序的正确 SplitSize (Chunk) 应该是什么?

What should be the right SplitSize (Chunk) for a external merge sort?

提问人:Usman 提问时间:9/11/2023 更新时间:9/11/2023 访问量:29

问:

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

该算法必须能够处理大文件(即 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 相当)。 谢谢

C# IO 合并排序

评论

0赞 Ralf 9/11/2023
您至少可以控制整个 PC 吗?所以你知道那台机器上没有同时运行其他东西吗?如果没有,请不要假设您可以依靠免费的RAM测量来展望未来。为了便于实现和安全并发使用,您可能会争夺从已安装的 RAM 派生的值减去其他进程使用的可用余量,并查看您的算法,如果实现对某个 MIN 大小有偏好,并且更多的 RAM 只会略有帮助。
0赞 Ralf 9/11/2023
因此,试着找到一个最佳点,在那里你最终不会主要使用交换文件,并尝试成为一个不妨碍其他进程有效运行的好公民。
0赞 Usman 9/11/2023
因此,我们无法执行动态和自动计算来制作用于将大文件拆分为较小文件的块大小?
0赞 JonasH 9/11/2023
您是否在问一次可以安全地将多少内容加载到内存中而不会引起交换?请参阅如何获取可用系统内存的大小,其中介绍了如何获取总 RAM 和可用 RAM。请注意,数组中的项数有一些固有的限制,因此为了简单起见,您可以只使用 。Array.MaxLength

答:

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