Язык программирования C

цаA[i][j] дано. Если мы хотим добавить элементы матрицы, какой метод лучше и почему?

мудрый столбецгребной

С моей точки зрения, строка лучше, поскольку элементы представления массива хранятся в смежных местах памяти, поэтому доступ к ним занимает меньше времени. Но так как при извлечении ОЗУ каждое место занимает одинаковое время, имеет ли это значение?

 algo-geeks17 янв. 2011 г., 18:55
я использую язык с
 Karmastan17 янв. 2011 г., 18:49
Какой язык вы используете? Разные языки имеют разные представления для матриц, и это влияет на то, как их следует использовать.

Ответы на вопрос(3)

Решение Вопроса

Извлекать выгодуПространственная местность

В C матрицы хранятся в rпоследний заказ, Так что, если вы получите доступ к элементуa[i][j], доступ к элементуa[i][j+1] скорее всего попадет в кеш. Доступ к основной памяти не будет выполнен. Кэши быстрее основной памяти, поэтому структура доступа имеет значение.

Конечно, необходимо учитывать больше факторов, таких как доступ на запись / доступ на чтение, политика записи (запись через, запись с обратной записью / выделение при записи, без выделения при записи), многоуровневые кэши и так далее. Но это кажется излишним для этого вопроса.

Повеселитесь с помощью инструмента профилирования, такого какпохожем на Cachegrindи убедитесь сами.

Например, рассмотрим фиктивную программу с доступом к 4-мегабайтным матрицам. Проверьте различия между коэффициентами пропуска на каждом шаблоне доступа.

доступ к столбцу

$ cat col_major.c 
#include <stdio.h>

int main(){

    size_t i,j;

    const size_t dim = 1024 ;

    int matrix [dim][dim];

    for (i=0;i< dim; i++){
        for (j=0;j <dim;j++){
            matrix[j][i]= i*j;
        }
    }
    return 0;
}

$ valgrind --tool=cachegrind ./col_major 

==3228== D   refs:      10,548,665  (9,482,149 rd   + 1,066,516 wr)
==3228== D1  misses:     1,049,704  (      968 rd   + 1,048,736 wr)
==3228== L2d misses:     1,049,623  (      893 rd   + 1,048,730 wr)
==3228== D1  miss rate:        9.9% (      0.0%     +      98.3%  )
==3228== L2d miss rate:        9.9% (      0.0%     +      98.3%  )

доступ к строке

$ cat row_major.c 
#include <stdio.h>

int main(){
    size_t i,j;
    const size_t dim = 1024 ;
    int matrix [dim][dim];

    for (i=0;i< dim; i++)
        for (j=0;j <dim;j++)
            matrix[i][j]= i*j;

    return 0;
}

$ valgrind --tool=cachegrind ./row_major 

==3524== D   refs:      10,548,665  (9,482,149 rd   + 1,066,516 wr)
==3524== D1  misses:        66,664  (      968 rd   +    65,696 wr)
==3524== L2d misses:        66,583  (      893 rd   +    65,690 wr)
==3524== D1  miss rate:        0.6% (      0.0%     +       6.1%  )
==3524== L2d miss rate:        0.6% (      0.0%     +       6.1%  )
 Niklas R15 июн. 2012 г., 15:48
Могу ли я спросить вас, если вы хотели написатьi< dim а такжеj <dim?
 Tom15 июн. 2012 г., 18:10
Что вы имеете в виду?
 JorenHeit16 янв. 2013 г., 11:59
@Tom Если вы сохраняете свои матрицы главным столбцом, вы должны перебирать их в главном порядке столбцов, верно? Это исправит ошибки в кеше, или я что-то упустил?
 algo-geeks18 янв. 2011 г., 04:40
действительно спасибо .. :)
 Ed.17 янв. 2011 г., 19:13
Ударь меня к этому ....

это не важно. Если они большие, то время чтения может пострадать. Большой проблемой является кеш. Если вы не можете ожидать, что ваша полная матрица будет загружена в кэш за один раз, то вы хотите минимизировать количество ошибок, с которыми вы сталкиваетесь, потому что работа с потерей кеша относительно трудоемка.

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

int a[MAX_I][MAX_J];
for (i = 0; i < MAX_I; ++i) {
   for (j = 0; j < MAX_J; ++j) {
      /* process a[i][j] */
   }
}

Причина этого заключается в том, что язык C обрабатывает массивы как указатели со смещениями, см .:Язык программирования C.

Ваш ответ на вопрос