1D або 2D масив, що швидше?

Я в необхідності представляти 2D поля (осі х, у) і я стикаюся з проблемою: Чи повинен я використовувати 1D масив або 2D масив?

Я можу уявити, що перерахунок індексів для 1D масивів (y + x * n) може бути повільніше, ніж при використанні 2D масиву (x, y), але я можу уявити, що 1D може бути в кеші процесора ..

Я зробив деякий googling, але тільки знайдені сторінки щодо статичного масиву (і заявивши, що 1D і 2D в основному однакові). Але мої масиви повинні бути динамічними.

Отже, що

  1. швидше,
  2. менший (RAM)

динамічні 1D масиви або динамічні 2D масиви?

Дякую :)

48
Коротка консультація експертів для чисельності реального світу: Way "rel =" nofollow noreferrer "> fftw.org/doc/… . Це навіть дає обхідний шлях, щоб мати краще з обох світів.
додано Автор alfC, джерело
Не повинно бути ніякої різниці, оскільки ваш 2D масив зберігається в пам'яті як 1D, так що коли ви викликаєте arr [x] [y] внутрішньо, він все ще обчислює (& arr [0] [0]) ) [x * dim + y]
додано Автор Alexandru Barbarosie, джерело
Незалежно від методу індексування, який використовується, наприклад, arr [n * i + j] або arr [i] [j] , вартість індексації буде значно затьмарена будь-якими затримками кешу . Витратьте зусилля на мінімізацію затримок кешу.
додано Автор NovaDenizen, джерело
@KonradRudolph Ви праві, я повністю пропустив динамічну частину питання.
додано Автор juanchopanza, джерело
@KonradRudolph, який не був би 2D-масивом, це було б :-)
додано Автор juanchopanza, джерело
@juan Технічно вірно, але OP, ймовірно, говорить про динамічний масив (тобто T ** ), а не про реальний масив. Таким чином, він більше не є суміжним.
додано Автор Konrad Rudolph, джерело
@juanchopanza У звичайному використанні це абсолютно 2D масив. Насправді, якщо хтось прямо не говорить про статичні довжини, я завжди припускаю динамічні масиви, і я майже завжди правий. Крім того, OP явно згадує, що йому потрібні динамічні масиви.
додано Автор Konrad Rudolph, джерело
Тільки правило , яке я з упевненістю можу сказати, що завжди буде вірним, є "Виміряйте два підходи і подивіться, який для вас швидше". Що таке швидше швидше, є підхід, коли ви робите один суміжний розподіл з еквівалентним індексом, обчисленим з двох індексів.
додано Автор Happy Green Kid Naps, джерело
@Paladin - Ви повинні використовувати 2D динамічний масив (вектор). Не тому, що це швидше, а тому, що це кращий дизайн.
додано Автор tfmontague, джерело

7 Відповіді

tl; dr: Ви, напевно, повинні використовувати одновимірний підхід.

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

1. Що швидше?

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

2. Що менше?

Dynamic-1D споживає менше пам'яті, ніж 2D-підхід. Останнє також вимагає додаткових асигнувань.

Зауваження

I laid out a pretty long answer beneath with several reasons but I want to make some Зауваження on your assumptions first.

Можна собі уявити, що перерахунок індексів для 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) проти lea (1d). Перший має латентність 3 циклів і максимальну пропускну здатність 2 за цикл, в той час як останній має затримку 2 циклів і максимальну пропускну здатність 3 за цикл. (Відповідно до таблиць інструкцій - Agner Fog Оскільки відмінності є незначними, я думаю, що не має бути великої різниці в продуктивності, що виникає внаслідок перерахунку індексу. Я очікую, що це дуже малоймовірно, щоб визначити цю різницю як вузьке місце в будь-якій програмі.

Це підводить нас до наступного (і більш цікавого) пункту:

... але я можу уявити, що 1D може бути в кеші процесора ...

Правда, але 2d також може бути в кеші процесора. Див. Місцеположення недоліків: пам'ять для пояснення, чому 1d все ще краще.

Довга відповідь, або чому динамічне 2-мірне зберігання даних (покажчик-покажчик або вектор-вектора) є "поганим" для простих /малих матриць.

Примітка: Це стосується динамічних масивів/схем виділення [malloc/new/vector etc.]. Статичний масив 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, відображених у випадку 1d :

  • The green square is the only required pointer int *
  • The blue squares ensemble the memory region for all matrix elements (16 x int).

Real 2d vs mapped 2d memory layout

Це означає, що (при використанні лівого макета) ви, мабуть, будете спостерігати гіршу продуктивність, ніж для безперервного шаблону зберігання (як видно справа), наприклад, через кешування.

Скажімо, лінія кеш-пам'яті - це "кількість даних, що передаються в кеш одночасно", і уявімо собі, що програма звертається до всього матриці за одним елементом за іншим.

Якщо у вас є правильно вирівняна 4 рази 4 матриця з 32-х бітових значень, то процесор з 64-байтовою лінією кешу (типовим значенням) здатний «одноразовим» даними (4 * 4 * 4 = 64 байти). Якщо ви починаєте обробку і дані ще не знаходяться в кеші, ви будете стикатися з пропуском кешу, і дані будуть вилучені з основної пам'яті. Це навантаження може одночасно вилучити всю матрицю, оскільки вона вписується в лінію кешу, якщо і тільки якщо вона послідовно зберігається (і правильно вирівняна). Можливо, не буде більше промаху під час обробки цих даних.

У випадку динамічної, "реальної двовимірної" системи з незв'язаними місцями кожного рядка/стовпця, процесор повинен окремо завантажувати кожну пам'ять. Незважаючи на те, що потрібно лише 64 байта, завантаження 4 ліній кешу для 4 не пов'язаних між собою позицій пам'яті - у найгіршому випадку - перенесення 256 байт і витрата пропускної здатності 75%. Якщо ви обробляєте дані за допомогою 2d-схеми, ви знову (якщо ще не кешовані) зіткнетеся з пропуском кешу на першому елементі. Але тепер, тільки перший рядок/colum буде в кеші після першого завантаження з основної пам'яті, тому що всі інші рядки розташовані в іншому місці в пам'яті, а не поруч з першим. Як тільки ви досягнете нового рядка/стовпця, знову буде пропущено кеш-пам'ять і буде виконано наступне завантаження з основної пам'яті.

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

Часте розміщення/вивільнення

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

Тому створення та копіювання таких матриць дорожче, на відміну від однієї схеми розподілу.

Це стає ще гіршим із зростанням числа рядків.

Накладні витрати на пам'ять

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

Пам'ятаємо: ми хочемо зберегти матрицю 4 × 4 int, що означає 64 байти.

Для матриці NxM, що зберігається з представленою схемою покажчик-покажчик, ми споживаємо

  • N*M*sizeof(int) [the actual blue data] +
  • N*sizeof(int*) [the green pointers] +
  • sizeof(int**) [the violet variable p] bytes.

That makes 4*4*4 + 4*4 + 4 = 84 bytes in case of the present Приклад and it gets even worse when using std::vector>. It will require N * M * sizeof(int) + N * sizeof(vector) + sizeof(vector>) bytes, that is 4*4*4 + 4*16 + 16 = 144 bytes in total, intead of 64 bytes for 4 x 4 int.

Крім того, залежно від використовуваного розподільника кожен окремий розподіл може (і, швидше за все, буде) мати ще 16 байт накладних витрат пам'яті. (Деякі «Інфобайти», які зберігають кількість виділених байт з метою належного звільнення.)

Це означає, що найгіршим є:

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/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

Резюме

Є випадки, коли "реальні 2d" макети пам'яті підходять і мають сенс (тобто, якщо кількість стовпців на рядок не є постійним), але в найпростіших і поширених випадках 2D зберігання даних, вони просто роздувають складність вашого коду і зменшують продуктивність і ефективність пам'яті вашої програми.

Альтернатива

Ви повинні використовувати суцільний блок пам'яті і зіставити рядки на цьому блоці.

"C ++ спосіб" робити це, ймовірно, щоб написати клас, який управляє вашою пам'яттю при розгляді важливих речей, як

Приклад

To provide an idea of how such a class may look like, here's a simple Приклад with some basic features:

  • 2d-size-constructible
  • 2d-resizable
  • operator(size_t, size_t) for 2d- row major element access
  • at(size_t, size_t) for checked 2d-row major element access
  • Fulfills Concept requirements for Container

Джерело:

#include 
#include 
#include 
#include 

namespace matrices
{

  template
  class simple
  {
  public:
   //misc types
    using data_type  = std::vector;
    using value_type = typename std::vector::value_type;
    using size_type  = typename std::vector::size_type;
   //ref
    using reference       = typename std::vector::reference;
    using const_reference = typename std::vector::const_reference;
   //iter
    using iterator       = typename std::vector::iterator;
    using const_iterator = typename std::vector::const_iterator;
   //reverse iter
    using reverse_iterator       = typename std::vector::reverse_iterator;
    using const_reverse_iterator = typename std::vector::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
  void swap(simple & lhs, simple & rhs)
  {
    lhs.swap(rhs);
  }
  template
  bool operator== (simple const &a, simple 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
  bool operator!= (simple const &a, simple const &b)
  {
    return !(a == b);
  }

}

Зверніть увагу на кілька речей:

  • T needs to fulfill the requirements of the used std::vector member functions
  • operator() doesn't do any "of of range" checks
  • No need to manage data on your own
  • No destructor, copy constructor or assignment operators required

Так що вам не доведеться турбуватися про належну обробку пам'яті для кожної програми, але тільки один раз для класу, який ви пишете.

Обмеження

Можливі випадки, коли динамічна "реальна" двовимірна структура є сприятливою. Це, наприклад, випадок, якщо

  • матриця дуже велика і розріджена (якщо будь-який з рядків навіть не потрібно виділяти, але може бути оброблений за допомогою nullptr) або
  • рядки не мають однакової кількості стовпців (тобто якщо у вас взагалі немає матриці, а інша двовимірна конструкція).
158
додано
У мене є 2 основні причини використання прикладу покажчика. Перш за все, це має складну компонування пам'яті (стандарт не має гарантії того, як сам вектор виглядає), а другий момент полягає в тому, що більшість "наївних підходів" я бачу тут на покажчиках SO.
додано Автор Pixelchemist, джерело
Нещодавно я додав відповідь про comon макет std :: vector і як його викладено в пам'яті. Можливо, це представляє інтерес щодо цього питання. c ++ Вектор, що відбувається, коли він розширюється/relocate на стек?
додано Автор Pixelchemist, джерело
@FrankH Це те, що я маю на увазі під " Купа виділень вимагає відповідної обробки виключень, щоб уникнути витоку пам'яті, якщо один з асигнувань провалиться! " @ ** Ризик витоку пам'яті **, але я думаю, що я Вам доведеться переглядати, щоб просунутися далі, що трохи далі.
додано Автор Pixelchemist, джерело
@beesleep: Так .. це відбувається, коли ви копіюєте та вставляєте operator() і наполовину перейменовуєте його в at ;)
додано Автор Pixelchemist, джерело
Суміжна пам'ять дозволяє компілятору краще авторизуватися з SIMD. Наприклад, цей код отримав 50x прискорення за допомогою плоского масиву замість покажчиків до покажчиків . (Це був майже найгірший випадок: тривимірна матриця покажчиків на покажчики на рядки лише 4 подвійних і цикл у неправильному порядку для місцевості, якщо речі були виділені переважно безперервно.) не повідомили про прискорення нового вузького місця , але воно має бути значним
додано Автор Peter Cordes, джерело
Це гарна відповідь, але чому ви наполягаєте на використанні (і обговорення взагалі) сирих покажчиків у вашому прикладі? У сучасному C ++ немає підстав. Просто використовуйте std :: vector і виконуйте його.
додано Автор Konrad Rudolph, джерело
Приклад збірки є оманливим. Він передбачає C == 4 , для більшого чи змінного C потрібно mul або принаймні додатковий shl . Це, напевно, ще не змінює картину.
додано Автор zch, джерело
Фантастична відповідь; Ви повинні блогувати його :)
додано Автор Brennan Vincent, джерело
Існує й інша причина, чому "2D динамічний масив" є поганим, але, швидше за все, вам вдасться вкусити лише від великих розмірів: пам'яті. Оскільки "динамічний розподіл" цього стилю вимагає принаймні двох викликів до нового (першого для масиву T * [N] , другий для T [N * M] ), тому ви також повинні try {} catch {} навколо кожного або ви втратите пам'ять, якщо перший успішно завершиться 2-й кидок. Справжнім винуватцем є те, що C ++/STL ніколи не турбувався зі стандартним класом matrix . Якщо Fortran отримав що-небудь прямо над C/C ++, то це один ...
додано Автор FrankH., джерело
Тут немає декількох помилок: reference at() (size_type const row, size_type const column) {return m_data.at (m_cols * row + column); } в операторі() (size_type const row, size_type const колонка) const {return m_data.at (m_cols * row + column); } ? Чи не слід його змінювати на посилання на (size_type const row, size_type const, стовпець) і const_reference at (size_type const row, size_type const, column) const ?
додано Автор beesleep, джерело
Я знаю ... Це відбувається весь час. Без злочину зробили :-D. Дякуємо за код до речі, милий маленький і ефективний фрагмент роботи!
додано Автор beesleep, джерело

Unless you are talking about static arrays, 1D is faster.

Here’s the memory layout of a 1D array (std::vector):

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

And here’s the same for a dynamic 2D array (std::vector>):

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

Зрозуміло, що 2D випадок втрачає локалізацію кешу і використовує більше пам'яті. Він також вводить додаткову непряму (і, таким чином, додатковий вказівник), але перший масив має накладні витрати при обчисленні показників, тому вони навіть більше або менше.

15
додано
Хороша відповідь. Я також думав про пропуски кешу на динамічному 2d-масиві
додано Автор Alex, джерело

1D і 2D статичні масиви

  • Розмір . Для обох сторінок потрібна однакова кількість пам'яті.

  • Швидкість. Можна припустити, що різниця швидкості не буде, оскільки пам'ять обох цих масивів повинна бути суміжною ( весь 2D масив повинен виглядати як один фрагмент у пам'яті, а не як a купа шматочків поширюється по всій пам'яті). (Це може бути компілятор залежний.)

Динамічні масиви 1D та 2D

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

  • Швидкість: масив 1D може бути швидшим, ніж 2D-масив, оскільки пам'ять для 2D-масиву не буде суміжною, тому пропуски в кеші стануть проблемою.


Використовуйте те, що працює і здається найбільш логічним, і якщо ви зіткнулися з проблемами швидкості, то рефактор.

8
додано
Як я вже вказував, 4x4 vector> (системно залежить) потребуватиме 164 байта, де 100 байтів є накладними. Я б не назвав це "крихітним" (це коефіцієнт> 2,5), особливо якщо вам потрібно обробляти багато хто з них, або якщо вам потрібно копіювати їх дуже часто. (Звичайно, втрачається значення зі зростаючим числом стовпців.)
додано Автор Pixelchemist, джерело
На швидкості, це також залежить від того, як ви використовуєте масив. Обчислення зсуву для випадково доступних елементів є однаковим, але якщо ви хочете повторити всі елементи, то з одновимірним масивом легко перебирати лінійно, а не з вкладеними циклами або з множенням багатовимірних координат на зміщення пам'яті.
додано Автор Boann, джерело
динамічний "2D масив" - це масив покажчиків, що вказують на інші масиви. Таким чином, він вимагає більше місця, ніж 1D масив.
додано Автор juanchopanza, джерело
@Pixelchemist Це правда, і я не згадав про це, тому що я очікую, що його масиви будуть досить великими, якщо він буде турбуватися про швидкість. : P (Думаю, що краще сказати так явно)
додано Автор Mohamad Ali Baydoun, джерело
Ой, це правда. Дякуємо, що ви зробили цю корекцію. @ mr5 Std :: vector буде вести себе як динамічний масив 1D, оскільки він був запрограмований таким чином. (Коли ми говоримо статичний , ми не маємо на увазі статичне ключове слово per se)
додано Автор Mohamad Ali Baydoun, джерело
"Немає різниці в швидкості". Це дійсно залежить від того, як компілятор обчислює зміщення для 2D масивів.
додано Автор SigTerm, джерело
Але як щодо статичного std :: vector статичного чи динамічного? На жаль, у мене немає можливості розрізняти ці.
додано Автор mr5, джерело

Існуючі відповіді лише порівнюють 1-D масиви з масивами покажчиків.

У C (але не C ++) є третій варіант; Ви можете мати безперервний 2-D масив, який динамічно виділяється і має розміри виконання:

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

і це доступно, як p [row_index] [col_index] .

Я б очікував, що це буде дуже схоже на 1-D масив, але це дає вам кращий синтаксис для доступу до осередків.

У C ++ можна досягти чогось подібного, визначивши клас, який внутрішньо зберігає 1-D масив, але може виставляти його через синтаксис доступу до 2-D масивів, використовуючи перевантажені оператори. Знову я очікую, що мати подібну або ідентичну продуктивність до простого 1-D масиву.

4
додано
@Paladin C і C ++ є різними мовами, кожна з яких має деякі особливості, інші не мають, а деякі загальні функції реалізовані по-різному. Спробуйте запустити g ++ у стандартному режимі, і ви отримаєте діагностику, за замовчуванням у нього є деякі розширення.
додано Автор M.M, джерело
@vsoftco у вашому коді C ++ num_cols має бути постійним виразом, але в моєму коді його можна визначити під час виконання
додано Автор M.M, джерело
@ M.M У C (але не C + +) є третій варіант Чому тільки в C? У C ++ можна легко зробити int (* p) [num_cols] = new int [num_rows] [num_cols]; delete [] p; .
додано Автор vsoftco, джерело
@ М. М. Ох, я бачу, спасибі! Так дійсно, lhs є покажчиком на VLA в C, хороший момент!
додано Автор vsoftco, джерело
Це звучить дивно, щоб бути чесним, я завжди думав, що практично будь-який дійсний C дійсний C ++ .. g ++ 4.8.3 приймає цей код .com/Te2n1XhZ ...
додано Автор Paladin, джерело

Інша відмінність 1D і 2D масивів з'являється в розподілі пам'яті. Ми не можемо бути впевнені, що члени 2D-масиву є послідовними.

4
додано
Так. І це може мати серйозний вплив, коли мова, про який йде мова, полягає в тому, що 1% критично важливого коду.
додано Автор Arcane Engineer, джерело

Це дійсно залежить від того, як ваш 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.

1
додано

Мені дуже подобається ретельна відповідь, надана Pixelchemist . Більш простий варіант цього рішення може бути наступним. По-перше, оголосити розміри:

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

Далі створіть псевдонім і, отримуйте і встановіть методи:

template
using Vector = std::vector;

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

template
inline const T& get_elem(const vector& 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 .

0
додано
IT KPI C/С++ новым годом
IT KPI C/С++ новым годом
747 учасників

Чат обсуждения С/С++. - Вопросы "напишите за меня лабу" - это оффтоп. - Оффтоп, флуд, оскорбления и вбросы здесь не приняты. - За нарушение - предупреждение или mute на неделю. - За спам и рекламу - ban. Все чаты IT KPI: https://t.me/itkpi/1147