Java 优化技术（5）

look_w

运行程序既然已经完成了第一个解拼图程序，那么我们就可以运行它以找出 Meteor 拼图的所有可能的解决方案。前几节中描述的源代码可从源代码下载的         meteor.initial 包中找到。这个包含有         Solver 类，该类具有         solve() 方法和用以启动程序的         main() 方法。         Solver 类的构造器初始化所有拼图块，然后将它们添加到         pieceList 。我们可以使用         java meteor.initial.Solver 启动程序。      
程序开始搜索解决方案，但如您将注意到的，它似乎什么解决方案也找不到。实际上，它确实能找到所有可能的解决方案，但您必须很耐心。找到一个解决方案就要花几个小时。我们的测试计算机是一台运行 RedHat Linux 7.2 和 Java 1.4.0 的具有 512MB RAM 的 Athlon XP 1500+，它大约花了 8 小时才找到了第一个解决方案。找出所有解决方案即使不需要几年，也需要几个月。
很明显，我们遇到了性能问题。优化的第一个候选方法是解拼图算法。当前我们正在使用一种幼稚的蛮力方法来找出所有可能的解决方案。我们应该对这个算法进行微调。我们能做的第二件事是对临时数据进行高速缓存。例如，我们可以对那些排列进行高速缓存，而不是每次都重新计算块的排列。最后，我们可以设法应用某些低级别的优化技术，诸如避免不必要的方法调用。在下几节中，我们将研究这些优化技术。
改进算法回顾        清单 1 并思考如何能够优化我们的初始解拼图算法。优化算法的一种好方法是使其可视化。可视化允许我们更好地理解正在实现的过程及其可能的缺点。下几节讨论可以辨别的两个低效率的实现。我们将解拼图程序的实际可视化代码留给感兴趣的读者。      
孤岛检测剪枝清单 1中的算法将块（或者更精确地说是块的块单元）放到图板上的每个合适位置。图 4 显示了过程开始时可能的图板状态。蓝色块的当前排列已经被放置在第一个可用的图板位置上，并且黄色块的当前排列已经被移动到其第二个可能的图板位置上。然后，我们的算法继续处理第三个块，以此类推。然而如果我们仔细看图 4，很明显，在图板的这些位置上放置蓝色和黄色的块不可能成为解决方案。原因是那两块已经形成了由三个相邻空单元组成的        孤岛。因为所有拼图块都由 5 个单元构成，所以无法填充这个孤岛。我们的算法努力尝试填充图板其余 8 块的工作都是徒劳的。如果我们在图板上检测到一个无法填充的孤岛，则需要调整我们的算法。      
图 4. 图板上的孤岛教科书中将这种中断递归搜索算法的过程称为        剪枝。将剪枝函数添加到我们的         Solver 类中是很容易的。在每次递归调用         solve() 方法前，我们都要检查图板上的孤岛。如果我们发现构成孤岛的空单元数不是 5 的倍数，我们就不进行递归调用。而算法继续当前级别的递归。清单 7 和 8 显示了必需的代码调整：      
清单 7. 带剪枝的解拼图算法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public class Solver {   public void solve() {     ...             if (!prune()) solve();     ...   }   private boolean prune() {     /* We'll use the processed field of board cells to avoid     infinite loops */     board.resetProcessed();     for (int i = 0; i < Board.NUMBEROFCELLS; i++) {       if (board.getBoardCell(i).getIslandSize()%Piece.NUMBEROFCELLS != 0) {         // We have found an unsolvable island         return true;       }     }     return false;   } }

清单 8. getIslandSize() 方法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

public class BoardCell {   public int getIslandSize() {     if (!isProcessed() && isEmpty()) {       setProcessed(true); // Avoid infinite recursion       int numberOfCellsInIsland = 1; // this cell       for (int i = 0; i < Cell.NUMBEROFSIDES; i++) {         BoardCell neighbour=(BoardCell)getNeighbour(i);         if (neighbour != null) {           numberOfCellsInIsland += neighbour.getIslandSize();         }       }       return numberOfCellsInIsland;     }     else {       return 0;     }   } }