Я аспирант физики и работаю над написанием кода для сортировки нескольких сотен гигабайт данных и возврата фрагментов этих данных по запросу. Вот в чем хитрость, я не знаю хорошего метода сортировки и поиска данных такого рода.
Мои данные по существу состоят из большого количества наборов чисел. Эти наборы могут содержать от 1 до n чисел внутри себя (хотя в 99,9% наборов n меньше 15), и таких наборов примерно 1,5 ~ 2 миллиарда (к сожалению, такой размер исключает перебор).
Мне нужно иметь возможность указать набор из k элементов и вернуть мне каждый набор из k+1 элементов или более, содержащий указанное подмножество.
Простой пример:
Предположим, у меня есть следующие наборы данных:
(1,2,3)
(1,2,3,4,5)
(4,5,6, 7)
(1,3,8,9)
(5,8,11)
Если бы я дал запрос (1,3), у меня были бы наборы: (1,2,3), (1,2,3,4,5) и (1,3,8,9).< br> Запрос (11) вернет набор: (5,8,11).
Запрос (1,2,3) вернет наборы: (1,2,3) и (1,2, 3,4,5)
Запрос (50) не вернет наборов:
К настоящему времени узор должен быть четким. Основное различие между этим примером и моими данными заключается в том, что наборы с моими данными больше, числа, используемые для каждого элемента наборов, варьируются от 0 до 16383 (14 бит), и есть еще множество наборов.
Если это имеет значение, я пишу эту программу на C++, хотя я также знаю java, c, немного ассемблера, немного фортрана и немного perl.
Кто-нибудь знает, как это осуществить?
редактировать:
Чтобы ответить на пару вопросов и добавить несколько моментов:
1.) Данные не меняются. Все это было снято за одну длинную серию прогонов (каждый из которых был разбит на 2 гигабайтных файла).
2.) Что касается места для хранения. Необработанные данные занимают примерно 250 гигабайт. По моим оценкам, после обработки и удаления большого количества посторонних метаданных, которые мне не интересны, я могу сократить их до 36–48 гигабайт в зависимости от того, сколько метаданных я решу сохранить (без индексов). Кроме того, если при первоначальной обработке данных я столкнусь с достаточным количеством одинаковых наборов, я смогу еще больше сжать данные, добавив счетчики для повторяющихся событий, а не просто повторяя события снова и снова.
3.) Каждое число в обрабатываемом наборе фактически содержит как минимум два числа: 14 бит для самих данных (обнаруженная энергия) и 7 бит для метаданных (номер детектора). Так что мне потребуется как минимум три байта на число.
4.) Мой комментарий «хотя в 99,9% наборов n меньше 15» вводил в заблуждение. При предварительном просмотре некоторых фрагментов данных я обнаружил, что у меня есть наборы, содержащие до 22 чисел, но медиана составляет 5 чисел на набор, а среднее значение — 6 чисел на набор.
5.) Хотя мне нравится идея создания индекса указателей в файлах, я немного подозреваю, потому что для запросов, включающих более одного числа, у меня остается полумедленная задача (по крайней мере, я думаю, что это медленно) найти набор всех указателей, общих для списков, т. е. нахождение наибольшего общего подмножества для заданного числа наборов.
6.) Что касается доступных мне ресурсов, я могу собрать около 300 гигабайт пространства после того, как у меня будут необработанные данные в системе (оставшаяся часть моей квоты в этой системе). Система представляет собой двухпроцессорный сервер с 2 четырехъядерными процессорами AMD и 16 гигабайтами оперативной памяти.
7.) Да 0 может возникнуть, это артефакт системы сбора данных, но это может произойти.
