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

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

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

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

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

Везде вижу, что лучше использовать одномернный массив, а не двумерный. Всегда принимал это на правду, но сейчас задумался. Нужели умножение и сложение в 1-ой строке быстрее, чем разыменование + ещё одна адресация во второй:
C++
1
2
mas1[i * n + j] = 10; // 1
mas2[i][j] = 10; // 2
?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.08.2013, 04:17     int[][] или int[] - что быстрее?
Посмотрите здесь:

Объясните что делает int z(int a) - C++
вот весь исходный код #include <iostream> #include <stdio.h> #include <cmath> using namespace std; int z(int a) { int x, y,...

Предел int или что то еще ? - C++
Задание: Определить входит ли введенная цифра в заданное натуральное число. Вот что у меня получилось: #include <iostream.h> void...

int main () { int a=3,b=2,c; c=a+b; cout << "c=" << c; } Что не правильно? - C++
#include &lt;iostream&gt; using namespace std; int main () { int a=3,b=2,c; c=a+b; cout &lt;&lt; &quot;c=&quot; &lt;&lt; c; }в чем...

Error C4430: missing type specifier - int assumed. Note: C++ does not support default-int - C++
1&gt;d:\program files\microsoft visual studio 9.0\visual studio 2008\projects\lab1\task5\task5\task5.cpp(6) : error C4430: missing type...

[Linker Error] Unresolved external 'Sort(int, int)' referenced from H:\INFORMATIC\5\UNIT1.OBJ - C++
понять не могу откуда, собственно, ошибка, да что там. Вот код ...

Написать функцию SUM (int M, int N) / С++ для начинающих - C++
Написать функцию SUM (int M, int N), которая вычисляет и возвращает сумму всех чисел кратных 3 и 9 в пределах от M и N включительно ....

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gray_fox
What a waste!
1447 / 1176 / 61
Регистрация: 21.04.2012
Сообщений: 2,463
Завершенные тесты: 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!
1447 / 1176 / 61
Регистрация: 21.04.2012
Сообщений: 2,463
Завершенные тесты: 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!
1447 / 1176 / 61
Регистрация: 21.04.2012
Сообщений: 2,463
Завершенные тесты: 3
09.08.2013, 05:15     int[][] или int[] - что быстрее? #6
nexen, да вся эта математика выполняется мнгновенно, а вот то, что данные не локальны уже хуже, думаю, кэшу это не понравится (здесь я уже не особо разбираюсь). Считать, сколько тактов уйдёт на +, * и пр. по мне так занятие бессполезное.
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,013
09.08.2013, 05:18     int[][] или int[] - что быстрее? #7
Просто мнение: оптимизируете не то. В любом случае доступ к элементу массива осуществляется за константное время.
В случае динамического выделения памяти проще один раз определить функцию доступа к элементам и выделять память одним куском, если возможно. Тупо потому что выделений памяти будет меньше, а это уже всяко более дорогая операция, чем доступ к элементу. С другой стороны, не стоит забывать о фрагментации памяти: теоретически в системе может не быть достаточно большого непрерывного фрагмента памяти. Сам, правда, на такое особо не напарывался - не приходилось работать с таким.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
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[] - что быстрее?
Еще ссылки по теме:

Класс Int имитирующий встроенный тип int - C++
Создать класс Int (с заглавной буквы) имитирующий встроенный тип int и позволяющий следующие конструкции: Int i = 0; i = i+1; i++; ...

Int _tmain(int argc, _TCHAR* argv[]) и др - C++
Добрый день! При компилировании кода, где присутствует данная строчка int _tmain(int argc, _TCHAR* argv) выдаёт ошибку: ...

Определение типов. Приведение int к unsigned int - C++
При таком определении 5 рассматривается как int. Как при определении указать что 5 будет именно unsigned int? unsigned int n=5; ...

Invalid types 'int[int]' for array subscript - C++
Добрый день! Не компилится код. Выдается ошибка invalid types 'int' for array subscript в строке a=abs(a-1); Помогите,...


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

Или воспользуйтесь поиском по форуму:
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[] - что быстрее?
Ответ Создать тему
Опции темы

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