Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Скорость доступа к элементам многомерного массива

Автор: Domine 25.1.2014, 11:55

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

Автор: vinter 25.1.2014, 12:33

Цитата(Domine @ 25.1.2014, 12:55

)

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

не правильно понимаешь, N-мерный массив представлен в памяти линейно, а обращение к нему происходит путём подсчёта нужного индекса(умножение + сложение) и одного обращения к памяти.

Автор: Domine 25.1.2014, 13:14

Перефразирую вопрос, к элементам какого массива быстрее получить доступ, и серьезна-ли разница во времени:
а)

Код


T ***data = new T**[sx];
for(int x = 0; x < sx; x++)
{
    data[x] = new T*[sy];
    for(int y = 0; y < sy; y++)
    {
        data[x][y] = new T[sz];
    }
}

доступ - data[x][y][z]
и б)

Код


T *data = new T[sx * sy * sz];

где для доступа считается что-то вроде data[X * sy * sz + Y * sz + Z]

Автор: vinter 25.1.2014, 14:06

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

Автор: bsa 25.1.2014, 19:46

Цитата(vinter @ 25.1.2014, 15:06

)

Компиляторы сейчас творят чудеса, и, вполне вероятно, что никакой разницы не будет.

вариант с множеством new будет работать хуже, потому что для вычисления адреса элемента, нужно сделать 3 загрузки из случайных мест памяти. Кэш данных процессора на реальных задачах просто это не переварит, поэтому будет сильное проседание производительности. А вот умножение операция почти бесплатная, особенно, для кэша.

Автор: vinter 26.1.2014, 08:45

Цитата(bsa @ 25.1.2014, 20:46

)

Можно ведь расположить данные последовательно в куче(я не знаю, есть ли такая оптимизация, но почему нет?) и первый пример просто превратиться во второй. Нужно измерять, разницы может не быть вообще.

Автор: xvr 27.1.2014, 12:26

Все зависит от конкретных значений. В частности от размеров массивов (влезут они в кэш или нет), и от того, где и как будет вычисляться X * sy * sz + Y * sz + Z (сможет компилятор что нибудь соптимизировать или нет).

Автор: akizelokro 29.1.2014, 01:23

Код


T ***data = new T[sx][sy][sz];

А с этим почему не сравниваете? smile

Автор: mes 29.1.2014, 09:08

Цитата(akizelokro @ 29.1.2014, 00:23

)

Код


T ***data = new T[sx][sy][sz]

;