Мне нужно выводить на экран массив размером около 1000x1000 . Если постоянно обращаться к элементам массива через [][] , это занимает долго времени. Хочу сделать через указатели. Так же должно быть быстрее. Как лучше сделать пробег по такому массиву с наименьшим временем через указатели?
-
2Нет, так не должно быть быстрее. Вас кто-то дезинформировал.– VladD21 фев 2014 в 15:38
-
1Можно потрахаться, выделить память одним куском, потом сгенерить массив указателей, расставить их по этому куску памяти и итерироваться так, как говорит @aknew про статический массив. Получится одно разыменование вместо двух, и это хорошо. Но стоит ли игра свечь? Еще раз повторюсь, вывод в 90% случаев медленнее доступа. codepaste.net/oddae7– free_ze21 фев 2014 в 15:50
-
Иначе, выделяя динамическом массиве, выделяя строки отдельно, они у тебя будут храниться отдельно. Т.е. сначала нужно найти указатель на нужную строку (один раз разыменовали), затем со смещением разыменовываем и указатель на конкретный элемент (два). Косвенное обращение дольше, чем непосредственное, потому, чем меньше разыменований, тем лучше.– free_ze21 фев 2014 в 16:03
-
1@Dexter384 Чтобы без указателей на начало строки переходить с одной строки на другую, вычисляя только смещение от элемента (0;0), тебе необходимо точно знать, где начинается следующая строка. Если ты делаешь new для каждой строки, то ты этого знать не можешь, ибо стандартным аллокатором управляет БОХ!– free_ze21 фев 2014 в 16:09
-
1@Dexter384 Да. Повторю еще раз: память выделяется один раз для всей матрицы строкой (одномерный массив или "буфер"). Строка за строкой, т.е. за крайним элементом каждой строки идет первый элемент следующей. Также мы создаем массив указателей на строки (чтобы так де удобно, как и раньше можно было ходить arr[i][j]), циклом заставляем указывать их на первый элемент каждой строки. В итоге: мы можем перемещаться быстро используя синтаксис arr[i+j] и по-старому, но дольше - arr[i][j].– free_ze21 фев 2014 в 16:21
3 ответа
Ты думаешь, если был бы выигрыш, то компилятор не догадался бы оптимизировать ptr[ i ][ j ] как
*( *( prt + i ) + j )
?
Да и, с большой долей вероятности, боттлнеком у тебя будут именно функции вывода, а не доступа.
-
1только не ((a+i)+j) , а ((a+i*length)+j), где length - длинна одной строки. Но в целом все верно - компилятор и сам прекрасно справляется с такими оптимизациями, а читаемость кода скорее всего упадет– aknew21 фев 2014 в 12:32
-
@aknew Вы считаете, что строки двумерного массива обязательно идут друг за другом?– free_ze21 фев 2014 в 12:46
-
именно так, память одномерна, так что двумерные массивы по дефолту это куча одномерных записаных друг за другом. Я правда не помню строки там или столбцы если честно. По вашей же формуле невозможно отличить a[2][5] от a[5][2]– aknew21 фев 2014 в 12:49
-
@aknew Вы обратили внимание на операторы разыменования в моем коде? Вопрос на засыпку: выделяя память динамически, вы создаете массив указателей, затем, по каждому из этих указателей выделяете буфер памяти. Вопрос: будут ли эти буферы располагаться один за другим? Есть ли разница в порядке создания этих буферов? И, наконец, как себя там поведет ваш код?– free_ze21 фев 2014 в 12:51
-
нет, разименование прозевал, каюсь. По поводу второго - мы же про статику говорим, иначе наши с вами фразы про умный компилер теряют смысл. Для динамики, насколько я понимаю, у нас есть массив указателей на первые элементы массивов-строк (расположеных не по порядку в массиве, а по порядку выделения и строго говоря даже не в одной области памяти) и располагается все это добро в куче (а вот статические могут быть и в стеке). Только тогда можно еще сказать и "а что если вместо массива будет список?" и тогда адресная арифметика вообще будет курить в сторонке– aknew21 фев 2014 в 13:03
А почему вы уверены, что это даст прирост производительности? Ведь объявление вида
#define WIDTH 1000
#define HEIGHT 1000
int a[WIDTH][HEIGHT];
практически аналогично (если не принимать во внимание фрагментацию памяти и алгоритмы аллокатора) вот этому:
int ** a = new int*[WIDTH];
for (int i = 0; i < WIDTH; i++) {
a[i] = new int[HEIGHT];
}
Объявления массивов через указатели имеет смысл только если вы заранее (на стадии компиляции) не знаете размер массива и вынуждены выделять память динамически. А вот что действительно может ускорить работу с двумерным массивом, так это объявление его как одномерного и доступ к его элементам через адресную арифметику:
int a[WIDTH * HEIGHT];
a[i * WIDTH + j];
Эта запись аналогична этой:
int a[WIDTH][HEIGHT];
a[i][j];
-
@fori1ton, может это и зависит от компилятора, но для большинства скорость доступа что к a[i * WIDTH + j]; что к a[i][j]; будет одинакова. -- Но, сей прием крайне полезно помнить для гибкой работы с матрицами, передавемыми как параметр в функцию.– avp21 фев 2014 в 13:47
-
1@avp, мне кажется, что нет. В первом случае будет два чтения из памяти, а во втором одно.– dzhioev21 фев 2014 в 14:36
-
1@dzhioev, это как? Если предположить, что речь идет о локальных переменных и
WIDTH
известна во время компиляции, то в обеих случаях потребуется извлечь из память толькоi
иj
(ну, и машинные инструкции с закодированными константами (WIDTH
(при записиa[i][j]
константаWIDTH
это размер строки, она известна компилятору, но явно в тексте программы не присутствует),sizeof(a[0][0])
и смещениеa[0][0]
отfp
(stack frame pointer)). Т.е. и там и там 3 обращения (считая выборкуa[i][j]
).– avp21 фев 2014 в 19:38
Раз тут пошла такая пьянка, расскажу немного про указатели, которые указывают на двумерные массивы в памяти.
int** mat = new int*[N];
Вот здесь будет выделено n-ое число указателей, которые следуют друг за другом (проверить можете легко).
ptrdiff_t diff = (mat + N) - mat;
Далее мы выделяем память для этих mat[n] = PTR
указателей, ведь диспетчер памяти не обязан выделять память строго друг за другом потому, что это не противоречит самой идеи указателей (здесь фрагментация как таковая роли не играет).
Возьмём, к примеру, разряжённую матрицу, в которой каждая строка это односвязной список.
node** mat = new node*[N];
m[0] - здесь связной список
m[1] - здесь связной список
m[n]...
А вот пример, как пройтись одними указателями по динамическому двумерному массиву.
#include <stdio.h>
#define ROWS 10
#define COLS 20
int main(void) {
int** mat = new int*[ROWS];
for(int j = 0; j < ROWS; ++j)
mat[j] = new int[COLS];
int** ptr = (int**)mat;
int** end = (int**)mat + ROWS;
int* e;
while(ptr != end) {
e = (int*)*ptr + COLS; // конечный запредельный адрес текущего массива
for(int* i = *ptr; i != e; )
*i++ = 0;
++ptr; // смещаемся к следующему массиву
}
for(int r = 0; r < ROWS; ++r)
delete[] mat[r];
delete[] mat;
return 0;
}
Другое дело статический двумерный массив: вот как раз тут элементы матрицы расположены в памяти друг за другом.
#include <stdio.h>
#define ROWS 10
#define COLS 20
int main(void) {
int mat[ROWS][COLS];
int* ptr = (int*)mat;
int* end = (int*)mat[ROWS];
while(ptr != end)
*ptr++ = 0;
return 0;
}
Dexter384, так что в твоём вопросе никакой экономии на спичках не будет. В asm для удобства также есть индексация массивов, только индекс массива умножаем на размер типа, то бишь удобно чтобы лишний раз регистр не смещать туда-сюда. В С/С++ компилятор эту работу делает за нас, то есть умножает на размер типа, если доступ к массиву по индексу, а если через указатель — то смещение на n-байт (то есть на размер типа).
#include <stdio.h>
//asm(INTEL) x86 32-bits
int main(void) {
int _arr[4];
__asm {
mov edx, 100
mov ebx, 200
lea esi, _arr
// записываем в третий элемент массива по-индексу
mov [esi+2*4], ebx
// смещаемся ко второму элементу ++ptr
add esi, 4
mov [esi], edx
};
printf("%d\n%d\n", _arr[1], _arr[2]);
return 0;
}
И последнее — для того, чтобы лишний раз куча не фрагментировалась, лучше использовать
int* mat = new int[ROWS*COLS];