Представление больших наборов данных в C / C ++

Question

Каков наилучший способ представления следующих данных для последующих параллельных вычислений:

Набор из четырех чисел (приблизительно 20 000 000) целых чисел, которые должны быть доступны для первых трех элементов четверки в качестве индексов?

Предполагается, что вычисления выполняются с использованием MPI в C / C ++.

UPD: Я также должен подчеркнуть, что у меня есть две аналогичные структуры данных, описанные выше, с той лишь разницей, что первая является статической, а вторая динамической. Чтобы быть точным, четвертый элемент каждого кортежа во второй структуре должен быть вычислен.

Основываясь на комментариях, я теперь склонен использовать векторы C ++ и хэшировать их по первым трем значениям. Я думаю, мне нужно создать хэш-карту. Как мне это сделать в C ++?

Answer 1

Это звучит как точечные данные в трехмерном пространстве, в основном. Существует много решений этой проблемы, и выбор наилучшего зависит от диапазона и распределения ваших индексов, а также от ваших схем доступа к данным. Последнее особенно важно - вы выбираете случайным образом набор значений в качестве своего ключа и хотите посмотреть, существует ли там четверка данных, или вы получаете к ним более регулярный доступ? Различные структуры данных предлагают очень разные затраты для регулярного и случайного доступа.

Ради описания я буду называть ваши квадраты данных {X, Y, Z, W}, где {X, Y, Z} - ваш ключ, а W - значение, связанное с этим ключом.

Если у вас есть прямоугольный диапазон Xmin-to-Xmax, Ymin-to-Ymax, Zmin-to-Zmax, и этот диапазон плотно заполнен, так что каждый X, Y и Z в этом диапазоне имеет данные связанный с ним, вы просто используете трехмерный массив, индексированный по X, Y и Z, где W хранится в каждой точке этого массива.

Если у вас есть что-то вроде этого, за исключением того, что только с некоторыми значениями связаны квадраторы данных, но их доля достаточно велика (скажем, 25% или более), тогда вы все равно можете использовать трехмерный массив и в каждой точке этого массива вы либо сохраняете значение W, либо «ничего». Если вам нужно уметь ответить на вопрос о том, присутствует ли триплет X, Y, Z в вашем наборе данных, вы либо сохраняете невозможное значение W (-1, возможно, если они являются положительными целыми числами, либо INT_MAX, если они в противном случае), или в каждой точке вы сохраняете структуру целого числа W и логического флага «is_present» и устанавливаете для флага значение true / false, если этот индекс присутствует в вашем наборе данных.

Если ваши квадраты данных более разрежены, но индексы все еще находятся в разумных пределах, вы можете использовать структуру, называемую октодеревом, для представления набора данных. В Википедии есть описание с диаграммами: http://en.wikipedia.org/wiki/Octree. По сути, вы делите диапазон возможных индексов на 8 октантов. Если в этом октанте всего несколько квадов данных, вы сохраняете их список; в противном случае вы рекурсивно делите этот октант на 8 субоктантов и повторяете. В конце концов вы получаете это дерево октантов и субоктантов, и каждый лист дерева представляет собой небольшой список квадратов данных. Даже если найти одну точку в дереве дорого (нужно пройти по дереву сверху вниз), дешево найти соседних соседей, дешево найти несколько точек в одном и том же пространстве и действительно дешево перебрать все точки в дереве.

Answer 2

Поскольку первая структура доступна только для чтения, а вторая доступна только через один поток (звучит так), вам не нужно беспокоиться о проблемах параллелизма.

Если вы знаете, что три части индекса будут сгруппированы в «небольшой» диапазон целочисленных значений, вы можете использовать (возможно, вложенный) вектор с некоторой неиспользуемой памятью и просто использовать прямую индексацию. Преимущество состоит в том, что он довольно быстрый, но не будет работать, если индексы могут охватывать целые значения большого диапазона.

В качестве альтернативы, если у вас широкий диапазон значений ключей, вы можете использовать карту, хэш-карту или отсортированный вектор. Карта будет проста в использовании, но имеет накладные расходы памяти на узел. Точно так же хэш-карта предложит отличное время поиска, но опять-таки потребует много памяти. Сортированный вектор все равно будет предлагать O (log n) удвоений без затрат на карту для каждого узла.

Answer 3

На какой системе вы планируете запускать это?

Может ли все это уместиться в память, или есть проблема с кэшированием ввода / вывода, которую необходимо решить?

Сколько байт на целое число?

При 32 битах вы просматриваете (20M * 4 * 4) ~ 305 МБ данных, которые вы могли бы легко разместить в ОЗУ выделенной системы или, по-видимому, для многоцелевого ПК.

Если у вас есть наилучшие возможные аппаратные обстоятельства, поместите все это в непрерывный блок оперативной памяти. Вектор этих четырехугольников может быть радикально отсортирован за O (N) время. Отсюда индексация в массив будет очень быстрой.

Answer 4

Как предполагают комментаторы (или, как я понимаю), они предлагают хэшировать первые три значения и использовать их в качестве ключа в некоторой хэш-карте.