Объявление структуры трехмерного массива в C ++ с использованием вектора

Question

Привет Я аспирант, изучающий научные вычисления с использованием c ++.Некоторые из наших исследований фокусируются на скорости алгоритма, поэтому важно построить достаточно массивную структуру массива.

Я видел два способа построения 3D-массивов.Первый - использовать векторную библиотеку.

vector<vector<vector<double>>> a (isize,vector<double>(jsize,vector<double>(ksize,0)))

Это дает структуру трехмерного массива размера isize x jsize x ksize.

Другой - создать структуру, содержащую массив 1d размера isize* jsize * ksize используя

new double[isize*jsize*ksize].Чтобы легко получить доступ к определенному местоположению (i, j, k), необходима перегрузка оператора (я прав?).

И из того, что я испытал, первое гораздо быстрее, так как оно может получить доступ к местоположению(i, j, k) легко, в то время как последний должен вычислить местоположение и вернуть значение.Но я видел, как некоторые люди предпочитали последний, а не первый.Почему они предпочитают последний параметр?и есть ли какой-либо недостаток в использовании первого?

Спасибо за продвижение.

Answer 1

Добро пожаловать в SO.

Если все, что у вас есть, это две альтернативы, то первая может быть лучше.

Предпочитают использовать массив или вектор STL вместо Cмассив

Вам следует избегать использования простых массивов C ++, поскольку вам нужно самим управлять выделением / освобождением памяти с помощью new/delete и другим стандартным кодом, таким как отслеживать размер / проверять границы.Четко говоря, «Массивы C менее безопасны и не имеют преимуществ перед массивом и вектором».

Однако в первом варианте есть некоторые важные недостатки.Я хотел бы отметить следующее:

std::vector<std::vector<std::vector<T>>>

не является трехмерной матрицей.В матрице все строки должны иметь одинаковый размер.С другой стороны, в «векторе векторов» нет гарантии, что все вложенные векторы имеют одинаковую длину.Причина в том, что вектор является линейной 1-D структурой, как указано в ответе @spectras.Следовательно, чтобы избежать всякого плохого или неожиданного поведения, вы должны включить в свой код охранники, чтобы получить гарантированный прямоугольный инвариант.

К счастью, первая альтернатива - не единственная, которую вы можете иметь в руках.

Например, вы можете заменить массив в стиле c на std :: array:

const int n = i_size * j_size * k_size;

std::array<int, n> myFlattenMatrix;

или использовать std::vector в случае, если размеры вашей матрицы могут измениться.

Доступ к элементу по его 3 координатам

Относительно вашего вопроса

Чтобы легко получить доступ к определенному местоположению (i, j, k), перегрузка операторанеобходимо (я прав?).

Не совсем так.Поскольку нет ни 3-параметрического оператора ни для std :: vector, ни для массива, вы не можете его перегрузить.Но вы можете создать шаблонный класс или функцию, чтобы обернуть его для вас.В любом случае вы должны отложить 3 вектора или вычислить индекс сглаживания элемента в линейном хранилище.

Учитывая, что для экспериментов не используйте библиотеку матриц третьей части, такую ​​как Eigen,

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

Производительность алгоритма и биг-о нотация

Обычно производительность алгоритмов анализируется с использованием подхода big-O , где такие факторы, какфактическое затраченное время, аппаратная скорость или особенности языка программирования не учитываются.Книга Адама Дроздека «Структуры данных и алгоритмы в C ++» может предоставить более подробную информацию об этом.

Answer 2

Прежде всего, идея о том, что вы обращаетесь к (i, j, k) в вашем vec ^ 3 напрямую, несколько ошибочна.У вас есть структура указателей, в которой вам нужно разыменовать три указателя.Обратите внимание, что я понятия не имею, будет ли это быстрее или медленнее, чем вычисление позиции в одномерном массиве.Вам нужно проверить это, и это может зависеть от размера ваших данных (особенно от того, помещается ли он в чанке).

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

В-третьих, необработанный массивсохраняет все в последовательной памяти, что хорошо для потоковой передачи и может быть полезно для определенных алгоритмов из-за быстрого доступа к кешу.Например, когда вы добавляете одно 3D-изображение к другому.

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

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

Answer 3

Основным отличием между ними будет макет:

vector<vector<vector<T>>>

Это даст вам одномерный массив vector<vector<T>>.
Каждый элемент будет одномерным массивом vector<T>.
И каждый элемент этого одномерного массива будет одномерным массивом T.

Дело в том, что vector сам не хранит свое содержимое.Он управляет частью памяти и хранит содержимое там.Это имеет ряд плохих последствий:

1. Для матрицы измерения X · Y · Z вы в конечном итоге выделите 1 + X + X·Y фрагментов памяти.Это ужасно медленно, и уничтожит кучу.Представьте себе: матрица куба размером 20 вызовет 421 вызов new!
2. Чтобы получить доступ к ячейке, у вас есть 3 уровня косвенности:
   • Вы должны получить доступ к объекту vector<vector<vector<T>>>, чтобыполучить указатель на блок памяти верхнего уровня.
   • Затем необходимо получить доступ к объекту vector<vector<T>>, чтобы получить указатель на блок памяти второго уровня.
   • Затем необходимо получить доступ к объекту vector<T>, чтобыполучить указатель на листовой блок памяти.
   • Только после этого вы сможете получить доступ к данным T.
3. Эти фрагменты памяти будут распределяться по куче, вызывая многоиз-за пропусков кэша и замедления общих вычислений.
4. Если в какой-то момент вы ошибетесь, возможно, что в вашей матрице окажется несколько строк разной длины.В конце концов, они являются независимыми массивами 1-й.

Наличие непрерывного блока памяти (например, new T[X * Y * Z]) с другой стороны дает:

1. Вы выделяете 1кусок памяти.Нет кучи, O (1).
2. Вам нужно только получить доступ к указателю на фрагмент памяти, затем можно перейти прямо к нужному элементу.
3. Вся матрица непрерывна в памяти, котораядружественный к кешу.

В те дни, одна промах кеша означает десятки или сотни потерянных вычислительных циклов, не стоит недооценивать аспект кеш-удобства.

Кстати, возможно, вы и не упомянули, возможно, лучший способ: использовать одну из многочисленных библиотек матриц, которые будут обрабатывать это для вас автоматически, и предоставлять хорошие инструменты поддержки (например, SSE).матричные операции).Одна из таких библиотек - Eigen , но есть множество других.

→ Вы хотите заниматься научными вычислениями?Позвольте lib разобраться с образцом и основами, чтобы вы могли сосредоточиться на научной вычислительной части.

Answer 4

С моей точки зрения, у std::vector слишком много преимуществ по сравнению с обычными простыми массивами.

Короче, вот некоторые из них:

• Это намного сложнеесоздать утечки памяти с std::vector.Один этот момент является одним из самых больших преимуществ.Это не имеет никакого отношения к производительности, но должно учитываться постоянно.
• std::vector является частью STL.Эта часть C ++ является одной из наиболее часто используемых.Тысячи людей используют STL и поэтому их "проверяют" каждый день.За последние годы они были оптимизированы настолько радикально, что им больше не хватает производительности.(пожалуйста, поправьте меня, если я вижу это неправильно)
• Обработка с std::vector проста как 1, 2, 3. Нет обработки указателя, нет ничего ... Просто доступ к нему через методы или с помощью [] -оператораи другие методы.