[ Home Page ] [ Eiffel Archive ] [ Eiffel Applications ]
Written by Peter Horan.
cricket.zip (26,089 bytes) - source code
The purpose of this offering for "The Class Struggle, 1998" is to illustrate that OO is about software structure.
I wrote the first version of this software when I wished to predict the performance of the Australian Cricket Team playing in England in 1996. At the time of exploring the problem, I sought an appropriate OO solution, its appropriateness judged by the elegance, in my eyes at least, of the design. This search for elegance has always been a driving force underlying my designs and I must say that I prefer OO and Eiffel because they assist me in thinking and building. My search ended with a solution in terms of the "Chain of Responsibility" design pattern.
After implementation, I considered what the code would be like if implemented according to different rules - one a single routine implementing nested loops and the other a recursive solution. I thought that examining solutions prepared with such restrictions would illustrate the value of the OO method when properly used and that an OO design would stand up well against procedural design in terms of performance.
I predicted that the procedural version would be faster and the recursive version slower. When I prepared the alternative solutions, I was not disappointed with the performance of the OO version, but I was surprised by the recursive version which was as good as the OO version, and very surprised by the single routine procedural version which was very slow. This proved to be a case of multiple references to the same element in an array. When replaced by a single access to assign the reference to a local variable, the performace was improved to almost the that of the other two versions. Further hand optimisation is possible.
Cricket is a game played by two teams of eleven players. In the simplest case, two innings are played. One team bats in the first innings and the other team bowls. The batsmen score runs when they hit the ball. The bowling team attempts to dismiss a batsman terminating his innings. Dismissal can occur in one of ten ways and the batsman is "out". When ten batsmen are out, the batting team is "all out" and the innings is closed. The teams swap roles and a second innings is played. At the end of the two innings, the team with the highest score of runs is declared the winner.
The concern, then, is to predict the batting performance of the cricket team from a series of past performances of the individual players. This can be done by determining the set of all possible scores generated by taking each score in turn from each player and computing the total. The result may be reported as a histogram showing the distribution of scores. So, that is what this software does. Words are deceptive, however, and when I stated the problem in this way, I thought the solution was a "loop within a loop" because I was had written "each score . . . from each player . . .". Actually, a loop is needed for each player; the clue is in the phrase "in turn".
As an aside, the problem may be viewed quite differently. Just as we map the total scores into a histogram, so we could map each player's scores into histograms and "convolve" them together. There is nothing to be gained here as, overall, the same number of additions and multiplications are required. It leads to a different structure, however, which may offer opportunities for OO solutions in suitable circumstances.
Several implementations have been prepared, which I have called the OO solution, the recursive solution and the procedural solution.
The computation time is significant. The number of additions to be made is (ignoring initialisation and incrementing entries in the histogram):
players.upper Product players.item(i).count i = players.lower 11
For example with 11 players with 10 scores each, this is 10 additions.
As the computation time depends exponentially on the number of players, this parameter was controlled by the data supplied to the program. That is, the time could be measured for any number of players by adjusting the data file.
In the experimental results, I have compared processing time for 8 and 9 players running on a Pentium 133 processor. I have not performed the measurements for 10 or 11 players as this would take longer than I am prepared to spend.
The OO solution is a "Chain of Responsibility" which is built by the root class. Each link in the chain is an object which models a batsman, holding his scores in an array. The total score is built by adding the incoming total to a score in the array and then invoking the same feature in the next batsman using the augmented total. This happens for each score in turn. (See oo.gif)
The last link in the chain is not a batsman but an object which holds a histogram in a array indexed by the total score. When this object is invoked with a total, the appropriate bin in the histogram is incremented.
To enable the batsman and histogram objects to be invoked without distinction (i.e. polymorphically) by a client, their classes inherit from a common class (the ELEMENT class). The gain is that once the chain of responsibility is built, testing is not required to distinguish between two courses of action, namely, the batsman action of adding a series of scores to the total and the histogram action of updating the histogram.
The testing has not actually disappeared, however. It has been moved into initialisation which builds the chain of player objects terminated by the histogram.
This solution is similar to the chain of responsibility, except that each batsman must determine whether to invoke the histogram by testing. I expected this to reduce the performance of the recursive solution.
Reference to the HISTOGRAM object needs to be provided. This is done by using the singleton pattern to build the histogram after the last player object and make it available for the root class to display.
This solution is a series of eleven nested loops. It was difficult to write as the loops looked very similar. Many local variables were used. 191 lines of code were used in the 11 loops rather than 8 lines in the OO version and 14 lines in the recursive version.
All solutions were tested in finalised form, discarding assertions.
8 players 9 players OO 0:02:36 0:21:18 Recursive 0:02:11 0:21:07 Procedural 0:02:50 0:28:29
(Time in hours, minutes, seconds)
There is room for further handcrafting of the code of the procedural version to improve its performance further.
OO 6 Recursive 14 Procedural 191
My opinion based on how well I could visualise the code I was writing (relative scale)
OO 1 Recursive 2 Procedural 2
Because the root class builds the computational structure in the OO version before it is used, it can be laid out as an object model. The computation does not modify this model.
On the other hand, in the recursive solution, all PLAYER objects have access to the HISTOGRAM object and access it dynamically. As designer, one is faced with a dynamic or behavioural question to be answered imposed by the recursive nature of the system.
OO 1 Recursive 1.5 Procedural 20
The weakness of the procedural version is that I was using different code to do the same thing. A simple typographical slip could go unnoticed because of the similar code nearby. Many local variables were used, all doing the same thing for different loops. I had to hand optimise the loops.
There is no significant difference in the performance of each method. That is, there is nothing lost by using the OO solution.
There is a difference in the effort of developing and testing the various solutions. The procedural method is significantly behind. The OO method is a little easier to my way of thinking than recursive. The difference is related to being able to express the solution structurally rather than dyamically. I think that replacing dynamic behaviour (procedure) with structure is a significant gain from OO methods.
This is the file readme.txt. It needs to be read in conjunction with the class diagrams for the OO and recursive solutions. These are in oo.gif and recursive.gif in this directory.
There are three subdirectories, CricketO, CricketR and CricketP which hold the Eiffel sources for the three solutions. Ace files are provided in each directory. I produced three executables for the testing by finalising using ISE Eiffel, V4.1. My tests were run on a Pentium 133MHz with 48Mb memory.
The file data.txt holds the data file used for testing the performance of each system. Players may be selected for computing the team performance by placing a '*' in column 1. This allows different sets of players to be selected. The file is hardwired in distribution.e to read this file. You will need to set the string to point to the file. Each "player" in this file has 10 scores.
The file cricket_data.txt holds real data in which the number of scores vary.-------------------------------
[ Home Page ] [ Eiffel Archive ] [ Eiffel Applications ]