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

Question

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

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

Расчет должен выполняться с использованием MPI в C/C++.

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

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

Answer 1

Какую систему вы планируете запустить?

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

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

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

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

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