Как сортировать и искать в очень большом файле, который не может быть загружен в память?

Question

В моем недавнем интервью меня спросили о поиске строки в очень большом файле, полном текстов, который не может быть загружен в основную / оперативную память. Например, файл размером 1 ТБ, когда объем оперативной памяти составляет 1 ГБ.

Я нашел много статей по этому поводу, мало, даже о стековом потоке, но не очень убедительно. Для ПОИСКА люди предлагают использовать кусок данных или читать файл построчно что-то в этом роде. Не удалось найти ответ о том, как читать строку за строкой без загрузки файла, и что, если строка поиска представлена ​​в нескольких чанках (какая-то часть строки в одном чанке, какая-то часть в другом чанке и может быть много чанков, если строка поиска довольно долго), на основании чего мы решаем размер куска. У меня много таких маленьких вопросов, потому что интервьюер задавал их.

Я полагаю, что это уже не гипотетический вопрос, поэтому, если кто-то действительно это реализовал или имеет справедливое представление об этом, поделитесь своими мыслями. Спасибо заранее.

Если возможно, предложите какой-нибудь алгоритм или код в 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);
    }
}