Developer Forums | About Us | Site Map
Search  
HOME > TUTORIALS > SERVER SIDE CODING > JAVA TUTORIALS > OPTIMIZE YOUR JAVA APPLICATIONS PERFORMANCE


Sponsors





Useful Lists

Web Host
site hosted by netplex

Online Manuals

Optimize your Java applications performance
By Erwin Vervaet & Maarten De Cock - 2003-12-15 Page:  1 2 3 4 5 6 7 8 9 10 11

Improving The Algorithm

Take a look back at Listing 1 and think about how we might be able optimize our initial puzzle-solving algorithm. A good way to optimize an algorithm is to visualize it. Visualisation allows us to get a better understanding of the process being implemented and its possible downsides. The next sections discuss two inefficiencies we can discern. We leave the actual visualisation code for our puzzle-solving program to the interested reader.

Island detection pruning


The algorithm in Listing 1 fits pieces (or more precisely, the piece cells of a piece) onto every position of the board. Figure 4 shows a possible board situation at the beginning of the process. The current permutation of the blue piece has been placed on the first available board position and the current permutation of the yellow piece has moved to its second possible board position. Our algorithm then continues with the third piece, and so on. However, if we look carefully at Figure 4, it's clear that there will be no possible solutions for the puzzle with the blue and yellow pieces in these positions. The reason is those two pieces have formed an island of three neighbouring empty cells. Because all the puzzle pieces consist of five cells, there is no way to fill this island. All the effort that our algorithm exerts trying to fit the remaining eight pieces on the board is useless. What we need to do is cut off our algorithm if we detect an island on the board that cannot be filled.

Figure 4. An island on the board
An island on the board

Text books call this process of interrupting a recursive search algorithm pruning. Adding a pruning function to our Solver class is easy. Before every recursive call to the solve() method, we check for islands on the board. If we find an island consisting of a number of empty cells that is not a multiple of five, we do not make the recursive call. Instead, the algorithm continues at the current level of recursion. Listings 7 and 8 show the necessary code adjustments:

Listing 7. A puzzle-solving algorithm with pruning


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;
  }
}
Listing 8. The getIslandSize() method

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


View Optimize your Java applications performance Discussion

Page:  1 2 3 4 5 6 7 8 9 10 11 Next Page: The Fill-Up Algorithm

First published by IBM developerWorks


Copyright 2004-2017 GrindingGears.com. All rights reserved.
Article copyright and all rights retained by the author.