日常开发中，我们经常会遇到类似这样的嵌套循环：
for (int i = 0; i < outterLoopCount; i++) for (int j = 0; j < innerLoopCount; j++) doSomething();
一般的说法是把循环次数少的循环放在外面，如jdk里java.util.Collections.disjoint(Collection<?> c1, Collection<?> c2)的实现.
public static boolean disjoint(Collection c1, Collection c2) { /* * We're going to iterate through c1 and test for inclusion in c2. * If c1 is a Set and c2 isn't, swap the collections. Otherwise, * place the shorter collection in c1. Hopefully this heuristic * will minimize the cost of the operation. */ if ((c1 instanceof Set) && !(c2 instanceof Set) || (c1.size() > c2.size())) { Collection tmp = c1; c1 = c2; c2 = tmp; } for (Object e : c1) if (c2.contains(e)) return false; return true; }
这种方法是出于减少循环次数的目的，能减少 (大循环长度 - 小循环长度)次循环，但这样能保证效率总是最优吗？
static void loop() { int[][] arr = new int[1000000][10]; // 第一个循环，大循环放在里面 long start = System.currentTimeMillis(); for (int i = 0; i < 10; i++) for (int j = 0; j < 1000000; j++) arr[j][i] = i + j; long loop1End = System.currentTimeMillis(); // 第二个循环，大循环放在外面 for (int i = 0; i < 1000000; i++) for (int j = 0; j < 10; j++) arr[i][j] = i + j; long loop2End = System.currentTimeMillis(); System.out.println(loop1End - start); System.out.println(loop2End - loop1End); }
在我的机器上运行，第二个循环总是比第一个循环快。
所以将循环次数少的循环放在外面只考虑到了循环次数，并没有考虑到单次循环花费的时间，并不总是正确的优化方法。那么怎样才对正确的优化循环呢？我首先想到的是对其建立模型求解。有两个循环loop1, loop2,次数为分别为 x,y ,单次循环时间分别为 a,b;
设x > y >= 0;a >= 0;b >= 0;解：设 n = x - y, 则 n >0 且为常数, y = x - n;两种组合花费的时间分别为：
loop1 在外，loop2 在内: x(a + b * y) #1式
loop1 在内，loop2 在外：y(b + a * x) #2式时间差t为:
t = #1 - #2t = (b - a) x^2 + (n + 1)(a - b)x + bn
(1) 当a==b时，t是常量bn;
(2) 当a<>b时，是一个二次函数，根据我们设置的条件，不能得到惟一的函数图形。
其顶点为: ((n + 1) / 2 , (a -b)(n + 1) ^ 2 / 4);
落在t轴上的坐标为: (0, bn);
落在x轴上的坐标为: 1/2的 (n + 1) ^ 2 + 4bn / (a - b) 平方根 - (n + 1);
说到最后，依然无法得出指导性的优化原则，当然了，一般编程时并不需要去考虑这种问题，对代码效率影响太小了，并没有什么太多的实际意义。