Тестовое задание для Тинькофф
Скрипт лежит в директории ddl.
Подпроект SourceFilesGenerator, класс com.lmm.tinkoff.task.filegen.GenerateSourceFilesMain.
Аргументы командной строки передаются в формате <ключ> <значение> в любом порядке, все аргументы опциональные.
Ключи аргументов командной строки:
-sourceDir - директория, в которую генерируются исходные файлы -filesList - файл, куда будет записан список сгенерированных файлов -filesCount - количество файлов -fileSize - размер каждого файла в байтах -origin - нижняя граница диапазона генерации -bound - верхняя граница диапазона генерации
Перед запуском необходимо прописать url базы данных в src/main/resources/application.properties и src/test/resources/application.properties.
Если при генерации файлов был изменен путь файла со списком сгенерированных файлов (опция -filesList генератора файлов), то необходимо указать путь к этому файлу. Для этого необходимо после соответствующей команды запуска указать опцию
-Dcom.lmm.tinkoff.task.files_list=<путь к файлу> или поменять свойства source-files-list и test.source-files-list в pom.xml.
Для запуска приложения с помощью Maven: mvn spring-boot:run.
Для запуска тестов с помощью Maven: mvn test.
При первом запуске производится индексация исходных файлов, операция займет длительное время.
Директорию, в которой хранятся файлы с индексами, можно поменять с помощью опции -Dcom.lmm.tinkoff.task.index_dir=<путь к директории> или поменяв свойства index-dir и test.index-dir в pom.xml.
При достаточно быстром чтении данных с диска, очень много времени занимает обработка прочитанных данных, то есть конвертирование сторки в int. Время работы обхода только одного файла при таком подходе - несколько минут, это сильно превышает допустимое время ожидания запроса.
Было принято во внимание существование алгоритмов поиска подстроки, которые могут сократить время работы, но на объеме данных 20 Гб оно все равно будет больше допустимого.
Единственное решение - предварительно проиндексировать входные файлы и работать уже с построенными индексами. При более долгом построении индексов, получается очень быстрая проверка наличия числа в файле. Недостаток такого подхода - длительное время между изменением исходного файла и видимостью обновленных данных на клиенте. В таком случае можно считать, что в этой системе относительно быстрая операция чтения и долгая операция изменения данных.
Числа из входного файла читаются за один проход по файлу в массив, этот массив сортируется. Используется тип int. Максимальный объем требуемой памяти в этом случае - 2 Гб для файла 1 Гб (если почти все числа состоят из одного десятичного знака). Средний объем - 500 Мб. Это много, но за объем памяти для JVM обычно не выходит. При этом, из - за большого (порядка 40 байт) оверхеда на хранение элемента уже нет возможности использовать ни BigInteger, ни SortedSet. Далее для размера массива выбирается количество блоков, на которые нужно поделить массив (я выбрал квадратный корень из размера массива), массив делится на это количество блоков. Затем все блоки по очереди пишутся в файл индекса, перед каждой записью получается и запоминается текущий offset в файле и кладется в TreeMap с ключом - первым элементом блока. TreeMap записывается в конец файла, offset до начала TreeMap в файле - в первые 8 байт файла. Такая структура чуть - чуть сложнее случая, когда TreeMap лежит в начале файла, но зато есть возможность использовать и писать в файл блоки переменного размера и не задумываться о размере этих блоков в файле (будет полезно, если вдруг нужно будет поменять алгоритм, например, все-таки заменить int на BigInteger). Зная структуру, читаем TreeMap из файла индекса, и вычисляем нужный блок для данного на вход числа n: нужен блок с таким ключом, чтобы n лежало в полуинтервале [текущий ключ; следующий по порядку ключ). По ключу получаем offset нужного блока, читаем блок целиком, а затем бинарным поиском определяем наличие числа n в блоке (зная, что блоки отсортированы). Если числа нет в блоке, то его нет в файле.
Алгоритм индексации можно сделать лучше и быстрее - увеличить количество уровней, применить какой-нибудь алгоритм со сбалансированным деревом, а в таком случае и перестроение индекса при незначительных измененях в исходном файле будет происходить быстрее, да и быстрее вообще.
Я решил остаться в рамках разумного для данной задачи и реализовать наиболее простой алгоритм.
Дополнительно, в случае, если исходные файлы могут меняться во время выполнения, я могу реализовать периндексирование файлов во время выполнения.