Ответ 1

tl; dr: Вероятно, вы должны использовать одномерный подход.

Примечание. Невозможно разобраться в деталях, влияющих на производительность при сравнении динамических 1d или динамических шаблонов хранения 2d без заполнения книг, поскольку производительность кода зависит от очень большого числа параметров. Профиль, если это возможно.

1. Что быстрее?

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

2. Что меньше?

Динамический-1D потребляет меньше памяти, чем 2D-подход. Последнее также требует больше ассигнований.

Примечания

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

Я могу себе представить, что пересчет индексов для 1D массивов (y + x * n) может быть медленнее, чем использование 2D-массива (x, y)

Сравним эти две функции:

int get_2d (int **p, int r, int c) { return p[r][c]; }
int get_1d (int *p, int r, int c)  { return p[c + C*r]; }

Сборка (не встроенная), сгенерированная Visual Studio 2015 RC для этих функций (с включенными оптимизациями):

[email protected]@[email protected] PROC
push    ebp
mov ebp, esp
mov eax, DWORD PTR _c$[ebp]
lea eax, DWORD PTR [eax+edx*4]
mov eax, DWORD PTR [ecx+eax*4]
pop ebp
ret 0

[email protected]@[email protected] PROC
push ebp
mov ebp, esp
mov ecx, DWORD PTR [ecx+edx*4]
mov eax, DWORD PTR _c$[ebp]
mov eax, DWORD PTR [ecx+eax*4]
pop ebp
ret 0

Разница заключается в mov (2d) vs. lea (1d). Первый имеет задержку в 3 цикла и максимальную пропускную способность 2 за цикл, в то время как последний имеет латентность в 2 цикла и максимальную пропускную способность 3 за цикл. (Согласно Таблицы инструкций - Agner Fog Поскольку различия незначительны, я думаю, что не должно быть большой разницы в производительности, связанной с пересчетом индекса. Я ожидаю, что очень маловероятно, чтобы эта разница сама по себе была узким местом в любой программе.

Это приводит нас к следующей (и более интересной) точке:

... но я мог бы представить, что 1D может быть в кэше CPU...

Правда, но 2d также может быть в кэше CPU. См. The Downsides: Местоположение памяти для объяснения, почему 1d все еще лучше.

Длинный ответ или почему динамическое 2-мерное хранилище данных (указатель на указатель или вектор-вектор) является "плохим" для простых/малых матриц.

Примечание. Это касается динамических массивов/схем распределения [malloc/new/vector и т.д.]. Статический 2d-массив является непрерывным блоком памяти и поэтому не подвержен минусам, которые я собираюсь представить здесь.

Проблема

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

Пример с использованием указателя на синтаксис указателя

int main (void)
{
    // allocate memory for 4x4 integers; quick & dirty
    int ** p = new int*[4];
    for (size_t i=0; i<4; ++i) p[i] = new int[4]; 

    // do some stuff here, using p[x][y] 

    // deallocate memory
    for (size_t i=0; i<4; ++i) delete[] p[i];
    delete[] p;
}

Недостатки

Местоположение памяти

Для этой "матрицы" вы выделяете один блок из четырех указателей и четыре блока из четырех целых чисел. Все распределения не связаны друг с другом и поэтому могут привести к произвольной позиции памяти.

Следующее изображение даст вам представление о том, как может выглядеть память.

Для реального 2d случая:

• Фиолетовый квадрат - это позиция памяти, занятая самой p.
• Зеленые квадраты собирают область памяти p указывает на (4 x int*).
• 4 области из 4 смежных синих квадратов - это те, на которые указывают каждая int* зеленой области

Для 2d, нанесенного на 1-й случай:

• Зеленый квадрат является единственным обязательным указателем int *
• Синие квадраты объединяют область памяти для всех матричных элементов (16 x int).

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

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

Если у вас правильно выровненная 4-кратная 4-разрядная матрица из 32-битных значений, процессор с 64-байтной строкой кэша (типичное значение) способен "одноразово" данных (4 * 4 * 4 = 64 байта), Если вы начнете обработку, а данные еще не находятся в кеше, вы столкнетесь с пропуском кеша, и данные будут извлечены из основной памяти. Эта загрузка может извлекать всю матрицу сразу, поскольку она вписывается в строку кэша, если и только если она смежно хранится (и правильно выровнена). Вероятно, не будет больше промахов при обработке этих данных.

В случае динамической, "реальной двумерной" системы с несвязанными расположениями каждой строки/столбца, процессор должен загружать каждую ячейку памяти отдельно. Несмотря на то, что требуется только 64 байта, загрузка 4 строк кэша для 4 несвязанных позиций памяти будет в худшем случае - фактически передать 256 байтов и потратить 75% пропускной способности. Если вы обрабатываете данные с помощью 2d-схемы, вы снова (если не кэшированы) сталкиваетесь с пропуском кеша на первый элемент. Но теперь только первая строка /colum будет в кеше после первого загрузки из основной памяти, потому что все остальные строки расположены где-то еще в памяти, а не рядом с первым. Как только вы достигнете новой строки/столбца, снова будет пропущен кеш, и выполняется следующая загрузка из основной памяти.

Короче говоря: у 2d-шаблона более высокая вероятность промаха в кэше с 1-й схемой, предлагающей лучший потенциал для производительности из-за локальности данных.

Частное распределение/освобождение

• Для создания нужной матрицы NxM (4 × 4) необходимы целые числа, такие как N + 1 (4 + 1 = 5) распределения (с использованием либо new, malloc, allocator:: allocate, либо любой другой).
• Необходимо также использовать такое же количество правильных, соответствующих операций освобождения.

Следовательно, создание или копирование таких матриц более выгодно, в отличие от одной схемы распределения.

Это становится все хуже с ростом числа строк.

Накладные расходы на память

Я напишу размер 32 бита для int и 32 бит для указателей. (Примечание: системная зависимость.)

Помните: мы хотим сохранить матрицу 4 × 4, что означает 64 байта.

Для матрицы NxM, сохраненной с представленной схемой указателя на указатель, мы потребляем

• N*M*sizeof(int) [фактические синие данные] +
• N*sizeof(int*) [зеленые указатели] +
• sizeof(int**) [фиолетовая переменная p] байт.

Это делает 4*4*4 + 4*4 + 4 = 84 байты в случае данного примера, и при использовании std::vector<std::vector<int>> становится еще хуже. Для этого потребуется N * M * sizeof(int) + N * sizeof(vector<int>) + sizeof(vector<vector<int>>) байтов, т.е. 4*4*4 + 4*16 + 16 = 144 байтов, всего 64 байта для 4 x 4 int.

Кроме того, в зависимости от используемого распределителя - каждое отдельное распределение может хорошо (и, скорее всего, будет) иметь еще 16 байт служебных данных памяти. (Некоторые "Infobytes", которые хранят количество выделенных байтов для надлежащего освобождения.)

Это самый худший случай:

N*(16+M*sizeof(int)) + 16+N*sizeof(int*) + sizeof(int**)
= 4*(16+4*4) + 16+4*4 + 4 = 164 bytes ! _Overhead: 156%_

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

Опасность утечки памяти

Связка распределений требует соответствующей обработки исключений, чтобы избежать утечек памяти, если одно из распределений не удастся! Вам нужно отслеживать выделенные блоки памяти, и вы не должны забывать их при освобождении памяти.

Если new пробегает память, а следующая строка не может быть выделена (особенно вероятно, когда матрица очень велика), std::bad_alloc вызывается new.

Пример:

В приведенном выше примере new/delete мы рассмотрим еще один код, если мы хотим избежать утечек в случае bad_alloc исключений.

  // allocate memory for 4x4 integers; quick & dirty
  size_t const N = 4;
  // we don't need try for this allocation
  // if it fails there is no leak
  int ** p = new int*[N];
  size_t allocs(0U);
  try 
  { // try block doing further allocations
    for (size_t i=0; i<N; ++i) 
    {
      p[i] = new int[4]; // allocate
      ++allocs; // advance counter if no exception occured
    }
  }
  catch (std::bad_alloc & be)
  { // if an exception occurs we need to free out memory
    for (size_t i=0; i<allocs; ++i) delete[] p[i]; // free all alloced p[i]s
    delete[] p; // free p
    throw; // rethrow bad_alloc
  }
  /*
     do some stuff here, using p[x][y] 
  */
  // deallocate memory accoding to the number of allocations
  for (size_t i=0; i<allocs; ++i) delete[] p[i];
  delete[] p;

Резюме

Есть случаи, когда "реальные 2d" макеты памяти подходят и имеют смысл (т.е. если количество столбцов на строку не является константой), но в самых простых и распространенных случаях хранения данных 2D они просто раздувают сложность вашего кода и снизить производительность и эффективность памяти вашей программы.

Alternative

Вы должны использовать непрерывный блок памяти и сопоставить свои строки на этом блоке.

"С++-путь" для этого - это, вероятно, написать класс, который управляет вашей памятью при рассмотрении важных вещей, таких как

• Что такое правило трех?
• Что подразумевается под инициализацией ресурсов (RAII)?
• Концепция С++: Контейнер (на cppreference.com)

Пример

Чтобы представить себе, как выглядит такой класс, вот простой пример с некоторыми основными функциями:

• 2d-размер-построимо
• 2d-изменяемая
• operator(size_t, size_t) для доступа к главному элементу с двумя строками
• at(size_t, size_t) для проверки доступа к главному элементу с 2-го ряда
• Выполняет концептуальные требования для контейнера

Источник:

#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>

namespace matrices
{

  template<class T>
  class simple
  {
  public:
    // misc types
    using data_type  = std::vector<T>;
    using value_type = typename std::vector<T>::value_type;
    using size_type  = typename std::vector<T>::size_type;
    // ref
    using reference       = typename std::vector<T>::reference;
    using const_reference = typename std::vector<T>::const_reference;
    // iter
    using iterator       = typename std::vector<T>::iterator;
    using const_iterator = typename std::vector<T>::const_iterator;
    // reverse iter
    using reverse_iterator       = typename std::vector<T>::reverse_iterator;
    using const_reverse_iterator = typename std::vector<T>::const_reverse_iterator;

    // empty construction
    simple() = default;

    // default-insert rows*cols values
    simple(size_type rows, size_type cols)
      : m_rows(rows), m_cols(cols), m_data(rows*cols)
    {}

    // copy initialized matrix rows*cols
    simple(size_type rows, size_type cols, const_reference val)
      : m_rows(rows), m_cols(cols), m_data(rows*cols, val)
    {}

    // 1d-iterators

    iterator begin() { return m_data.begin(); }
    iterator end() { return m_data.end(); }
    const_iterator begin() const { return m_data.begin(); }
    const_iterator end() const { return m_data.end(); }
    const_iterator cbegin() const { return m_data.cbegin(); }
    const_iterator cend() const { return m_data.cend(); }
    reverse_iterator rbegin() { return m_data.rbegin(); }
    reverse_iterator rend() { return m_data.rend(); }
    const_reverse_iterator rbegin() const { return m_data.rbegin(); }
    const_reverse_iterator rend() const { return m_data.rend(); }
    const_reverse_iterator crbegin() const { return m_data.crbegin(); }
    const_reverse_iterator crend() const { return m_data.crend(); }

    // element access (row major indexation)
    reference operator() (size_type const row,
      size_type const column)
    {
      return m_data[m_cols*row + column];
    }
    const_reference operator() (size_type const row,
      size_type const column) const
    {
      return m_data[m_cols*row + column];
    }
    reference at() (size_type const row, size_type const column)
    {
      return m_data.at(m_cols*row + column);
    }
    const_reference at() (size_type const row, size_type const column) const
    {
      return m_data.at(m_cols*row + column);
    }

    // resizing
    void resize(size_type new_rows, size_type new_cols)
    {
      // new matrix new_rows times new_cols
      simple tmp(new_rows, new_cols);
      // select smaller row and col size
      auto mc = std::min(m_cols, new_cols);
      auto mr = std::min(m_rows, new_rows);
      for (size_type i(0U); i < mr; ++i)
      {
        // iterators to begin of rows
        auto row = begin() + i*m_cols;
        auto tmp_row = tmp.begin() + i*new_cols;
        // move mc elements to tmp
        std::move(row, row + mc, tmp_row);
      }
      // move assignment to this
      *this = std::move(tmp);
    }

    // size and capacity
    size_type size() const { return m_data.size(); }
    size_type max_size() const { return m_data.max_size(); }
    bool empty() const { return m_data.empty(); }
    // dimensionality
    size_type rows() const { return m_rows; }
    size_type cols() const { return m_cols; }
    // data swapping
    void swap(simple &rhs)
    {
      using std::swap;
      m_data.swap(rhs.m_data);
      swap(m_rows, rhs.m_rows);
      swap(m_cols, rhs.m_cols);
    }
  private:
    // content
    size_type m_rows{ 0u };
    size_type m_cols{ 0u };
    data_type m_data{};
  };
  template<class T>
  void swap(simple<T> & lhs, simple<T> & rhs)
  {
    lhs.swap(rhs);
  }
  template<class T>
  bool operator== (simple<T> const &a, simple<T> const &b)
  {
    if (a.rows() != b.rows() || a.cols() != b.cols())
    {
      return false;
    }
    return std::equal(a.begin(), a.end(), b.begin(), b.end());
  }
  template<class T>
  bool operator!= (simple<T> const &a, simple<T> const &b)
  {
    return !(a == b);
  }

}

Обратите внимание на несколько вещей здесь:

• T должен удовлетворять требованиям используемых функций-членов std::vector
• operator() не выполняет никаких проверок "диапазона"
• Вам не нужно управлять данными самостоятельно
• Не требуется деструктор, конструктор копирования или оператор присваивания

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

Ограничения

Бывают случаи, когда динамическая "реальная" двумерная структура благоприятна. Это, например, случай, если

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

Ответ 2

Если не указано, вы говорите о статических массивах, 1D быстрее.

Сохраняет расположение памяти массива 1D (std::vector<T>):

+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+

И одинаково для динамического 2D-массива (std::vector<std::vector<T>>):

+---+---+---+
| * | * | * |
+-|-+-|-+-|-+
  |   |   V
  |   | +---+---+---+
  |   | |   |   |   |
  |   | +---+---+---+
  |   V
  | +---+---+---+
  | |   |   |   |
  | +---+---+---+
  V
+---+---+---+
|   |   |   |
+---+---+---+

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

Ответ 3

1D и 2D статические массивы

• Размер: Оба будут нуждаться в том же объеме памяти.

• Скорость:. Вы можете предположить, что не будет разницы в скорости, потому что память для обоих этих массивов должна быть смежной (The весь 2D-массив должен отображаться как один фрагмент в памяти, а не куча кусков распространяется по памяти). (Это может быть компилятор зависимо однако.)

1D и 2D динамические массивы

• Размер:. В 2D-массиве потребуется немного больше памяти, чем 1D-массив из-за указателей, необходимых в 2D-массиве, чтобы указать на набор выделенных массивов 1D. (Этот маленький бит только крошечный, когда мы говорим о действительно больших массивах. Для небольших массивов крошечный бит может быть довольно значительным относительно.)

• Скорость: 1D-массив может быть быстрее, чем 2D-массив, потому что память для 2D-массива не будет смежной, поэтому проблемы с пропуском кэша станут проблемой.

  /li >

Используйте то, что работает и кажется наиболее логичным, и если вы столкнулись с проблемами скорости, то рефакторинг.

Ответ 4

Существующие ответы только сравнивают 1-D массивы с массивами указателей.

В C (но не С++) есть третий вариант; вы можете иметь смежный двухмерный массив, динамически распределенный и имеющий размеры времени выполнения:

int (*p)[num_columns] = malloc(num_rows * sizeof *p);

и к нему обращаются как p[row_index][col_index].

Я ожидаю, что это будет очень похоже на работу с массивом с 1-D массивом, но дает вам более удобный синтаксис для доступа к ячейкам.

В С++ вы можете добиться чего-то подобного, указав класс, который поддерживает одномерный массив внутри, но может выставить его через синтаксис доступа к двумерному массиву с использованием перегруженных операторов. Опять же, я ожидал бы, что аналогичная или идентичная производительность будет равна 1-мерному массиву.

Ответ 5

В распределении памяти появляется другое отличие 1D и 2D-массивов. Мы не можем быть уверены, что члены 2D-массива будут секвенциальными.

Ответ 6

Это действительно зависит от того, как реализован ваш 2D массив.

рассмотрим код ниже:

int a[200], b[10][20], *c[10], *d[10];
for (ii = 0; ii < 10; ++ii)
{
   c[ii] = &b[ii][0];
   d[ii] = (int*) malloc(20 * sizeof(int));    // The cast for C++ only.
}

Здесь есть 3 реализации: b, c и d

Не будет большой разницы в доступе к b[x][y] или a[x*20 + y], поскольку один - это вы выполняете вычисления, а другой - компилятор, который делает это за вас. c[x][y] и d[x][y] медленнее, потому что машина должна найти адрес, на который указывает c[x] а затем получить доступ к y-му элементу оттуда. Это не одно прямое вычисление. На некоторых машинах (например, AS400, который имеет 36-битные (не битовые) указатели), доступ к указателю является чрезвычайно медленным. Все зависит от используемой архитектуры. В архитектурах типа x86 a и b имеют одинаковую скорость, c и d медленнее, чем b.

Ответ 7

Мне нравится тщательный ответ Pixelchemist. Более простая версия этого решения может быть следующей. Сначала объявите размеры:

constexpr int M = 16; // rows
constexpr int N = 16; // columns
constexpr int P = 16; // planes

Затем создайте псевдоним и, получите и установите методы:

template<typename T>
using Vector = std::vector<T>;

template<typename T>
inline T& set_elem(vector<T>& m_, size_t i_, size_t j_, size_t k_)
{
    // check indexes here...
    return m_[i_*N*P + j_*P + k_];
}

template<typename T>
inline const T& get_elem(const vector<T>& m_, size_t i_, size_t j_, size_t k_)
{
    // check indexes here...
    return m_[i_*N*P + j_*P + k_];
}

Наконец, вектор может быть создан и проиндексирован следующим образом:

Vector array3d(M*N*P, 0);            // create 3-d array containing M*N*P zero ints
set_elem(array3d, 0, 0, 1) = 5;      // array3d[0][0][1] = 5
auto n = get_elem(array3d, 0, 0, 1); // n = 5

Определение размера вектора при инициализации обеспечивает оптимальную производительность. Это решение модифицировано из этого ответа. Функции могут быть перегружены для поддержки различных размеров с помощью одного вектора. Недостатком этого решения является то, что параметры M, N, P неявно передаются функциям get и set. Это можно решить, реализовав решение внутри класса, как это сделано Pixelchemist.