Подтвердить что ты не робот

Что такое соглашение индексации 2D-массива с координатами x/y в C?

Я пишу небольшую программу, в которой мне приходилось использовать систему координат на борту (x/y в 2d-массиве) и думал, следует ли использовать индексирование как array[x][y], что кажется мне более естественным или array[y][x], который будет лучше соответствовать тому, как массив представлен в памяти. Я считаю, что оба эти метода будут работать, если я буду последовательно, и это просто проблема с именами, но как насчет соглашений при написании больших программ?

Ответ 1

В моей области (обработка изображений) соглашение [y][x] более обычное. Независимо от того, что вы делаете, будьте последовательны и хорошо документируйте.

Ответ 2

Вы также должны рассмотреть, что вы собираетесь делать с этими массивами, и важно ли это критически важно для времени.

Как указано в комментариях: Элемент a[r][c+1] находится рядом с a[r][c]. Этот факт может оказать значительное влияние на производительность при повторении более крупных массивов. Правильный порядок обхода приведет к тому, что линии кэша будут полностью использованы: при обращении к одному индексу массива он считается "вероятным", после чего будет доступен следующий индекс, и весь блок памяти будет загружен в кэш. Если после этого вы получаете доступ к совершенно другому местоположению памяти (а именно к одному в следующей строке), то пропускная способность этого кэша пропадает.

Если возможно, вы должны попытаться использовать порядок обхода, соответствующий размеру макета.

_{(Конечно, это касается "условностей" и "привычек": при записи доступа к массиву, например, a[row][col], это обычно интерпретируется как доступ к массиву a[y][x] из-за соглашения x - ось горизонтальная, а ось y - вертикальная...)}

Вот небольшой пример, демонстрирующий потенциальное влияние "неправильного" порядка обхода:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

float computeSumRowMajor(float **array, int rows, int cols)
{
    float sum = 0;
    for (int r=0; r<rows; r++)
    {
        for (int c=0; c<cols; c++)
        {
            sum += array[r][c];
        }
    }
    return sum;
}

float computeSumColMajor(float **array, int rows, int cols)
{
    float sum = 0;
    for (int c=0; c<cols; c++)
    {
        for (int r=0; r<rows; r++)
        {
            sum += array[r][c];
        }
    }
    return sum;
}


int main()
{
    int rows = 5000;
    int cols = 5000;
    float **array = (float**)malloc(rows*sizeof(float*));
    for (int r=0; r<rows; r++)
    {
        array[r] = (float*)malloc(cols*sizeof(float));
        for (int c=0; c<cols; c++)
        {
            array[r][c] = 0.01f;
        }
    }

    clock_t start, end;

    start = clock();
    float sumRowMajor = 0;
    for (int i=0; i<10; i++)
    {
        sumRowMajor += computeSumRowMajor(array, rows, cols);
    }
    end = clock();
    double timeRowMajor = ((double) (end - start)) / CLOCKS_PER_SEC;    

    start = clock();
    float sumColMajor = 0;
    for (int i=0; i<10; i++)
    {
        sumColMajor += computeSumColMajor(array, rows, cols);
    }
    end = clock();
    double timeColMajor = ((double) (end - start)) / CLOCKS_PER_SEC;    

    printf("Row major %f, result %f\n", timeRowMajor, sumRowMajor);
    printf("Col major %f, result %f\n", timeColMajor, sumColMajor);
    return 0;
}

_{(извинения, если я нарушил некоторые лучшие практики здесь, я обычно парень Java...)}

Для меня доступ к ряду строк почти на порядок быстрее, чем доступ к столбцу. Конечно, точные цифры будут сильно зависеть от целевой системы, но общая проблема должна быть одинаковой для всех целей.