for 循环嵌套性能

矫情吗；* 2022-06-14 06:06 229阅读 0赞

比较两个方法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),那么，很明显，第二段代码的执行效率要高于第一段时钟的执行效率。`