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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
#1

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

09.08.2013, 04:17. Просмотров 624. Ответов 9
Метки нет (Все метки)

Везде вижу, что лучше использовать одномернный массив, а не двумерный. Всегда принимал это на правду, но сейчас задумался. Нужели умножение и сложение в 1-ой строке быстрее, чем разыменование + ещё одна адресация во второй:
C++
1
2
mas1[i * n + j] = 10; // 1
mas2[i][j] = 10; // 2
?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gray_fox
What a waste!
1256 / 1139 / 55
Регистрация: 21.04.2012
Сообщений: 2,361
Завершенные тесты: 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!
1256 / 1139 / 55
Регистрация: 21.04.2012
Сообщений: 2,361
Завершенные тесты: 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!
1256 / 1139 / 55
Регистрация: 21.04.2012
Сообщений: 2,361
Завершенные тесты: 3
09.08.2013, 05:15     int[][] или int[] - что быстрее? #6
nexen, да вся эта математика выполняется мнгновенно, а вот то, что данные не локальны уже хуже, думаю, кэшу это не понравится (здесь я уже не особо разбираюсь). Считать, сколько тактов уйдёт на +, * и пр. по мне так занятие бессполезное.
0x10
2454 / 1626 / 238
Регистрация: 24.11.2012
Сообщений: 4,002
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[] - что быстрее?
Еще ссылки по теме:

C++ Int _tmain(int argc, _TCHAR* argv[]) и др
Объясните что делает int z(int a) C++
Error C4430: missing type specifier - int assumed. Note: C++ does not support default-int C++
С++ ошибка error C4430: missing type specifier - int assumed. Note: C++ does not support default-int C++
Не понимаю ошибку invalid conversion from 'int' to 'int* C++

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

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

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