【计算机系统】局部性

（一）理解局部性：

时间局部性：被引用过一次的内存位置，很有可能在不远的将来再次被引用。（引用可以理解为访问）
空间局部性：步长决定空间局部性的好坏，一般而言：步长越大，空间局部性越差。
顺序引用模式：步长为1的引用模式，例如一维数组（具有连续内存空间的数据结构）、二维数组（行优先）

（二）为什么要引入局部性？

局部性好的程序比局部性差的程序运行的更快。（原因后期补充：先挖个坑）

举个例子：对一维数组的所有元素进行求和

int SumArr(int* arr, int len)
{
	if(NULL == arr || len <= 0)
	{
		return -1;
	}
	int sum = 0;
	for(int i = 0; i < len; i++)
	{
		sum += arr[i];
	}
	return sum;
}

分析：

对于sum来说，具有较好的时间局部性（访问频率高），不具备空间局部性（sum是标量）
对于arr来说，具有很好的空间局部性（地址连续，访问速度快），时间局部性差（arr每个元素只使用一次）

关键的变量	时间局部性	空间局部性
sum	好	无
arr	差	好

结论：对于一个程序来说，要么具有好的时间局部性，要么具有好的空间局部性，该程序具有较好的局部性

1. 小试身手

（1）行优先：对一个二维数组所有元素求和

//int Sum2DArr(int (*parr)[col], int row, int col)
int Sum2DArr(int parr[row][col], int row, int col)
{
	//注意：形参parr会退化成数组指针，原型如上个注释所示
	if(NULL == parr || row <= 0 || col <= 0)
	{
		return -1;
	}
	int sum = 0;
	//行优先 求和
	for(int i = 0; i < row; i++)
	{
		for(int j = 0; j < col; j++)
		{
			sum += parr[i][j];
		}
	}
	return sum;
}

分析：

关键的变量	时间局部性	空间局部性
sum	好	无
parr	差	好

2. 小试身手

（1）列优先：对一个二维数组所有元素求和

//int Sum2DArr(int (*parr)[col], int row, int col)
int Sum2DArr(int parr[row][col], int row, int col)
{
	//注意：形参parr会退化成数组指针，原型如上个注释所示
	if(NULL == parr || row <= 0 || col <= 0)
	{
		return -1;
	}
	int sum = 0;
	//行优先 求和
	for(int i = 0; i < col; i++)
	{
		for(int j = 0; j < row; j++)
		{
			sum += parr[i][j];
		}
	}
	return sum;
}