Java最適化手法

                
public void solve() {
  if (!pieceList.isEmpty()) {
    // Take the first available piece
    Piece currentPiece = (Piece)pieceList.remove(0);

    for (int i = 0; i < Piece.NUMBEROFPERMUTATIONS; i++) {
      Piece permutation = currentPiece.nextPermutation();

      for (int j = 0; j < Board.NUMBEROFCELLS; j++) {
        if (board.placePiece(permutation, j)) {
          
          /* We have now put a piece on the board, so we have to
             continue this process with the next piece by 
             recursively calling the solve() method */
          
          solve();
          
          /* We're back from the recursion and we have to continue
             searching at this level, so we remove the piece we
             just added from the board */
          
          board.removePiece(permutation);
        }
        // Else the permutation doesn't fit on the board
      }
    }

    // We're done with this piece
    pieceList.add(0, currentPiece);
  }
  else {
    
    /* All pieces have been placed on the board so we
       have found a solution! */
    
    puzzleSolved();
  }
}

                
public class Cell {
  public static final int NUMBEROFSIDES = 6;

  // The sides of a cell
  public static final int EAST      = 0;
  public static final int SOUTHEAST = 1;
  public static final int SOUTHWEST = 2;
  public static final int WEST      = 3;
  public static final int NORTHWEST = 4;
  public static final int NORTHEAST = 5;

  private Cell[] neighbours = new Cell[NUMBEROFSIDES];

  private boolean processed = false;

  public Cell getNeighbour(int side) {
    return neighbours[side];
  }

  public void setNeighbour(int side, Cell cell) {
    neighbours[side] = cell;
  }

  public boolean isProcessed() {
    return processed;
  }

  public void setProcessed(boolean b) {
    processed = b;
  }
}

                
public class PieceCell extends Cell {
  public void flip() {
    Cell buffer = getNeighbour(NORTHEAST);
    setNeighbour(NORTHEAST, getNeighbour(NORTHWEST));
    setNeighbour(NORTHWEST, buffer);
    buffer = getNeighbour(EAST);
    setNeighbour(EAST, getNeighbour(WEST));
    setNeighbour(WEST, buffer);
    buffer = getNeighbour(SOUTHEAST);
    setNeighbour(SOUTHEAST, getNeighbour(SOUTHWEST));
    setNeighbour(SOUTHWEST, buffer);
  }

  public void rotate() {
    // Clockwise rotation
    Cell eastNeighbour = getNeighbour(EAST);
    setNeighbour(EAST, getNeighbour(NORTHEAST));
    setNeighbour(NORTHEAST, getNeighbour(NORTHWEST));
    setNeighbour(NORTHWEST, getNeighbour(WEST));
    setNeighbour(WEST, getNeighbour(SOUTHWEST));
    setNeighbour(SOUTHWEST, getNeighbour(SOUTHEAST));
    setNeighbour(SOUTHEAST, eastNeighbour);
  }
}

                
public class Piece {
  public static final int NUMBEROFCELLS = 5;
  public static final int NUMBEROFPERMUTATIONS = 12;

  private PieceCell[] pieceCells = new PieceCell[NUMBEROFCELLS];
  private int currentPermutation = 0;

  private void rotatePiece() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      pieceCells[i].rotate();
    }
  }

  private void flipPiece() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      pieceCells[i].flip();
    }
  }

  public Piece nextPermutation() {
    if (currentPermutation == NUMBEROFPERMUTATIONS)
      currentPermutation = 0;

    switch (currentPermutation%6) {
      case 0:
        // Flip after every 6 rotations
        flipPiece();
        break;

      default:
        rotatePiece();
        break;
    }

    currentPermutation++;

    return this;
  }

  public void resetProcessed() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      pieceCells[i].setProcessed(false);
    }
  }

  //Getters and setters have been omitted
}

                
public class BoardCell extends Cell {
  private Piece piece = null;

  public Piece getPiece() {
    return piece;
  }

  public void setPiece(Piece piece) {
    this.piece = piece;
  }
}

                
public class Board {
  public static final int NUMBEROFCELLS = 50;
  public static final int NUMBEROFCELLSINROW = 5;

  private BoardCell[] boardCells = new BoardCell[NUMBEROFCELLS];

  public Board() {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      boardCells[i] = new BoardCell();
    }

    for (int i = 0; i < NUMBEROFCELLS; i++) {
      initializeBoardCell(boardCells[i], i);
    }
  }

  /**
   * Initialize the neighbours of the given boardCell at the given
   * index on the board
   */
  private void initializeBoardCell(BoardCell boardCell, int index) {
    int row = index/NUMBEROFCELLSINROW;

    // Check if cell is in last or first column
    boolean isFirst = (index%NUMBEROFCELLSINROW == 0);
    boolean isLast = ((index+1)%NUMBEROFCELLSINROW == 0);

    if (row%2 == 0) { // Even rows
      if (row != 0) {
        // Northern neighbours
        if (!isFirst) {
          boardCell.setNeighbour(Cell.NORTHWEST, boardCells[index-6]);
        }
        boardCell.setNeighbour(Cell.NORTHEAST, boardCells[index-5]);
      }
      if (row != ((NUMBEROFCELLS/NUMBEROFCELLSINROW)-1)) {
        // Southern neighbours
        if (!isFirst) {
          boardCell.setNeighbour(Cell.SOUTHWEST, boardCells[index+4]);
        }
        boardCell.setNeighbour(Cell.SOUTHEAST, boardCells[index+5]);
      }
    }
    else { // Uneven rows
      // Northern neighbours
      if (!isLast) {
        boardCell.setNeighbour(Cell.NORTHEAST, boardCells[index-4]);
      }
      boardCell.setNeighbour(Cell.NORTHWEST, boardCells[index-5]);
      // Southern neighbours
      if (row != ((NUMBEROFCELLS/NUMBEROFCELLSINROW)-1)) {
        if (!isLast) {
          boardCell.setNeighbour(Cell.SOUTHEAST, boardCells[index+6]);
        }
        boardCell.setNeighbour(Cell.SOUTHWEST, boardCells[index+5]);
      }
    }

    // Set the east and west neighbours
    if (!isFirst) {
      boardCell.setNeighbour(Cell.WEST, boardCells[index-1]);
    }
    if (!isLast) {
      boardCell.setNeighbour(Cell.EAST, boardCells[index+1]);
    }
  }

  public void findOccupiedBoardCells(
    ArrayList occupiedCells, PieceCell pieceCell, BoardCell boardCell) {
    if (pieceCell != null & boardCell != null & !pieceCell.isProcessed()) {
      occupiedCells.add(boardCell);
      
      /* Neighbouring cells can form loops, which would lead to an
         infinite recursion. Avoid this by marking the processed 
         cells. */
      
      pieceCell.setProcessed(true);

      // Repeat for each neighbour of the piece cell
      for (int i = 0; i < Cell.NUMBEROFSIDES; i++) {
        findOccupiedBoardCells(occupiedCells,
                               (PieceCell)pieceCell.getNeighbour(i),
                               (BoardCell)boardCell.getNeighbour(i));
      }
    }
  }

  public boolean placePiece(Piece piece, int boardCellIdx) {
    // We will manipulate the piece using its first cell
    return placePiece(piece, 0, boardCellIdx);
  }

  public boolean 
    placePiece(Piece piece, int pieceCellIdx, int boardCellIdx) {
    // We're going to process the piece
    piece.resetProcessed();

    // Get all the boardCells that this piece would occupy
    ArrayList occupiedBoardCells = new ArrayList();
    findOccupiedBoardCells(occupiedBoardCells,
                           piece.getPieceCell(pieceCellIdx),
                           boardCells[boardCellIdx]);

    if (occupiedBoardCells.size() != Piece.NUMBEROFCELLS) {
      // Some cells of the piece don't fall on the board
      return false;
    }

    for (int i = 0; i < occupiedBoardCells.size(); i++) {
      if (((BoardCell)occupiedBoardCells.get(i)).getPiece() != null)
        // The board cell is already occupied by another piece
        return false;
    }

    // Occupy the board cells with the piece
    for (int i = 0; i < occupiedBoardCells.size(); i++) {
      ((BoardCell)occupiedBoardCells.get(i)).setPiece(piece);
    }

    return true; // The piece fits on the board
  }

  public void removePiece(Piece piece) {
    for (int i = 0; i < NUMBEROFCELLS; i++) {
      // Piece objects are unique, so use reference equality
      if (boardCells[i].getPiece() == piece) {
        boardCells[i].setPiece(null);
      }
    }
  }
}

                
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;
  }
}

                
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;
    }
  }
}

                
public void solve() {
  if (!pieceList.isEmpty()) {
    // We'll try to find a piece that fits on this board cell
    int emptyBoardCellIdx = board.getFirstEmptyBoardCellIndex();

    // Try all available pieces
    for (int h = 0; h < pieceList.size(); h++) {
      Piece currentPiece = (Piece)pieceList.remove(h);

      for (int i = 0; i < Piece.NUMBEROFPERMUTATIONS; i++) {
        Piece permutation = currentPiece.nextPermutation();
        
        /* Instead of always using the first cell to manipulate
           the piece, we now try to fit any cell of the piece on 
           the first empty board cell */
        
        for (int j = 0; j < Piece.NUMBEROFCELLS; j++) {
          if (board.placePiece(permutation, j, emptyBoardCellIdx)) {
            if (!prune()) solve();
            board.removePiece(permutation);
          }
        }
      }

      
      /* Put the piece back into the list at the position where
         we took it to maintain the order of the list */
      
      pieceList.add(h, currentPiece);
    }
  }
  else {
    puzzleSolved();
  }
}

java -verbose:gc meteor.algorithm.Solver

                
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[i]=
        ((Piece)prevPermutation.clone()).nextPermutation_orig();
      prevPermutation=permutations[i];
    }

    // Calculate occupied board cells for every permutation
    for (int i = 0; i < NUMBEROFPERMUTATIONS; i++) {
      permutations[i].generateOccupiedBoardCells(board);
    }
  }

  private void generateOccupiedBoardCells(Board board) {
    for (int i = 0; i < Piece.NUMBEROFCELLS; i++) {
      for (int j = 0; j < Board.NUMBEROFCELLS; j++) {
        occupiedBoardCells[i][j]=new ArrayList();
        resetProcessed(); // We're going to process the piece
        board.findOccupiedBoardCells(occupiedBoardCells[i][j],
                                     pieceCells[i],
                                     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];
  }
}

                
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);
    ...
  }
}