0

Мне нужно выводить на экран массив размером около 1000x1000 . Если постоянно обращаться к элементам массива через [][] , это занимает долго времени. Хочу сделать через указатели. Так же должно быть быстрее. Как лучше сделать пробег по такому массиву с наименьшим временем через указатели?

7
  • 2
    Нет, так не должно быть быстрее. Вас кто-то дезинформировал.
    – VladD
    21 фев 2014 в 15:38
  • 1
    Можно потрахаться, выделить память одним куском, потом сгенерить массив указателей, расставить их по этому куску памяти и итерироваться так, как говорит @aknew про статический массив. Получится одно разыменование вместо двух, и это хорошо. Но стоит ли игра свечь? Еще раз повторюсь, вывод в 90% случаев медленнее доступа. codepaste.net/oddae7
    – free_ze
    21 фев 2014 в 15:50
  • Иначе, выделяя динамическом массиве, выделяя строки отдельно, они у тебя будут храниться отдельно. Т.е. сначала нужно найти указатель на нужную строку (один раз разыменовали), затем со смещением разыменовываем и указатель на конкретный элемент (два). Косвенное обращение дольше, чем непосредственное, потому, чем меньше разыменований, тем лучше.
    – free_ze
    21 фев 2014 в 16:03
  • 1
    @Dexter384 Чтобы без указателей на начало строки переходить с одной строки на другую, вычисляя только смещение от элемента (0;0), тебе необходимо точно знать, где начинается следующая строка. Если ты делаешь new для каждой строки, то ты этого знать не можешь, ибо стандартным аллокатором управляет БОХ!
    – free_ze
    21 фев 2014 в 16:09
  • 1
    @Dexter384 Да. Повторю еще раз: память выделяется один раз для всей матрицы строкой (одномерный массив или "буфер"). Строка за строкой, т.е. за крайним элементом каждой строки идет первый элемент следующей. Также мы создаем массив указателей на строки (чтобы так де удобно, как и раньше можно было ходить arr[i][j]), циклом заставляем указывать их на первый элемент каждой строки. В итоге: мы можем перемещаться быстро используя синтаксис arr[i+j] и по-старому, но дольше - arr[i][j].
    – free_ze
    21 фев 2014 в 16:21

3 ответа 3

7

Ты думаешь, если был бы выигрыш, то компилятор не догадался бы оптимизировать ptr[ i ][ j ] как

*( *( prt + i ) + j )

?

Да и, с большой долей вероятности, боттлнеком у тебя будут именно функции вывода, а не доступа.

9
  • 1
    только не ((a+i)+j) , а ((a+i*length)+j), где length - длинна одной строки. Но в целом все верно - компилятор и сам прекрасно справляется с такими оптимизациями, а читаемость кода скорее всего упадет
    – aknew
    21 фев 2014 в 12:32
  • @aknew Вы считаете, что строки двумерного массива обязательно идут друг за другом?
    – free_ze
    21 фев 2014 в 12:46
  • именно так, память одномерна, так что двумерные массивы по дефолту это куча одномерных записаных друг за другом. Я правда не помню строки там или столбцы если честно. По вашей же формуле невозможно отличить a[2][5] от a[5][2]
    – aknew
    21 фев 2014 в 12:49
  • @aknew Вы обратили внимание на операторы разыменования в моем коде? Вопрос на засыпку: выделяя память динамически, вы создаете массив указателей, затем, по каждому из этих указателей выделяете буфер памяти. Вопрос: будут ли эти буферы располагаться один за другим? Есть ли разница в порядке создания этих буферов? И, наконец, как себя там поведет ваш код?
    – free_ze
    21 фев 2014 в 12:51
  • нет, разименование прозевал, каюсь. По поводу второго - мы же про статику говорим, иначе наши с вами фразы про умный компилер теряют смысл. Для динамики, насколько я понимаю, у нас есть массив указателей на первые элементы массивов-строк (расположеных не по порядку в массиве, а по порядку выделения и строго говоря даже не в одной области памяти) и располагается все это добро в куче (а вот статические могут быть и в стеке). Только тогда можно еще сказать и "а что если вместо массива будет список?" и тогда адресная арифметика вообще будет курить в сторонке
    – aknew
    21 фев 2014 в 13:03
3

А почему вы уверены, что это даст прирост производительности? Ведь объявление вида

#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];
3
  • @fori1ton, может это и зависит от компилятора, но для большинства скорость доступа что к a[i * WIDTH + j]; что к a[i][j]; будет одинакова. -- Но, сей прием крайне полезно помнить для гибкой работы с матрицами, передавемыми как параметр в функцию.
    – avp
    21 фев 2014 в 13:47
  • 1
    @avp, мне кажется, что нет. В первом случае будет два чтения из памяти, а во втором одно.
    – dzhioev
    21 фев 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]).
    – avp
    21 фев 2014 в 19:38
3

Раз тут пошла такая пьянка, расскажу немного про указатели, которые указывают на двумерные массивы в памяти.

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];

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.