Getting runtime from ~ 15 seconds to 4 seconds

This is a bit of information on how I got a ~ 15 second program to work in less than 4 seconds. Although the insights are obvious, using the profiler defenitely gave more info than raw intuition.

The Problem: The anagram problem as discussed by Bentley. For a quick example 'rickets', 'sticker' and 'tickers' are anagrams. Using a permutations approach is defenitely unacceptable because of the time complexity. This brings us to the signature approach where we identify anagrams based on signatures. My program uses quick sort to build a signature. The partition code for the quick sort is that discussed by Bentley as I know from my college days the bugs and the confusion involved in coding the partition using the regular method.

The input to the code is a 58111 long list of english words.

Case 1: Using a swap function, quick sort and signature function. Output was dumped to the screen using 'System.out'.  The total run time of the program was around 15 seconds. The quick sort took close to under 5 seconds. The screen dump took around 7-8 seconds !.

* I replaced the screen dump code with a write to a text file. So, I wrote all the anagrams (the hash map contents) to a text file. But, this was done using Buffered Writer. This saved 8 seconds leaving the whole code to around 6-7seconds.

This is a general approach I always used.

Case 2: I had a look at the time taken by the functions and noted the following. Notice the quicksort, partition, swap methods in the hot spots window. The invocation frquency for the simple swap is a place to tune. I replaced the 3 line swap code at 3 invocation points in the quick sort. So swap as a seperate function is gone.

Before the substitution was made partition code took colse to 2 seconds. After eliminating the method invocation, it takes 414 ms ! Quick sort now takes 2.3 seconds. But, overall time saved is 2 seconds! Now the runtime is 3.6 seconds compared to 5.5 before.

Case 3: Something I have taken for granted is Horners method in hashing a string. This is explained by Robert Lafore in his book. Hasing the strings took 120 ms.

Case 4: Since we can save time on method invocations, I believed that a non-recursive version of quick sort can have a serious effect on the running time. This was not the case. The self time of the quick sort function was more by 1 second.  The program itself was a bit slow by 3-4 seconds. There are more instructions in the quicksort function so, the increase is 'explainable'. The stack which was used to bypass the recurssion was being called, for pop and push a huge number of times. The point is that, the non recursive version of quick sort did not yield anything better. On the contrary it is performing a bit worse (7-9 seconds for the whole program ! looking for the missing 3-4 seconds ).