Информация об изменениях

Сообщение Re: Как правильно сортировать содержимое больших файлов? от 02.09.2022 0:48

Изменено 02.09.2022 11:32 gandjustas

Старый текст
Новый текст
Разница

Re: Как правильно сортировать содержимое больших файлов?

Здравствуйте, _FRED_, Вы писали:

Внезапно задачка очень интересная получилась.

Сделал сначала наивное решение с асинхронным IO как полагается. Получилось в 2 раза медленнее вашего. Начал "оптимизировать" переводя все на работу с Memory и Span вместо string. Кроме того распараллелил IO с сортировкой, добавил MemoryPool чтобы уменьшить аллокации.
Смог сделать на решение, которое было на 15% медленнее вашего. Причем ускорилась фаза разбиения, а слияние почти ничего не выиграло.

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

Разбиение на куски

Encoding encoding;
List<string> tempFiles;
using (var reader = new StreamReader(file, true))
{
    encoding = reader.CurrentEncoding;

    tempFiles = reader
        .EnumerateLines()
        .Chunk(chunkSize)
        .Select(chunk => {
            Array.Sort(chunk, comparer);
            var tempFileName = Path.GetTempFileName();
            File.WriteAllLines(tempFileName, chunk);
            return tempFileName;
        }).ToList();

}

public static IEnumerable<string> EnumerateLines(this StreamReader reader)
{            
    while (!reader.EndOfStream)
    {
        yield return reader.ReadLine()!;
    }
}

Объединение кусков:

var files = tempFiles
    .Select(f => File.OpenText(f))
    .ToList();
File.WriteAllLines(file, files.Select(f => f.EnumerateLines()).MergeLines(comparer), encoding);
files.ForEach(f => f.Dispose());
tempFiles.ForEach(f => File.Delete(f));

public static IEnumerable<string> MergeLines(this IEnumerable<IEnumerable<string>> sources, IComparer<string> comparer)
{
    var enumerators = ( from source in sources
                        let e = source.GetEnumerator()
                        where e.MoveNext()
                        select e ).ToList();

    while (enumerators.Any())
    {
        var min = enumerators.MinBy(e => e.Current, comparer);
        yield return min.Current;
        if (!min.MoveNext())
        { 
            enumerators.Remove(min);
            min.Dispose();
        }
    }
}

Внезапно оно показало лишь немного проиграло вашему коду, но значительно проиграло коду на питоне.
Далее я сделал две вещи: добавил .AsParallel() в фазу разбиения, чтобы чанки разбивались и записывались в несколько потоков и поменял реализацию MergeLines на использование PriorityQueue.

Обогнал вашу версию, работает примерно как версия на питоне. Полный код тут: https://github.com/gandjustas/HugeFileSort

Много нового для себя узнал:
1) async медленный, не надо все подряд делать async, особенно в консольном приложении.
2) Диски достаточно быстрые, чтобы программа которая пишет 50-100мб\сек упиралась в скорость работы кода, а не в IO.
3) Алгоримты рулят. У меня было подозрение что поиск наименьшего значения из итераторов медленно работает, но я не думал что замена на PriorityQueue ускорит слияние почти в три раза.
4) Обогнать StreamReader\StreamWriter можно, но смысла нет, это не дает заметного прироста
5) Строки это дорого, особенно когда они влезают в ОП.

Re: Как правильно сортировать содержимое больших файлов?

Encoding encoding;
List<string> tempFiles;
using (var reader = new StreamReader(file, true))
{
    encoding = reader.CurrentEncoding;

    tempFiles = reader
        .EnumerateLines()
        .Chunk(chunkSize)
        .Select(chunk => {
            Array.Sort(chunk, comparer);
            var tempFileName = Path.GetTempFileName();
            File.WriteAllLines(tempFileName, chunk);
            return tempFileName;
        }).ToList();

}

public static IEnumerable<string> EnumerateLines(this StreamReader reader)
{            
    while (!reader.EndOfStream)
    {
        yield return reader.ReadLine()!;
    }
}

Объединение кусков:

var files = tempFiles
    .Select(f => File.OpenText(f))
    .ToList();
File.WriteAllLines(file, files.Select(f => f.EnumerateLines()).MergeLines(comparer), encoding);
files.ForEach(f => f.Dispose());
tempFiles.ForEach(f => File.Delete(f));

public static IEnumerable<string> MergeLines(this IEnumerable<IEnumerable<string>> sources, IComparer<string> comparer)
{
    var enumerators = ( from source in sources
                        let e = source.GetEnumerator()
                        where e.MoveNext()
                        select e ).ToList();

    while (enumerators.Any())
    {
        var min = enumerators.MinBy(e => e.Current, comparer);
        yield return min.Current;
        if (!min.MoveNext())
        { 
            enumerators.Remove(min);
            min.Dispose();
        }
    }
}