具有良好局部性的程序快鱼，傾向于訪問(wèn)相同的數(shù)據(jù)，或者訪問(wèn)鄰近的數(shù)據(jù)抹竹。
因?yàn)榈谝淮卧L問(wèn)后窃判，被訪問(wèn)的數(shù)據(jù)及其鄰近的數(shù)據(jù)（在同一個(gè)塊里）被緩存了，下次繼續(xù)訪問(wèn)可以命中緩存
具有良好局部性的程序袄琳，傾向于從更高層次的存儲(chǔ)結(jié)構(gòu)訪問(wèn)數(shù)據(jù)唆樊。
高層次的存儲(chǔ)結(jié)構(gòu)是低層次的存儲(chǔ)結(jié)構(gòu)的緩存，層次越高窗轩，訪問(wèn)速度越快
image.png
image.png
局部性有2種不同的形式
- 時(shí)間局部性: 在一個(gè)具有良好時(shí)間局部性的程序中痢艺，如果一個(gè)存儲(chǔ)位置被引用了，很可能在不久的將來(lái)被再次引用
- 空間局部性: 在一個(gè)具有良好空間局部性的程序中色建，如果一個(gè)存儲(chǔ)位置被引用了舌缤，很可能在不久的將來(lái)引用其附近的存儲(chǔ)位置
以二維數(shù)組的求和為例某残，看一下局部性原理對(duì)程序性能的影響有多大陵吸。
定義一個(gè)M*N的二維數(shù)組，用兩種不同的順序遍歷數(shù)組進(jìn)行求和澳厢。
public class TestLocality {
private static final int M = 2000;
private static final int N = 3000;
public static void main(String[] args) {
int[][] arr = new int[M][N];
init(arr);
int testTimes = 10;
int totalTime1 = 0, totalTime2 = 0;
for (int i = 0; i < testTimes; i++) {
long time1 = test1(arr);
long time2 = test2(arr);
totalTime1 += time1;
totalTime2 += time2;
}
System.out.println("average time1: " + totalTime1 / testTimes + "ms");
System.out.println("average time2: " + totalTime2 / testTimes + "ms");
}
private static void init(int[][] arr) {
int num = 0;
for (int i = 0; i < M; i ++) {
for (int j = 0; j < N; j++) {
arr[i][j] = num++;
}
}
}
/**
* 按照行順序掃描
*/
private static long test1(int[][] arr) {
long sum = 0;
long start = System.currentTimeMillis();
for (int i = 0; i < M; i ++) {
for (int j = 0; j < N; j++) {
sum += arr[i][j];
}
}
return System.currentTimeMillis() - start;
}
/**
* 按照列順序掃描
*/
private static long test2(int[][] arr) {
long sum = 0;
long start = System.currentTimeMillis();
for (int i = 0; i < N; i ++) {
for (int j = 0; j < M; j++) {
sum += arr[j][i];
}
}
return System.currentTimeMillis() - start;
}
}
打印結(jié)果
average time1: 4ms
average time2: 47ms
test1方法剩拢，按照數(shù)組存儲(chǔ)順序進(jìn)行訪問(wèn)饶唤，具有良好的空間局部性，10次運(yùn)行平均耗時(shí)4ms
image.png
test2方法办素，沒(méi)有按照數(shù)組存儲(chǔ)順序進(jìn)行訪問(wèn)熬尺，不具備良好的空間局部性谓罗，10次運(yùn)行平均耗時(shí)47ms
image.png
