有人说,两个嵌套的for循环,把循环次数多的放在里面,效率会比较高。
这是个老话题了。网上的讨论很多。我记得我第一次见到这个问题的时候还在上高中。今天就简单的总结一下吧。
先上代码: void test1() { long dt = DateTime.Now.Ticks; for (int i = 0; i < 1000000; i++) { for (int j = 0; j < 10; j++) { a[i,j] = 0; } } Console.WriteLine("test1:{0}",DateTime.Now.Ticks - dt); }
void test2() { long dt = DateTime.Now.Ticks; for (int j = 0; j < 10; j++) { for (int i = 0; i < 1000000; i++) { a[i,j] = 0; } } Console.WriteLine("test2:{0}",DateTime.Now.Ticks - dt); }
有书上说是方法2快,道理是大的循环放在里面,效率会比较高。
不过实际的结果,一般都是方法1快,而且快很多。这是为什么呢? 这是因为当CPU从内存获取数据到cache的时候,是一块一块获取的。因此,如果我们的程序总是顺序的访问内存,那么cache的利用率就会比较高了,会大大减少系统换页的次数,提高程序运行的效率。
对于多维数组,每行的最后一个数据后面,紧接着的是下一行的第一个。因此,方法1是顺序访问内存,方法2则是跳跃性的访问内存。这样一来,谁快谁慢自然就很明了了。
不过,并不能因此就说书上说错了,更不能说把大的循环放在外面才会更高效。
再看下面的代码: void test3() { long k = 0; long dt = DateTime.Now.Ticks; for (int i = 0; i < 1000000; i++) { for (int j = 0; j < 10; j++) { k++; if (k > 100000) k++; } } Console.WriteLine("test3:{0}",DateTime.Now.Ticks - dt); }
void test4() { long k = 0; long dt = DateTime.Now.Ticks; for (int j = 0; j < 10; j++) { for (int i = 0; i < 1000000; i++) { k++; if (k > 100000) k++; } } Console.WriteLine("test4:{0}",DateTime.Now.Ticks - dt); }
实际的测试结果支持了大循环在内部会快一些的说法,虽然快的幅度很有限吧。
出现这个问题的原因,在于CPU的流水线长度和预判断功能的强弱。如果CPU流水线长,而预判定功能又很准确,那方法4的效率将超过方法3很多。如果流水线很长,但是预判定功能不好,方法4就不一定比方法3快了,甚至还会慢很多。
比如高频率的P3 CPU,流水线短,分支预判功能效果好,在上面测试方法3和方法4就区别不大。再比如低频率的P4 CPU,流水线很长,但是预判定效果差,方法4在这上面就会吃大亏。
所以,把大的循环放在最里面,并不是永恒不变的硬道理。究竟要如何取舍,还得根据实际的硬件情况和软件逻辑来做选择。更好的方法就是,选择一个合适的设计结构,避免陷入上面的问题。唯一的真理就是:实际测试一下,用事实说话。
附:测试结果: 方法:时间(tick) test1:2187500 test1:1875000 test1:1718750 test1:1718750 test1:1718750 test2:4375000 test2:4375000 test2:4218750 test2:4375000 test2:4375000 test3:1562500 test3:1406250 test3:1562500 test3:1406250 test3:1562500 test4:1093750 test4:1250000 test4:1406250 test4:1250000 test4:1250000
|