如何在无法加载到内存的巨大文件中进行排序和搜索？

Question

在最近的采访中，有人问我如何对无法加载到主/ RAM内存中的非常大的文件进行排序和搜索。例如，当RAM为1gb时，文件大小为1tb。

我发现了很多有关此的文章，即使是关于stackoverflow的文章也很少，但是没有多少说服力。对于排序，人们说使用合并排序，而对于搜索则使用数据块或逐行读取文件之类的东西。即使合并的数据块大于RAM，也找不到答案。在搜索的情况下，如何在不加载文件的情况下逐行读取，以及如果搜索字符串出现在多个块中，该如何确定块大小。我有很多这样的小问题，因为面试官也问过同样的问题。

我的上下文是在C＃.Net中找到一些算法来执行排序和搜索。

我相信这不再是假设的问题，因此，凡是已实际实施或对此有明确想法的人，请分享您的想法。提前谢谢了。

Answer 1

对于大文件，您可以使用memorymappedfile：

https://docs.microsoft.com/en-us/dotnet/api/system.io.memorymappedfiles.memorymappedfile?view=netframework-4.8

来自msdn的示例：

using System;
using System.IO;
using System.IO.MemoryMappedFiles;
using System.Runtime.InteropServices;

class Program
{
    static void Main(string[] args)
    {
        long offset = 0x10000000; // 256 megabytes
        long length = 0x20000000; // 512 megabytes

        // Create the memory-mapped file.
        using (var mmf = MemoryMappedFile.CreateFromFile(@"c:\ExtremelyLargeImage.data", FileMode.Open,"ImgA"))
        {
            // Create a random access view, from the 256th megabyte (the offset)
            // to the 768th megabyte (the offset plus length).
            using (var accessor = mmf.CreateViewAccessor(offset, length))
            {
                int colorSize = Marshal.SizeOf(typeof(MyColor));
                MyColor color;

                // Make changes to the view.
                for (long i = 0; i < length; i += colorSize)
                {
                    accessor.Read(i, out color);
                    color.Brighten(10);
                    accessor.Write(i, ref color);
                }
            }
        }
    }
}

public struct MyColor
{
    public short Red;
    public short Green;
    public short Blue;
    public short Alpha;

    // Make the view brighter.
    public void Brighten(short value)
    {
        Red = (short)Math.Min(short.MaxValue, (int)Red + value);
        Green = (short)Math.Min(short.MaxValue, (int)Green + value);
        Blue = (short)Math.Min(short.MaxValue, (int)Blue + value);
        Alpha = (short)Math.Min(short.MaxValue, (int)Alpha + value);
    }
}