Форум программистов, компьютерный форум CyberForum.ru

int[][] или int[] - что быстрее? - C++

Восстановить пароль Регистрация
 
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
09.08.2013, 04:17     int[][] или int[] - что быстрее? #1
Везде вижу, что лучше использовать одномернный массив, а не двумерный. Всегда принимал это на правду, но сейчас задумался. Нужели умножение и сложение в 1-ой строке быстрее, чем разыменование + ещё одна адресация во второй:
C++
1
2
mas1[i * n + j] = 10; // 1
mas2[i][j] = 10; // 2
?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
09.08.2013, 04:27     int[][] или int[] - что быстрее? #2
nexen, если на стеке, то без разницы, двумерный массив - это всё равно один блок памяти. Другое дело когда выделяется в куче массив указателей, а потом ещё n массивов - выделить один кусок будет эффективнее.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
09.08.2013, 04:35  [ТС]     int[][] или int[] - что быстрее? #3
gray_fox, выделить - возможно, но обращаться к массиву всё же будет быстрее через [][]?
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
09.08.2013, 04:42     int[][] или int[] - что быстрее? #4
nexen, нет. Будет массив указателей + n массивов значений - всё эти массивы будут "раскиданы" в куче, как заблагорассудиться ОС. Разыменовав первый указатель, надо перейти по полученному адресу в другой блок памяти, потом ещё раз разыменовать. Имея одномерный массив, надо лишь посчитать сдвиг и разыменовать.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
09.08.2013, 05:04  [ТС]     int[][] или int[] - что быстрее? #5
gray_fox, ну так подсчет сдвига - умножение. А умножение гораздо медленее сложения. В итоге что имеем:
Первый подход: адресная арифметика (переход по адресу), разыменование (берем адрес по адресу), адресная арифметика (переход по адресу), разыменование (забираем значение)
Второй подход: умножение, сумма, адресная арифметика, разыменование.
Точно ли умножение и сумма выиграют разыменование и адресную арифметику и, если да, выходит, что разыменование крайне дорогая операция?..
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
09.08.2013, 05:15     int[][] или int[] - что быстрее? #6
nexen, да вся эта математика выполняется мнгновенно, а вот то, что данные не локальны уже хуже, думаю, кэшу это не понравится (здесь я уже не особо разбираюсь). Считать, сколько тактов уйдёт на +, * и пр. по мне так занятие бессполезное.
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
09.08.2013, 05:18     int[][] или int[] - что быстрее? #7
Просто мнение: оптимизируете не то. В любом случае доступ к элементу массива осуществляется за константное время.
В случае динамического выделения памяти проще один раз определить функцию доступа к элементам и выделять память одним куском, если возможно. Тупо потому что выделений памяти будет меньше, а это уже всяко более дорогая операция, чем доступ к элементу. С другой стороны, не стоит забывать о фрагментации памяти: теоретически в системе может не быть достаточно большого непрерывного фрагмента памяти. Сам, правда, на такое особо не напарывался - не приходилось работать с таким.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
09.08.2013, 15:18     int[][] или int[] - что быстрее? #8
обострение у вас, ребята, какое-то...

Добавлено через 1 минуту
одни неделю пытаются задачу решить, сэкономив 2 символа, другие в поте лица размышляют, как лучше массив объявить... успех...
alex1392
31 / 31 / 3
Регистрация: 24.07.2013
Сообщений: 187
09.08.2013, 15:21     int[][] или int[] - что быстрее? #9
Цитата Сообщение от salam Посмотреть сообщение
обострение у вас, ребята, какое-то...

Добавлено через 1 минуту
одни неделю пытаются задачу решить, сэкономив 2 символа, другие в поте лица размышляют, как лучше массив объявить... успех...
Война фи-я главное маневры
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.08.2013, 15:35     int[][] или int[] - что быстрее?
Еще ссылки по теме:

Ошибка при компиляции error: cannot convert ‘int (*)[5]’ to ‘int**’ for argument ‘1’ to ‘void Replase(int**)' C++
C++ Error LNK2019: unresolved external symbol "public: __thiscall Vector<int>::Vector<int>(int,int,int)" (?0?$Vec
C++ В каком случае надо начинать с int main() или с int _tmain( int argc, _TCHAR* argv[] ) и т.д.?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
NEbO
583 / 451 / 49
Регистрация: 22.01.2009
Сообщений: 1,173
Записей в блоге: 1
Завершенные тесты: 1
09.08.2013, 15:35     int[][] или int[] - что быстрее? #10
если применяется в глубоко вложенном цикле (сталкивался например, при обработке изображений), используйте [], при последовательном чтении. При "[][]", вероятно (ну смотря какой у вас массив: в сишном компилятор поймет, и скомпилирует в тот же самый код, что и "[]"), потребуется два обращения к памяти, причем к разным блокам. Из-за этого при обращении на первом [] в кеш данных грузиться будет вся строка, а читаться только одно число. Вот это и есть неэффективное использование кеша (нужные строки могут удалиться).
Если цикл не сильно вложенный, то действительно задумываться об этом не стоит. Если же вам жизненно необходим эффективный и высокопроизводительный код, то о кеше забывать нельзя.
Прочтите http://habrahabr.ru/post/93263/ , там отличные примеры
Yandex
Объявления
09.08.2013, 15:35     int[][] или int[] - что быстрее?
Ответ Создать тему
Опции темы

Текущее время: 09:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru