for 循环嵌套性能

比较两个方法t1和t2的运行速度

#include
#include
using namespace std;
#define A_NUM 10000000
#define B_NUM 1000

void t1 (int *b ) {
    int i, j;
    for ( i = 0; i < A_NUM; i ++ ) { 
        for ( j = 0; j < B_NUM; j ++ ) { 
            b[ j ] ++; 
        } 
    } 
} 
void t2 (int *a ) { 
    int i, j; 	
    for ( j = 0; j < B_NUM; j ++ ) { 
        for ( i = 0; i < A_NUM; i ++ ) { 
            a[ i ] ++; 
        } 
    } 
}

int main(){
	int * b = new int[B_NUM];
	int* a = new int[A_NUM];
	for (int j = 0; j < B_NUM; j ++ )
		b[ j ] =0;
	for (int i = 0; i < A_NUM; i ++ ) 
        a[ i ] =0; 
	clock_t ibegin, iend;
	ibegin = clock();
	t1 (b);
	iend = clock();
	cout<<"t1 (b)运行时间："<

/*
进行数组访问时，操作系统需要将相关内存页面载入cache中，一个页面的大小是有限的，
如果程序需要访问页面外的内存数据，操作系统需要进行换页操作，这个操作是耗时的。
t1访问的内存区域大小为1000，系统不需要或极少需要换页。t2需要访问的内存区域大小为1000000，
系统需要多次换页，比较耗时。简单的讲，t1具有较好的程序局部性。这题需要具备一些操作系统或微机原理的知识。
*/

从cache大小来分析，tl运行速度快。因为cache调入次数少；从局部性原理和缺页率来分析，t2运行速度快。因为t2的缺页率更小。

牛客网：https://www.nowcoder.com/questionTerminal/4541d33f47174e9eb79c77d9d9920e93

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

1). for ( i= 0;  i < 1000000;  i++)

      for (j =0; j < 100; j++)

          {expression;}

 

2). for ( i= 0;  i < 100;  i++)

      for (j =0; j < 1000000; j++)

          {expression;}

看jump指令，

第一个汇编代码中，jg  A指令和 jump B 指令，正常情况下，jg  A被执行了1000000次，而jump B 指令被执行了 100* 1000000次，

第二个汇编代码中，jg  A指令和 jump B 指令，正常情况下，jg  A被执行了100次，而jump B 指令被执行了 100* 1000000次，

在两个代码中，jump B 指令被执行的次数相等，而在第二段代码中jg  A指令执行的次数比第一段代码中执行的次数少1000000次，那么一个jump指令大概执行的一个时钟循环(clock cycle),那么，很明显，第二段代码的执行效率要高于第一段时钟的执行效率。