HDU4920 Matrix multiplication(CPU cache가 프로그램에 미치는 영향)
Given two matrices A and B of size n×n, find the product of them.
bobo hates big integers. So you are only asked to find the result modulo 3.
Input
The input consists of several tests. For each tests:
The first line contains n (1≤n≤800). Each of the following n lines contain n integers -- the description of the matrix A. The j-th integer in the i-th line equals A
ij. The next n lines describe the matrix B in similar format (0≤A
ij,B
ij≤10
9).
Output
For each tests:
Print n lines. Each of them contain n integers -- the matrix A×B in similar format.
Sample Input
1
0
1
2
0 1
2 3
4 5
6 7
Sample Output
0
0 1
2 1
고전적인 행렬 곱셈은 3층 순환(최내층 순환)이 k에 대한 순환이기 때문에 b[k][j]는 b에 대한 열을 따라 접근한다.우리는 메모리에서 2차원 그룹이 행위 단위로 연속적으로 저장되는 것을 알고 있으며, 열별로 방문하면 매번 1000*4 (bytes) 를 뛴다.cpu cache의 교체 정책에 따라 대량의 cache가 효력을 상실할 것입니다.
그래서 square2.cpp는 j 순환과 k 순환을 위치를 교환합니다. 이렇게 하면 보장합니다.
c[i][j] += a[i][k] * b[k][j];
이 문장은 메모리에 대한 접근이 연속적이며cache의 명중률을 증가시켜 프로그램의 실행 속도를 크게 향상시켰다.
구체적인 예:http://blog.csdn.net/a775700879/article/details/11750703
코드는 다음과 같습니다.
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 810;
int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];
int n;
int main()
{
while(~scanf("%d",&n)){
int i,j,k;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&a[i][j]);
a[i][j]%=3;
c[i][j]=0;
}
}
for(i=0;i<n;i++)
for(int j=0;j<n;j++){
scanf("%d",&b[i][j]);
b[i][j]%=3;
}
for(i=0;i<n;i++)
for(k=0;k<n;k++)
for(j=0;j<n;j++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
for(i=0;i<n;i++){
for(j=0;j<n-1;j++)
printf("%d ",c[i][j]%3);
printf("%d
",c[i][n-1]%3);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
