Матрица

[Tural]

Программа находит обратную матрицу с выбором элемента по столбце или по строке методом Гаусса-Жордана. записывает матрицу в одномерный или двумерный массив. Все 4 вар. выложил.
Вопрос: Почему прога которая считает обратную матрицу с выбором элемента по строке находит гораздо быстрее чем та же самая прога переделанная для нахождения с выбором эл.-та по столбце? Проги 2postr, 1postr находят обратную матрицу 1000x1000 за 15-20 сек а 2postlb, 1postlb за 150-160 сек. Для проверки запустите программу и введите размер матрицы. Например: 1000

 

[lazybiz]

Есть такая штука, Кэш называется. (

Ссылка скрыта от гостей

)

 

[Tural]

Есть такая штука, Кэш называется. (

Ссылка скрыта от гостей

)

Я знаю есть такая штука. Можеш подробно обяснить почему это происходит?

 

[lazybiz]

Давай попробую...

Допустим у тебя есть матрица:

char mat[1000][1000];

И тебе нужно вычислить сумму первой строки:

sum += mat[0][i];

Элементы строки расположены последовательно, т.е. один за другим в памяти компьютера. В этом случае может кэшироваться вся строка, и, следовательно, цикл нахождения суммы чисел, взятых (уже) из кэша пройдет быстрее чем в следующем примере, в котором мы находим сумму первого столбца:

sum += mat[i][0];

В этом случае кэш просто не может вместить в себя всю матрицу, т.к. адрес первого слагаемого элемента будет отличаться от адреса второго как минимум на 1000 байт! И для того, чтобы вместить в кэш все первые элементы столбцов матрицы ему потребуется как минимум (1000*1000)-999 байт!!! В итоге у нас получается что мы читаем первое значение каждого столбца не из кэша, а из обычной памяти, которая хоть и быстрая сама по себе, но намного медленней памяти кэша.

А так как у всех процессоров размер кэша разный, то поэтому результаты измерения времени выполнения твоей программы будут не только меняться не линейно, но и не прапорционально.
Например у меня были вот такие результаты:
1postr : 24.898 sec.
1postlb: 69.434 sec.

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

 

[Tural]

Огромное спасибо. А ты попробовал запустить 2postlb? у меня находит за 91 сек.

 

[lazybiz]

А ты попробовал запустить 2postlb?

Нет. Для тебя это так важно?