Java 优化技术（7）

look_w

对中间结果进行高速缓存重新设计我们的解拼图算法极大地提高了程序的执行速度。对于进一步的优化，我们将必须研究技术性的性能技术。Java 程序中要考虑的一个重要问题是垃圾收集。您可以使用         -verbose:gc 命令行开关在程序执行期间显示垃圾收集器的活动。      

1	java -verbose:gc meteor.algorithm.Solver

如果我们使用这个开关运行程序，则看到来自垃圾收集器的许多输出。对源代码的研究告诉我们问题出在对         Board 类的         placePiece() 方法的临时         ArrayList 对象的实例化（请参阅        清单 6）。我们使用这个         ArrayList 对象保存块的特定排列将占用的图板单元。最好对结果进行高速缓存以备以后引用，而不是每次都重新计算该列表。      
如果将块的某个特定单元放置在特定的图板位置上，         findOccupiedBoardCells() 方法确定将被拼图块占用的拼图图板单元。该方法的结果由三个参数确定：首先我们有拼图块或对它的排列；其次，我们有正在用来操作块的块单元；最后，我们有将要放置块的图板的单元。要对这些结果进行高速缓存，我们可以将一张表与每个可能的块排列相关联。这张表使用特定块单元索引和图板单元位置保存了那个排列的         findOccupiedBoardCells() 方法的结果。清单 10 显示了维护此类表的         Piece 类的一个更新版本：      
清单 10. 对 findOccupiedBoardCells() 方法的结果进行高速缓存

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

public class Piece {   private Piece[] permutations = new Piece[NUMBEROFPERMUTATIONS];   private ArrayList[][] occupiedBoardCells =     new ArrayList[Piece.NUMBEROFCELLS][Board.NUMBEROFCELLS];   private void generatePermutations(Board board) {     Piece prevPermutation=this;     for (int i = 0; i < NUMBEROFPERMUTATIONS; i++) {       // The original nextPermutation() has been renamed       permutations=         ((Piece)prevPermutation.clone()).nextPermutation_orig();       prevPermutation=permutations;     }     // Calculate occupied board cells for every permutation     for (int i = 0; i < NUMBEROFPERMUTATIONS; i++) {       permutations.generateOccupiedBoardCells(board);     }   }   private void generateOccupiedBoardCells(Board board) {     for (int i = 0; i < Piece.NUMBEROFCELLS; i++) {       for (int j = 0; j < Board.NUMBEROFCELLS; j++) {         occupiedBoardCells[j]=new ArrayList();         resetProcessed(); // We're going to process the piece         board.findOccupiedBoardCells(occupiedBoardCells[j],                                      pieceCells,                                      board.getBoardCell(j));       }     }   }   public Piece nextPermutation() {     if (currentPermutation == NUMBEROFPERMUTATIONS)       currentPermutation = 0;     // The new implementation of nextPermutation()     // accesses the cache     return permutations[currentPermutation++];   }   public ArrayList     getOccupiedBoardCells(int pieceCellIdx, int boardCellIdx) {     // Access requested data in cache     return occupiedBoardCells[pieceCellIdx][boardCellIdx];   } }

generatePermutations() 方法是在创建         Piece 对象时触发的。它计算了块的每个排列并对那些排列的         findOccupiedBoardCells() 方法的所有可能的结果进行了高速缓存。很明显，如果我们想计算被占用的图板单元，则我们将需要对拼图图板进行访问。还请注意，块的排列是原始的         Piece 对象的克隆。克隆         Piece 涉及对其所有单元的深层复制。      
剩余的唯一一件事是从         Board 类的         placePiece() 方法访问高速缓存，在清单 11 中显示了该方法：      
清单 11. 访问被占用的图板单元高速缓存

1 2 3 4 5 6 7 8 9

public class Board {   public boolean     placePiece(Piece piece, int pieceCellIdx, int boardCellIdx) {     // Get all the boardCells that this piece would occupy     ArrayList occupiedBoardCells =       piece.getOccupiedBoardCells(pieceCellIdx, boardCellIdx);     ...   } }

，从而导致了低级别优化的使用缺乏吸引力。