Generate a huge text file of the kind "Number. String". And sort this one.
Developed in Embarcadero RAD Studio 10.3.1
В коммнадной строке терминала вводим последовательно команды:
> Git clone https://github.com/PavelValentov/SortBigTextFile.git
> cd ./SortBigTextFile/
> BDS.exe ProjectGroup.groupproj
В открывшейся среде Embarcadero RAD Studio Delphi для группы проекта выполняем команду "Build All". В результате в каталоге проекта компилируются 2 исполняемых файла:
- TextFileGenerator.exe — генератор файла
- TextFileSorter.exe — сортировщик файла
Исходные коды утилиты располагаются в каталоге ./Generator/
После запуска в форме приложения указываем
* Максимальный размер генерируемого файла в MB
* Фразу, из слов которой будет формироваться словарь файла
Чтобы сформировать текстовый файл, нажимаем кнопку "Generate a new text file"
В результате работы утилиты получится файл ./database.txt
Основная работа производится в отельном потоке TGenerator.
После нажатия на кнопку "Generate" создается поток и запускается, блокируются контролы на форме.
При нажатии на кнопку "Stop" или при закрытии формы, поток останавливается и уничтожается.
В теле потока *TGenerator.Execute*:
* Производится разбор введенной в форме фразы на слова *DispatchPhrase()*
* Слов должно быть не меньше двух, для формирования из них различных фраз
* Формирутся словарь фраз для наполнения результирующего текстового файла *AddPhrase()*.
Метод вызывает рекурсивно сам себя для формирования всех возможных вариантов фраз.
* Создается файловый поток *LStringStream* для записи в текстовый файл полученных фраз
* Формируются фразы вида "Число. Строка" и записываются в буфер *LPhrases: TStringList;*.
Размер буфера = BUFFER_STRINGS_COUNT строк.
* Пока не достигнут лимит размера файла, буфер пишется в поток, и в цикле наполняется снова.
* Кажая строка содержит случайное число типа UInt64
и случайную строку из ранее сформированного словаря фраз.
После завершения работы генератора, поток уничтожается, контролы на форме разблокируются.
Узким местом утилиты является время формирования словаря фраз. Если исходная фраза состоит из 5 и более слов, словарь фраз может формироваться длительное время. Для ускорения работы формирования словаря, на каждое слово, с которого начинается фраза можно создавать отдельный вспомогательный поток TThread.
Исходные коды утилиты располагаются в каталоге ./Sorter/
После запуска в форме приложения доступна одна кнопка "Sort file"
Если существует файл файл ./database.txt, то сортировщик создаст файл файл ./destdb.txt.
Строки в полученном файле будут отсортированы по критерию: сначала сравнивается часть String, если она совпадает, тогда Number.
Для сортировки большого файла используется алгоритм External Merge Sorting. Основная работа производится в отельном потоке TSorter.
После нажатия на кнопку *Sort* создается и запускается поток *TSorter*, наслдник класса *TThread*.
На форме остается доступной только кнопка *Stop*.
После формирования отсортированного файла поток уничтожается. Кнопка *Sort* снова становится доступной.
1. Читается блок из исходного потока файла
2. Блок разбивается на строки вида "Number. String"
4. Каждая уникальная строка String вносится в массив TArray<TPhraseFile>
3. Для каждой уникальной строки String создается массив индексов TArray<UInt64>,
куда вносятся по порядку все значения Number для этой строки
4. Если массив индексов больше MAX_PHRASE_INDEXES_BUFFER_SIZE,
он сохраняется в файле, чтобы высвободить память для построения остальных индексов и дальнейшей сортировки.
5. После построения всех индексных файлов, массив со значениями String сортирется
6. Далее сортируются индексы для каждой фразы String, последовательно загружаются из файлов в память.
7. Последовательно в результирующий файл сохраняются отсортированные значения "Number. String"
8. Каждый сохраненный отсортированный индексный файл удалятся из памяти и с диска.
Результат записан в файл *DEST_FILE_NAME*.
Для сортировки текстовых строк типа "TAltiumString"
доработана ранее созданная универсальная библиотека сортировки любых типов данных.
Данная библиотека ("AppliedObjectList") основана на дженериках, и использует вспомогательные библиотеки:
* "SortMethods", в которой описываются реализованные методы сортировки.
В библиетеке реализованы методы:
- Быстрой сортировки "TAllSort.QuickSort<T>"
- Пирамидальная сортировка "TAllSort.HeapSort<T>"
- Пузырьковый метод "TAllSort.BubbleSort<T>"
* "AllObjects", в которой описываются типы данных, которые можно сортировать и способы их сравнения.
Основная проблема производительности находится в работе с HDD, если подобрать правильный размер буфферов чтения/записи это существенно ускорит работу. Но для этого потребуется большой объем оперативной памяти.
Так же сортировка файлов производится частями размером ~BUFFER_STRINGS_COUNT. Каждый блок можно сортировать в отдельном потоке, и по готовности записывать блок в соответствующее место в отсортированном файле.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent