Какие популярные решения / алгоритмы для упорядочения таких больших наборов данных?
Поскольку вы уже пришли к выводу, что данные слишком велики для сортировки / манипулирования в имеющейся памятидоступно, популярное решение - это база данных, которая будет создавать дисковые структуры для управления и сортировки большего количества данных, чем может быть в памяти.
Вы можете создать свою собственную дисковую схему или получить такую, котораяуже полностью разработана, оптимизирована и поддерживается (например, популярная база данных).«Популярное» решение, о котором вы спрашивали, - это использовать базу данных для управления / сортировки больших наборов данных.Это именно то, для чего они созданы.
База данных
Вы можете создать таблицу, индексированную вашим ключом сортировки, вставить все записи в базу данных,затем создайте курсор, отсортированный по вашему ключу, и итерируйте курсор, записывая теперь отсортированные записи в новый файл по одному.Затем удалите базу данных, когда закончите.
Сортировка фрагментированной памяти, объединение вручную
В качестве альтернативы вы можете выполнить сортировку фрагментированных данных, разбивая данные на меньшие.фрагменты, которые могут поместиться в памяти, отсортировать каждый фрагмент, записать каждый отсортированный блок на диск, затем выполнить слияние всех блоков, в которых вы читаете следующую запись из каждого блока в память, найти самый низкий из всех блоков, записать егов ваш конечный выходной файл, прочитайте следующую запись из этого блока и повторите.Используя эту схему, объединение будет когда-либо иметь только N записей в памяти в то время, когда N - это количество отсортированных чанков, которые у вас есть (вероятно, меньше, чем исходная сортировка чанкованных блоков).
Как упомянул ДжувианВот краткий обзор того, как может работать такая «внешняя сортировка»: https://en.wikipedia.org/wiki/External_sorting.
Одним из ключевых аспектов сортировки по частям памяти является определение размера блоков.Есть несколько стратегий.Самым простым может быть просто решить, сколько записей вы можете надежно разместить и отсортировать в памяти, на основе нескольких простых тестов или даже просто предположить, что вы уверены в безопасности (выбор меньшего числа для обработки за один раз означает, что вы будетеразделить данные на несколько файлов).Затем просто прочитайте столько записей в память, отсортируйте их, запишите их по известному имени файла.Повторяйте этот процесс до тех пор, пока вы не прочитаете все записи, а затем все они находятся во временных файлах с известными именами файлов на диске.
Затем откройте каждый файл, прочитайте первую запись из каждой, найдите самую низкую записьдля каждого, что вы прочитали, запишите его в свой окончательный файл, прочитайте следующую запись из этого файла и повторите процесс.Когда вы доберетесь до конца файла, просто удалите его из списка данных, которые вы сравниваете, так как это теперь сделано.Когда данных больше нет, все готово.
Сортировка ключей только в памяти
Если все ключи сортировки поместятся в память, ноне связанные данные, то вы можете создать и отсортировать свой собственный индекс.Есть много разных способов сделать это, но вот одна схема.
Прочитать все исходные данные, сохраняя в памяти две вещи для каждой записи: ключ сортировки и смещение файла в исходном файле, где находятся эти данныесохраняются.Затем, когда у вас есть все ключи сортировки в памяти, сортируйте их.Затем перебирайте отсортированные ключи один за другим, ища место записи в файле, читая эту запись, записывая ее в выходной файл, переходя к следующему ключу и повторяя, пока данные для каждого ключа не будут записаны по порядку.
BTree Key Sort
Если все ключи сортировки не помещаются в памяти, то вы можете получить основанную на диске библиотеку BTree, которая позволит вам сортироватьвещи больше, чем могут быть в памяти.Вы бы использовали ту же схему, что и выше, но вы бы поместили ключ сортировки и смещение файла в BTree.
Конечно, это только один шаг, чтобы поместить сами фактические данные из файла в BTree, и тогда у вас будет база данных.