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

_FR>Привет,

_FR>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где

Считаю, проблема в том, что у тебя MergeFilesAsync работает за O(N*K), где N — общее количество строк в исходном файле, и K — количество чанков.
Потому что на каждую строку ты меняешь список items с помощью операций Insert/RemoveAt.

А должно работать за O(N * log K)

Вероятно, проверяющий запускал тест с большим количество чанков (с меньшей потребляемой памятью).

_FR>В целом как сделано: на вход программе сортировки подаётся путь к файлу и количество строк, на которые можно перед сортировкой разбить входной файл. Так мы можем подобрать, сколько памяти программа будет занимать.
_FR>Схематично, алгоритм такой: входной файл вычитывается PipeReader-ом: столько строк, сколько задано. Пока эти строки сохраняются в файл, начимаем вычитывать следующий буфер, дабы избежать простоя.
_FR>Затем открываем все созданные файлыб вычитываем по строке, сортируем, пишем в выходной файл меньшее значение и из этого файла вычитываем следующу строчку.

_FR>Буду брагодарем за объяснения, как это должно быть сделано правильно.

Сам алгоритм норм, но реализация не очень.

Кроме кривой реализации merge еще добавлю:
— смешаны отслеживание прогресса и сам алгоритм, я бы разделил (с помощью хуков, например)
— возможно, не стоит использовать async. Это усложняет реализацию, но, по-моему не дает значимых плюсов. Почти все время работы алгоритмы — работа с диском. Сама сортировка в памяти — единицы процентов
— я использовал генераторы (yield), алгоритм упрощается. см. http://rsdn.org/forum/dotnet/8339349.1

Автор: Буравчик
Дата: 19.08.22