Programming Java 2 Micro Edition for Symbian OS 2004 (779882), страница 68
Текст из файла (страница 68)
Again this points to the inefficiency of thealgorithm, given that there are typically a few hundred live cells in eachgeneration. Character arrays and Strings are next on the list: these aregood targets for obfuscators. The hash tables do not take up as muchmemory as might be expected.7.14.3.3 Debugging FlagsWhat will the compiler do with this code?boolean debug = false;if(debug){debugStream.println("Debug information");// other statementsdebugStream.println("Status: " + myClass);}The compiler will not compile this obviously dead code.
You shouldnot be afraid of putting in debug statements in this manner as, providedthe debug flag is false, the code will not add to the size of your classfiles. You do have to be careful of one thing: if the debug flag is in aseparate file, ensure that you recompile both files when you change thestate of the debug flag.LIFETIME CASE STUDY377Figure 7.12 Heap Analysis of LifeTime.7.14.3.4 What We Should Look Forward ToThe tools for wireless development are still fairly immature. Despite theprospect of more mobile phones running Java than the total number ofdesktop computers, Wireless IDEs (such as those from IBM, Sun, Borland,Metrowerks and others) are heavyweight J2SE environments modified forwireless development.We also need real-time tools that work with any emulator and ontarget devices.
To assist this, it is likely that Java VMs on Symbian OS willbe at least debug-enabled in the near future, with support for on-targetprofiling and heap analysis to follow.Better profiling is needed, for instance to see how much time a methodspends servicing each of the methods that call it and how much time isspent on each line of code.Heap analysis that gives a more detailed snapshot of the heap isrequired. For instance, the J2SE profiling tools provide a complete dumpof the heap so that it is possible to trace and examine the contents of eachheap variable.7.14.4 Implementing the GenerationMap ClassThe most successful container in LifeTime used a sorted binary tree.Under the Wireless Toolkit emulator (running on a 500 MHz Windows2000 laptop), LifeTime took about 33 s to calculate and render the first378WRITING OPTIMIZED CODE150 generations of the r Pentomino.
As we saw, most of this time wasspent in the algorithm.On a Sony Ericsson P800 and a Nokia 6600 the MIDlet ran dramaticallyfaster, taking around 6 s. Again, most of this was spent in the Game of Lifealgorithm. We know this because we can disable the rendering (usingthe LifeTime setup screen); doing so took the execution time down fromabout 6 s to 4 s, so only about 2 s of the 6 s is spent in rendering.Here is a summary of some results, all running under the Wireless Toolkit.GenerationMapimplementation2D arrayTime200 sComparativememoryrequirementsCommentbig!Need to inspect every cell; limitedplaying area; not scalableFast creation and enumeration, butsearching is slowFast creation and enumeration, butsearching is slowQuite fast creation and searching;enumeration is slow but there isroom for improvementEasy access to the source code gavemore opportunity for optimization. Inparticular, we dramatically cut thenumber of cells created by the GenerationMap.getNeighbourCount()method.Searching, enumeration and creation isquite fast but memory-hungry:Linked list>500 s3Vector>500 s2Binary tree34 s4Hash table42 s7• a HashTable is sparsely populated• we store a value and a key, whenwe only need the key.Hashtable.containsKey(obj)first checks the obj hash code andthen checks for equality.
In our case,we only need to do one or the other,not both (it would be interesting todownload the Hashtable sourcecode and reimplement it to meet ourrequirements).LIFETIME CASE STUDY379The linked list and vector implementations performed similarly, andvery badly. This is because the searches are linear, with the result thatover 90 % of the execution time is spent in the GenerationMap.isAlive() implementation. On the other hand, the binary tree is sortedand the hash table uses hashing for faster lookup. Running on actualphones, the hash table version took 7.5 s on a Nokia 6600 and thebinary tree version took 7 s on a Nokia 6600 and 6.5 s on a SonyEricsson P900.It is worth looking at the BinaryTreeGM class, but we need tostart with the Cell class, which is very straightforward.
positioncombines the x and y coordinates into a single 32-bit integer. nextand previous point to the two branches at each node of the tree(LinkedListGM just uses the next pointer and HashtableGM usesneither):package com.symbiandevnet.lifetime;public class Cell {int position;Cell next;Cell previous;There are two constructors: one takes the packed integer position, theother combines separate x and y coordinates.Cell(int position) {this.position = position;}Cell(int x, int y) {position = (x & 0x0000FFFF) + (y << 16);}Getter methods for the x and y coordinates:public final int getX() {return (short) position;}public final int getY() {return position >> 16;}equals() and hashCode() are needed to allow correct searchingwithin a hashtable. In general, equals() should check that obj is notnull, returning false if it is.
However, we can skip this check becausewe know this will never be the case.380WRITING OPTIMIZED CODEpublic final boolean equals(Object obj) {if ((((Cell)obj).position) == position) return true;else return false;}public final int hashCode() {return position;}}The BinaryTreeGM class implements the GenerationMap interface. root is the Cell at the start of our binary tree and size tracks thenumber of cells held in the tree. clear() clears the tree by simply settingsize to zero and the root to null. getCount() just has to return size:package com.symbiandevnet.lifetime;import java.util.*;import java.io.*;class BinaryTreeGM implements GenerationMap {private Cell root;private int size;public final void clear() {root = null;size = 0;}public final int getCount(){return size;}create(Cell) inserts a Cell in the correct location in the tree.
Itreturns silently if the tree already contains a Cell in the same position.The algorithm can be found in Section 6.2.2 of The Art of ComputerProgramming, Volume 3 by Knuth:public final void create(Cell aCell) {Cell cell = new Cell(aCell.position); // Clone cellint position = cell.position;if (root == null) {root = cell;size++;return;}Cell node = root;while (true) {if (node.position < position) {if (node.previous == null) {node.previous = cell;size++;LIFETIME CASE STUDY381return;}else {node = node.previous;continue;}}else if (node.position > position) {if (node.next == null) {node.next = cell;size++;return;}else {node = node.next;continue;}}else return;}}isAlive(Cell) returns true if the tree contains a cell with the sameposition.
Because the tree is sorted it is a fast and simple method:public final boolean isAlive(Cell cell) {int position = cell.position;Cell node = root;while (node != null) {if(node.position < position)node = node.previous;else if(node.position > position)node = node.next;else return true;}return false;}getNeighbourCount(cell) returns the number of live cells adjacent to cell.
It checks whether each of the eight neighboring positionscontains a live cell or is empty:public final int getNeighbourCount(Cell cell) {int x = cell.getX();int y = cell.getY();return getAlive(x-1, y-1)+ getAlive(x, y-1)+ getAlive(x+1, y-1)+ getAlive(x-1, y)+ getAlive(x+1, y)+ getAlive(x-1, y+1)+ getAlive(x, y+1)+ getAlive(x+1, y+1);}382WRITING OPTIMIZED CODEgetAlive(int x, int y) is called from getNeighbourCount().It is similar to isAlive(), but is a private method that returns 0 or 1. Itis used to count the number of neighboring cells:private int getAlive(int x, int y) {int position = (x & 0x0000FFFF) + (y << 16);Cell node = root;while (node != null) {if(node.position < position)node = node.previous;else if(node.position > position)node = node.next;else return 1;}return 0;}The remaining methods implement an Enumeration.
copyTreeToVector() copies the contents of the binary tree to the Vector listV;getEnumeration() then returns the Enumeration for listV:private Vector listV;public final Enumeration getEnumeration() {copyTreeToVector();return listV.elements();}private void copyTreeToVector() {listV = new Vector(size);addToListV(root); // recursive call}copyTreeToVector() initializes listV to the correct size (tosave resizing during copying, which is expensive) and then callsaddToListV(Cell). This is a recursive method which wanders downthe tree, adding the Cell at each node to the Vector ListV.private void addToListV(Cell node) {if(node == null) return;listV.addElement(node);addToListV(node.previous);addToListV(node.next);}}7.14.5Recursion: A Second LookIn Section 7.12.2, we looked at the cost of recursion, both in terms ofmemory and performance.
We showed how we could avoid recursionwhen a method called itself once, but said that even if a methodLIFETIME CASE STUDY383called itself twice (for instance to enumerate a binary tree) we couldavoid recursion.In the LifeTime BinaryTreeGM class, copyTreeToVector() useda recursive call to traverse the tree. As promised, here is how we can doit non-recursively:private Vector listV;private Stack stack = new Stack();private void copyTreeToVector() {listV = new Vector(size);if(size == 0) return;int count = size;Cell node = root;while(true) {stack.push(node);node = node.previous;while(node == null) {node = (Cell)stack.pop();listV.addElement(node);count--;node = node.next;if(count == 0) break;}if (count == 0) break;}}To explain what is going on, it is easier to think in terms of left andright, rather than next and previous, to describe the branches of thebinary tree.We start at the root and go as far down as we can taking left (previous)branches.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
