Programming Java 2 Micro Edition for Symbian OS 2004 (779882), страница 64

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 64)

Wehave defined tab and nl as char rather than as StringBuffer:appending one StringBuffer to another is no better than appending aString to a StringBuffer, and significantly slower than appendinga char.public final static float IMP_TO_MET = 1/2.2;final char tab = '\t';final char nl = '\n';int numberEmployees = company.getNumberEmployees();Employee[] employees = new Employee[numberEmployees];StringBuffer nameList = new StringBuffer(128);StringBuffer companyName= new StringBuffer(company.getCompanyName()).append(tab);for(int id = 0; id < numberEmployees; id++){nameList.append(companyName);Employee employee = company.getEmployee(id);nameList.append(employee.getName()).append(tab);nameList.append(employee.getWeight()*IMP_TO_MET).append(nl);// Do something with nameListFinally, we reuse the StringBuffer, though note that this does notphysically resize its internal store:nameList.setLength(0);employees[id] = employee;}COPYING AN ARRAY3517.11 Copying an ArraySystem.arraycopy() is a standard Java method which copies thecontents of one array into a second array, and is generally implemented as a native method.

However, rather than JNI, it uses the nativeinterface of the VM, which provides direct access to the array contentsand type data.The following is part of a test used to compare arraycopy() with ourjavaCopy() method for copying an array, taken from the MicrobenchMIDlet:...private static Object[] sourceArray = new Object[1000];private static Object[] destinationArray = new Object[1000];private static int size;private static void vmCopy(){System.arraycopy(sourceArray, 0, destinationArray, 0, size);}private static void javaCopy(){for(int i = size; --i >= 0; ){destinationArray[i] = sourceArray[i];}}...The number of elements copied is determined by size, which is set bythe user interface.

javaCopy() and vmCopy() were called 3 200 000times and the total durations compared:012310Nokia 7650:arraycopy()javaCopy()19.53 s6.25 s20.47 s11.09 s20.94 s15.78 s21.41 s20.47 s22.66 s52.81 sNokia 6600:arraycopy()javaCopy()3.30 s1.38 s3.83 s2.97 s4.28 s4.56 s4.78 s6.09 s8.13 s17.17 ssize(number ofelementscopied)For small arrays of two or three elements, copying using Java code isfaster. For arrays larger than this, using arraycopy() is much faster.

So,352WRITING OPTIMIZED CODEin general, use arraycopy() unless you have a very large number ofsmall arrays to copy.The results under the Emulator were qualitatively different. Nativecopying was faster except for a zero-length array, emphasizing onceagain that an optimization must be evaluated on target hardware.It is not clear how meaningful the results are for zero-length arrays,though dividing the total time of 3.3 s for native copying by the numberof calls (3 200 000) suggests a native overhead of about 1 µs per call forthe CLDC HI VM on the Nokia 6600.7.12Thoughts on LoopingIn Section 7.10 we saw that we should not dereference variables inside aloop. In this section we shall look at further issues to do with looping.7.12.1 Loop Control StatementsIn the previous section we used the following Java code to copy thecontents of an array:private static void javaCopy(){for(int i = size; --i >= 0; ){destinationArray[i] = sourceArray[i];}}The loop control statement was originally written like this:for(int i = 0; i < size; i++)However, the loop termination comparison (>= 0) used in the finalcode is built into the Assembler branch opcode and so is quicker.

Thedifference is significant: the final javaCopy() ran about 16 % faster thanthe original.7.12.2 RecursionRecursion can be used to create compact code and, if used carefully,code that is also clear. For instance, searching through the contents ofa directory structure lends itself to recursive code. In general, however,recursive code is slow and memory-intensive.

Each pass has the overheadof a method call and the resulting stack space.THOUGHTS ON LOOPING353Here is a recursive example that prints out the values of a binary tree(each Node in the tree stores a value and references to the two Nodesthat branch from it):class Node{Object value;Node smaller;Node bigger;}class BinaryTree{static void print(Node node){if(node == null) return;System.out.println(node.value);print(node.smaller);print(node.bigger);}...}The body of the print() method calls itself twice unless the Node isnull, in which case the call returns.The Microbench MIDlet includes tests to compare recursive and nonrecursive implementations.

The non-recursive test simply decrements anumber (value) until it reaches zero, and this is repeated repeattimes:static long doNonRecursive(int repeat, int value){long timeStart = System.currentTimeMillis();for(int loop = repeat; --loop >= 0; ) {int count = value;while (true){if(--count == 0) break;}}return System.currentTimeMillis() - timeStart;}In the recursive version, decrementCount() calls itself until countis zero. doRecursive() does the timing and sets up the first call todecrementCount():private static void decrementCount(int n){if (--count == 0) return;else decrementCount(n);}static long doRecursive(int repeat, int value){long timeStart = System.currentTimeMillis();for(int loop = repeat; --loop >= 0; ){int count = value;354WRITING OPTIMIZED CODEdecrementCount(count);}return System.currentTimeMillis() - timeStart;}We can see from the results below that the recursive option witha depth of 500, repeated 10 000 times, took 7.2 s on the Nokia 6600.The non-recursive solution took just 0.6 s.

The message is clear: avoidrecursion!9210i9210iNokiaNokiaSEMCPersonal MIDP 1.076506600P900JavaKVMMIDP 1.0MIDP 2.0CLDCKVMCLDC HI 1.0 HI 1.0RecursiveNon-recursive34.0 s4.6 s19.6 s3.4 s15.2 s3.1 s7.2 s0.6 s6.7 s0.4 s7.12.3 Stack Size and Limits on Recursion DepthThe stack size available with PersonalJava on the Nokia 9210 and KVMon the Nokia 9210 or 7650 is sufficient to allow a recursion depth inexcess of 5000 (at least 9000 with PersonalJava on the 9210).For PersonalJava, the Java stack used to push Java method call framesis set by default to about 400 KB. If you need a greater Java stackdepth, the -ossx parameter in the command line can be used. Thefollowing command runs the Performance Tests application allowing ahuge recursion depth:\epoc32\release\wins\udeb\pjava_g -oss32m -cd j:\examples\PerformanceTests-cp PerformanceTests.jarcom.symbian.devnet.crystal.performance.PerformanceTestsThe maximum depth that can be achieved with CLDC HI 1.0 isaround 500.

This reflects the VM’s inability to support dynamic stackextension: instead a fixed, albeit generous, stack size was chosen for useby all threads. The unfortunate side effect is an increase in the dynamicfootprint per thread (this has been addressed in CLDC HI 1.1).Sun’s KVM allowed thread stacks to be stretched in linked chunksup to the capacity of the dynamic heap.

CLDC HI 1.1 can also stretchstacks, but requires a stack to be contiguous. It therefore has to perform acopying realloc on each extension, which is a slower process.THOUGHTS ON LOOPING3557.12.4 More ExamplesCalculating FactorialsWe can calculate n! either recursively or non-recursively. The recursivecode looks like this:private static long factorialR(int value){if(value < 2) return 1L;else return value*factorialR(value - 1);}Here is the non-recursive version:private static long factorial(int value){long valueFactorial = value;while (--value > 1){valueFactorial *= value;}return valueFactorial;}These methods are called from doFactorialRecursive() anddoFactorialNonrecursive() respectively. doFactorialRecursive() looks like this:static long doFactorialRecursive(int repeat, int value){long valueFactorial = 0;long timeStart = System.currentTimeMillis();for(int loop = repeat; --loop >= 0; ){valueFactorial = factorialR(value);}return System.currentTimeMillis() - timeStart;}doFactorialNonrecursive() is identical to doFactorialRecursive() except that it calls factorial(), not factorialR().Calculating 20! recursively one million times on a Nokia 6600 took6.1 s.

Calculating 20! non-recursively took 5.7 s.However, there is a better way of calculating factorial numbers. Themaximum 64-bit long value is 9 223 372 036 854 775 807. The largestfactorial that can be calculated in a 64-bit long is only 20!, which is2 432 902 008 180 000 000; 21! overflows and returns a negative value.The obvious solution is to use a lookup table of 20 values.First we need an array to store the factorials:private static long[] factorials = new long[20];356WRITING OPTIMIZED CODEThen a lookup method:private static long factorialLookup(int value){return factorials[value-1];}These are called by the doFactorialLookup() wrapper. This firstpopulates the array by calling the earlier factorial() method (thiscould be done much more efficiently, but the startup time is insignificant),then repeatedly calls factorialLookup():static long doFactorialLookup(int repeat, int value){for (int index = 0; index < 20; index ++){factorials[index] = factorial(index + 1);}long valueFactorial = 0;long timeStart = System.currentTimeMillis();for(int loop = repeat; --loop >= 0; ){valueFactorial = factorialLookup(value);}return = System.currentTimeMillis() - timeStart;}Calculating 20! one million times using this lookup table took just 0.7 son a Nokia 6600.

Here is a complete set of results:RecursiveNon-recursiveLookup9210iMIDP 1.0KVMNokia7650 MIDP1.0 KVMNokia 6600MIDP 2.0CLDC HI1.0SEMCP900CLDC HI1.039.4 s38.0 s3.8 s26.6 s25.5 s2.5 s6.1 s5.7 s0.7 s4.5 s4.4 s0.5 sSearching a Binary TreeIf a recursive method calls itself just once, then replacing the recursivecalls with a loop is trivial: the examples above do this. The problem is alittle harder when a method calls itself more than once; for instance, tofind a node with a particular value in a binary tree or searching through adirectory structure. You do not need recursion for searching if the binarytree is sorted:Node root;boolean contains(Node nodeToFind){Node node = root;THOUGHTS ON LOOPING357while (true) {if (node == null) return false;if(node.compare(nodeToFind) == -1)node = node.smaller;else if(node.compare(nodeToFind) == 1)node = node.bigger;else return true;}}Avoiding recursion in the print() example is harder.

Характеристики

Список файлов книги