Как правильно сортировать содержимое больших файлов?
От: _FRED_ Черногория
Дата: 21.08.22 11:11
Оценка:
Привет,

Ещё в прошлом году дали в одной компании тестовое задание, которое мне показалось интересным сделать — во-первых, я на программиста не учился и сортировку файлов слиянием делать мне никогда не приходилось, только читал. Во-вторых, показалось, что в такой задаче можно как раз удачно поиграть с последними нововведениями в C# и dotnet и покапаться в спанах (может, в этом и была моя ошибка, подскажите).

Но так в открытую задание шарить не хотелось (чтобы не подводить компанию), а подготовить для общественного порицания своюь реализацию в более простом виде всё времени небыло, тормозил с этим
А раз уж аж видео-обзор этого задания вышел: Тестовое задание Senior .Net — критикуйте, то, думаю. не страшно, если я прям так. Если что, звиняйте.

  Задание
На входе есть большой текстовый файл, где каждая строка имеет вид Number. String
Например:
415. Apple
30432. Something something something
1. Apple
32. Cherry is the best
2. Banana is yellow

Обе части могут в пределах файла повторяться. Необходимо получить на выходе другой файл, где
все строки отсортированы. Критерий сортировки: сначала сравнивается часть String, если она
совпадает, тогда Number.
Т.е. в примере выше должно получиться
1. Apple
415. Apple
2. Banana is yellow
32. Cherry is the best
30432. Something something something

Требуется написать две программы:
  1. Утилита для создания тестового файла заданного размера. Результатом работы должен быть
    текстовый файл описанного выше вида. Должно быть какое-то количество строк с одинаковой
    частью String.
  2. Собственно сортировщик. Важный момент, файл может быть очень большой. Для тестирования
    будет использоваться размер ~100Gb.
    При оценке выполненного задания мы будем в первую очередь смотреть на результат
    (корректность генерации/сортировки и время работы), во вторую на то, как кандидат пишет код.
Язык программирования: C#.

Решение моё интервьюеров не удовлетворило, говорят, что очень медленно работает: как обычно, у меня на лаптопе как раз всё летает, файл в 1Г сортируется за 13 с небольшим секунд, а у ревьюеров получилось 130c на файл 1 гиг Так мне написали.

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

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

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

Решение: https://github.com/ViIvanov/DataSort

  Как это запускать
Сначала можно запустить GenerateFile.cmd, он создаст подпапку Results и в ней файл DataSort-1G.txt размером 1 гигабайт.
Командная строка:
@GenerateFile --FilePath "..\..\..\..\Results\DataSort-1G.txt" --RequiredLengthGiB 1
то есть путь к файлу и требуемый размер в гигабайтах. Размер можно указывать дробный, например 0.1 для 100-мегабайтного файла. Какие-то более тонкие настройки есть в AppSettings.json рядом с исполняемым файлом.

Потом (при необходимости нужно изменить текущую директорию снова на папку solution) можно запустить SortFile.cmd, он отсортирует файл, результат (единственный файл) будет в папке "Results\<guid>\"
Командная срока:
@SortFile --FilePath "..\..\..\..\Results\DataSort-1G.txt" --MaxReadLines 200000

Снова путь к файлу и количество строк, на которые можно перед сортировкой можно разбить входной файл. Этим параметром можно регулировать используемую оперативную память.
Так же, некоторые более тонкие настройки есть в AppSettings.json рядом с исполняемым файлом.


P.S. Мне показалось, что Алгоритмы более подходящий форум для этого обсуждения, но если нет — то давайте перенесём.
Help will always be given at Hogwarts to those who ask for it.
Отредактировано 21.08.2022 11:11 _FRED_ (Исправил заголовок) . Предыдущая версия .
Re: Как правильно сортировать содержимое больших файлов?
От: Буравчик Россия  
Дата: 21.08.22 12:12
Оценка: +1
Здравствуйте, _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 19:17
Best regards, Буравчик
Re[2]: Как правильно сортировать содержимое больших файлов?
От: _FRED_ Черногория
Дата: 21.08.22 12:37
Оценка:
Здравствуйте, Буравчик, Вы писали:

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

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

Спасибо. RemoveAt всегда удаляет последний элемент из списка, поэтому она сложности добавлять не должна.
Далее бинарным поиском находится, куда вставить новый элемент и это как раз и есть логарифм. Нет?

Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?

P.S. Если вообще "отключить" сортировку, то есть удалять последний элемент списка и новую строку всегда добавляить в конец же, то 1,976 файлов сливаются за 8..9 секунд. Всё-таки кажется, что проблема не в этом.
Help will always be given at Hogwarts to those who ask for it.
Отредактировано 21.08.2022 12:56 _FRED_ . Предыдущая версия .
Re[3]: Как правильно сортировать содержимое больших файлов?
От: Буравчик Россия  
Дата: 21.08.22 12:59
Оценка:
Здравствуйте, _FRED_, Вы писали:

_FR>Спасибо. RemoveAt всегда удаляет последний элемент из списка, поэтому она сложности добавлять не должна.

_FR>Далее бинарным поиском находится, куда вставить новый элемент и это как раз и есть логарифм. Нет?

Так еще insert есть, в середину

_FR>Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?


Чтобы определить логарифм там или нет, надо мерять не весь этап мержа, а только on-CPU, т.е. только работу с items, без диска

P.S. Большая разница во времени могла также получиться из-за типа диска HDD/SSD/NVME
Best regards, Буравчик
Re[3]: Как правильно сортировать содержимое больших файлов?
От: Буравчик Россия  
Дата: 21.08.22 13:02
Оценка:
Здравствуйте, _FRED_, Вы писали:

_FR>P.S. Если вообще "отключить" сортировку, то есть удалять последний элемент списка и новую строку всегда добавляить в конец же, то 1,976 файлов сливаются за 8..9 секунд. Всё-таки кажется, что проблема не в этом.


Ну, может и не в этом

А профайлер что говорит?
Best regards, Буравчик
Re[4]: Как правильно сортировать содержимое больших файлов?
От: _FRED_ Черногория
Дата: 21.08.22 13:18
Оценка:
Здравствуйте, Буравчик, Вы писали:

_FR>>Спасибо. RemoveAt всегда удаляет последний элемент из списка, поэтому она сложности добавлять не должна.

_FR>>Далее бинарным поиском находится, куда вставить новый элемент и это как раз и есть логарифм. Нет?

Б>Так еще insert есть, в середину


То есть вот это вот по сути имеет линейную сложность:
var index = list.BinarySearch(item);
list.Insert(index >= 0 ? index : ~index, item);


_FR>>Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?

Б>Чтобы определить логарифм там или нет, надо мерять не весь этап мержа, а только on-CPU, т.е. только работу с items, без диска
Б>P.S. Большая разница во времени могла также получиться из-за типа диска HDD/SSD/NVME

Мне выдали такие вот:

Как ориентир по времени — 10Гб файл генерируется около 2,5 минут, сортируется — 9 (кстати, это не самое быстрое решение).
Дополнительный ориентир — при сортировке 1Гб используется 2-2,5 Гб памяти.


На моём стареньком лаптопе, хорошем, но совсем не геймерском с ССД ессно генерация файла в 10Г занимает 35 секунд, сортировка 140с (памяти при этом расходуется меньше гига).
Если мне сказали, что моя программа работает 130 секунд на гигабайтном файле и это медленно, значит у них есть программы, которые там же работают значительно быстрее.

Я подозреваю, что дело тут может быть или в работе с диском или в каком-то принципиально другом подходе, потому что иначе не вижу, почему вдруг мой код работает в 10 раз медленнее, чем их.
Вот и интересно, в чём же именно я так промахнулся.
Help will always be given at Hogwarts to those who ask for it.
Re[4]: Как правильно сортировать содержимое больших файлов?
От: _FRED_ Черногория
Дата: 21.08.22 13:24
Оценка:
Здравствуйте, Буравчик, Вы писали:

_FR>>P.S. Если вообще "отключить" сортировку, то есть удалять последний элемент списка и новую строку всегда добавляить в конец же, то 1,976 файлов сливаются за 8..9 секунд. Всё-таки кажется, что проблема не в этом.

Б>Ну, может и не в этом

Да точно не там. Половина времени (примерно, ±10%) у меня это разбивка большого файла на мелкие, другая половина — сборка обратно большого сортированного файла из этих мелких.

Б>А профайлер что говорит?


А я даже и не подозреваю на что ещё смотреть. Большая часть времени — работа с диском, что и вызывает подозрения или в неверном подходе к этим операциями (размеры буферов не верные, флаги не те) или может надо как-то иначе делать
Help will always be given at Hogwarts to those who ask for it.
Re: Как правильно сортировать содержимое больших файлов?
От: Pavel Dvorkin Россия  
Дата: 21.08.22 13:42
Оценка: 5 (1) +2
Здравствуйте, _FRED_, Вы писали:

Решал эту задачу в реальном проекте в 2000-е. Но писал на C, поэтому мог позволить себе все. Да и исходный файл делал сам из других данных, так что мог его портить. Кроме того, надо было получить возможность доступа в порядке отсортированности, а собственно передвижение строк не требовалось.

Решение

Открываем file mapping и view на весь файл.

За линейное время проходим весь файл, заменяем разделитель внутри строки на '\0'. Конец строки тоже заменяем на '\0'. Одновременно строим массив указателей (смещение от начала файла + базовый адрес view) для каждой строки.

Этот массив и сортируем обычной qsort, используя strcmp в качестве int (*compare), так как строка заканчивается '\0'. Если strcmp возвращает 0 для первого критерия, strcmp по второму критерию.

Потом можно пройти файл заново, вернуть концы строк и разделители, но мне это было не нужно.

Если таки нужен выходной файл — пройти массив указателей линейно, переписывая строки в новый файл.

P.S. В действительности все было немного иначе. Полей в строке было 5-6 штук и надо было отсортировать по каждому полю. Так что массивов указателей было столько же и каждый сортировался.
With best regards
Pavel Dvorkin
Отредактировано 21.08.2022 13:48 Pavel Dvorkin . Предыдущая версия .
Re[2]: Как правильно сортировать содержимое больших файлов?
От: _FRED_ Черногория
Дата: 21.08.22 14:10
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Решал эту задачу в реальном проекте в 2000-е. Но писал на C, поэтому мог позволить себе все. Да и исходный файл делал сам из других данных, так что мог его портить. Кроме того, надо было получить возможность доступа в порядке отсортированности, а собственно передвижение строк не требовалось.

PD>Решение
PD>Открываем file mapping и view на весь файл.
PD>За линейное время проходим весь файл, заменяем разделитель внутри строки на '\0'. Конец строки тоже заменяем на '\0'. Одновременно строим массив указателей (смещение от начала файла + базовый адрес view) для каждой строки.

Хм. У меня в файле на 10 гиг 19,759,295 строк. Получается, файл на 200 гиг может содержать порядка (x20) 395,185,900 строк. Уже, вроде, гига полтора интов.

PD>Этот массив и сортируем обычной qsort, используя strcmp в качестве int (*compare), так как строка заканчивается '\0'. Если strcmp возвращает 0 для первого критерия, strcmp по второму критерию.


Исходный файл:
415. Apple
30432. Something something something
1. Apple
32. Cherry is the best
2. Banana is yellow


после преобразования:
415
Apple
30432
Something something something
1
Apple
32
Cherry is the best
2
Banana is yellow


Если я правильно понял предлагаемый алгоритм, то после сортировки будет:
1
2
30432
32
415
Apple
Apple
Banana is yellow
Cherry is the best
Something something something


И как потом собрать из этого то, что должно получиться в итоге:
1. Apple
415. Apple
2. Banana is yellow
32. Cherry is the best
30432. Something something something


Не расскажете подробнее часть про сортировку, как в ней учесть порядок полей. по которым надо сортировать и как потом собрать результат обратно?
Help will always be given at Hogwarts to those who ask for it.
Re[3]: Как правильно сортировать содержимое больших файлов?
От: Pavel Dvorkin Россия  
Дата: 21.08.22 14:22
Оценка:
Здравствуйте, _FRED_, Вы писали:

_FR>Хм. У меня в файле на 10 гиг 19,759,295 строк. Получается, файл на 200 гиг может содержать порядка (x20) 395,185,900 строк. Уже, вроде, гига полтора интов.


Тогда на них тоже file mapping. Хотя этого я не делал, за скорость не поручусь.

PD>>Этот массив и сортируем обычной qsort, используя strcmp в качестве int (*compare), так как строка заканчивается '\0'. Если strcmp возвращает 0 для первого критерия, strcmp по второму критерию.


_FR>Исходный файл:

_FR>
_FR>415. Apple
_FR>30432. Something something something
_FR>1. Apple
_FR>32. Cherry is the best
_FR>2. Banana is yellow
_FR>


После преобразования будет

415\0Apple\0
30432\0Something something something\0
1\0Apple\0
32\0Cherry is the best\0
2\0Banana is yellow\0

(точки я убрал, но они погоды не делают)

А массив указателей — на начала каждой исходной строки : p[0] на 415, p[1] на 30432 и т.д.

И тогда p[i] — указатель на число в строке, а p[i] + strlen(p[i]) — указатель на текстовую часть строки

Ну и все. qsort на этот p. В compare сравниваем как нам надо. Строки не переставляем, только p[i] будут переставлены.
With best regards
Pavel Dvorkin
Отредактировано 21.08.2022 14:26 Pavel Dvorkin . Предыдущая версия .
Re[2]: Как правильно сортировать содержимое больших файлов?
От: Буравчик Россия  
Дата: 21.08.22 16:14
Оценка: +1
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Этот массив и сортируем обычной qsort, используя strcmp в качестве int (*compare), так как строка заканчивается '\0'. Если strcmp возвращает 0 для первого критерия, strcmp по второму критерию.


Такой вариант будет медленнее, чем merge-сорт. Потому что кардинально поменяется работа с диском, вместо sequential read&write будет выполняться random read&write.
Best regards, Буравчик
Re: Как правильно сортировать содержимое больших файлов?
От: Codealot Земля  
Дата: 21.08.22 19:28
Оценка: +1
Здравствуйте, _FRED_, Вы писали:

_FR>сортировку файлов слиянием


На сакмом деле, здесь лучше bucket sort
Ад пуст, все бесы здесь.
Re[4]: Как правильно сортировать содержимое больших файлов?
От: _FRED_ Черногория
Дата: 22.08.22 05:49
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>После преобразования будет

PD>415\0Apple\0
PD>30432\0Something something something\0
PD>1\0Apple\0
PD>32\0Cherry is the best\0
PD>2\0Banana is yellow\0

PD>(точки я убрал, но они погоды не делают)


Тогда не понял: вы ранее писали, что "Конец строки тоже заменяем на '\0'.". Что такое "конец строки"? В винде это два символа \r\n. Каждый из них нужно заменить на \0 или только какой-то один?

PD>А массив указателей — на начала каждой исходной строки : p[0] на 415, p[1] на 30432 и т.д.

PD>И тогда p[i] — указатель на число в строке, а p[i] + strlen(p[i]) — указатель на текстовую часть строки
PD>Ну и все. qsort на этот p. В compare сравниваем как нам надо. Строки не переставляем, только p[i] будут переставлены.

Это часть понял, спасибо. Действительно, не могу представить, что случайные перескакивания по файлу, размер которого значительно больше объёма оперативной памяти, будут быстрее.
Help will always be given at Hogwarts to those who ask for it.
Re[5]: Как правильно сортировать содержимое больших файлов?
От: Буравчик Россия  
Дата: 22.08.22 05:59
Оценка: +1
Здравствуйте, _FRED_, Вы писали:

_FR>Тогда не понял: вы ранее писали, что "Конец строки тоже заменяем на '\0'.". Что такое "конец строки"? В винде это два символа \r\n. Каждый из них нужно заменить на \0 или только какой-то один?


Вообще не нужно ничего заменять. Достаточно сохранять индекс начала строки. А еще лучше сохранять индексы начала и длину строки, но потребуется чуть больше памяти.

Заменялось на \0, наверное, для того, чтобы использовать библиотечную оптимизированную strcmp. В задаче данного топика это не дает такой выгоды.
Best regards, Буравчик
Re[6]: Как правильно сортировать содержимое больших файлов?
От: _FRED_ Черногория
Дата: 22.08.22 06:16
Оценка:
Здравствуйте, Буравчик, Вы писали:

_FR>>Тогда не понял: вы ранее писали, что "Конец строки тоже заменяем на '\0'.". Что такое "конец строки"? В винде это два символа \r\n. Каждый из них нужно заменить на \0 или только какой-то один?

Б>Вообще не нужно ничего заменять. Достаточно сохранять индекс начала строки. А еще лучше сохранять индексы начала и длину строки, но потребуется чуть больше памяти.
Б>Заменялось на \0, наверное, для того, чтобы использовать библиотечную оптимизированную strcmp. В задаче данного топика это не дает такой выгоды.

Да, в таком разрезе это понятно: при каждом сравнении так сможем распарсить всю строку и сравнить как нужно.
Help will always be given at Hogwarts to those who ask for it.
Re[5]: Как правильно сортировать содержимое больших файлов?
От: Pavel Dvorkin Россия  
Дата: 22.08.22 06:33
Оценка:
Здравствуйте, _FRED_, Вы писали:


_FR>Тогда не понял: вы ранее писали, что "Конец строки тоже заменяем на '\0'.". Что такое "конец строки"? В винде это два символа \r\n. Каждый из них нужно заменить на \0 или только какой-то один?


Первый, то есть \r. Мне надо, чтобы каждая строка исходного файла превратилась в 2 строки ASCIIZ. Что будет после второй ASCIIZ — не важно, так как использоваться не будет

Исходно

415 Apple

То есть

415 Apple\r\n

После преобразования

415\0Apple\0\n

Имеем 2 строки ASCIIZ и указатель на первую из них. Если к нему прибавить strlen(первой) + 1, получим указатель на вторую, она тоже ASCIIZ. А что там за вторым нулем — мне совсем не важно.
With best regards
Pavel Dvorkin
Re[6]: Как правильно сортировать содержимое больших файлов?
От: Pavel Dvorkin Россия  
Дата: 22.08.22 06:34
Оценка: +1
Здравствуйте, Буравчик, Вы писали:

Б>Заменялось на \0, наверное, для того, чтобы использовать библиотечную оптимизированную strcmp. В задаче данного топика это не дает такой выгоды.


Да. Я же писал, там в действительности было 5 или 6 полей. Записал \0 в конец каждого и stricmp
With best regards
Pavel Dvorkin
Re[3]: кстати, о скорости
От: Pavel Dvorkin Россия  
Дата: 22.08.22 06:42
Оценка:
Здравствуйте, _FRED_, Вы писали:

Нашел у себя этот код, и даже замеры времени.

Файл размером примерно в 1 Гбайт. Максимальное количество строк 1 миллион. Время на сортировку в разных случаях от 1-2 минут до 5-10 минут.

Писал я это в 2002 году. Pentium III, 666 Mhz, 256 Мб ОП, винчестер на 80 Гб. Хорошая была машинка, на тот момент одна из лучших в университете
With best regards
Pavel Dvorkin
Re[4]: кстати, о скорости
От: _FRED_ Черногория
Дата: 22.08.22 07:20
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Нашел у себя этот код, и даже замеры времени.

PD>Файл размером примерно в 1 Гбайт. Максимальное количество строк 1 миллион. Время на сортировку в разных случаях от 1-2 минут до 5-10 минут.
PD>Писал я это в 2002 году. Pentium III, 666 Mhz, 256 Мб ОП, винчестер на 80 Гб. Хорошая была машинка, на тот момент одна из лучших в университете

О, так может удастся запустить сейчас, можно будет и померить?
Help will always be given at Hogwarts to those who ask for it.
Re[5]: кстати, о скорости
От: Pavel Dvorkin Россия  
Дата: 22.08.22 08:26
Оценка: 18 (1)
Здравствуйте, _FRED_, Вы писали:

_FR>О, так может удастся запустить сейчас, можно будет и померить?


Увы, запустить не удастся. Эти csv файлы делаются из других, а тех у меня уже давно нет. Да и не помню я, что и как именно там запускалось — все же 20 лет прошло.
With best regards
Pavel Dvorkin
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.