Java Data Structures - Contents
A D V E R T I S E M E N T
A day after I wrote the above section, I realized I
made a blunder. Not only does that suck, but it's slow and has tons of useless code in it
as well! For example, I realized that I didn't really need to care about the node pool
that much. Even if I didn't setup the node pool, things would still work, since node pool
gets re-initialized every time though the loop (look at the code in the above article). I
later realized that I don't even need a pointer to the next free node on the node pool!
Since we are allocating a node per number, and we are doing that in a loop, we could just
use the loop counter to point to our free node!
After I got the code down to a mere 14 lines, I
still wasn't satisfied with the inner loop that searched for the last node on the queue.
So, created another array, just to hold the backs of queues. That eliminated lots of
useless operations, and increased speed quite a bit, especially for large arrays.
After all that, I've moved the static arrays out of
the function (just for the fun of it), since I didn't want to allocate exactly the same
arrays every single time.
With each and every improvement, I was getting code
which sucked less and less. Later, I just reset the 32 bit size to 16 bit integer size (to
make it twice as fast, since the test program only throws stuff as large as 1024). I
didn't go as far as unrolling the loops, but for a performance needy job, that could
provide a few extra cycles.
Anyway, I won't bore you any longer, and just give
you the new and improved code (which should have been the first one you've saw, but... I
was lazy, and didn't really feel like putting in lots of effort into radix sort).
import java.lang.*;
import java.io.*;
public class pRadixSort{
private static int q[],ql[];
static{
q = new int[256];
ql = new int[256];
for(int i=0;i<q.length;q[i++] = -1);
}
public static void radixSort(int[] arr){
int i,j,k,l,np[][] = new int[arr.length][2];
for(k=0;k<2;k++){
for(i=0;i<arr.length;np[i][0]=arr[i],np[i++][1]=-1)
if(q[j=((255<<(k<<3))&arr[i])>>(k<<3)]==-1)
ql[j] = q[j] = i;
else
ql[j] = np[ql[j]][1] = i;
for(l=q[i=j=0];i<q.length;q[i++]=-1)
for(l=q[i];l!=-1;l=np[l][1])
arr[j++] = np[l][0];
}
}
public static void main(String[] args){
int i;
int[] arr = new int[15];
System.out.print("original: ");
for(i=0;i<arr.length;i++){
arr[i] = (int)(Math.random() * 1024);
System.out.print(arr[i] + " ");
}
radixSort(arr);
System.out.print("\nsorted: ");
for(i=0;i<arr.length;i++)
System.out.print(arr[i] + " ");
System.out.println("\nDone ;-)");
}
}
This code is so much better than the previous one,
that I'd consider it as fast as quicksort (in some cases). Counting the looping, we can
get an approximate idea of how fast is it... First, we have a loop which repeats 2 times
(for 16 bit numbers), inside of it, we have 2 loops, both of which repeat on the order of
N. So, on average, I'd say this code should be about 2*2*N, which is 4N... (not bad...
<if I did it correctly>), imagine, if you have 1000 elements in the array, the sort
will only go through about 4000 loops (for bubble sort, it would have to loop for
1,000,000 times!). True, these loops are a bit complicated compared to the simple bubble
sort loop, but the magnitude is still huge.
Anyway, I should really get some sleep right about
now (didn't get much sleep in the past few days due to this little 'thought' which kept me
awake). Never settle for code which you truly believe sucks (go do something about it!).
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
|
Add to Favorites
Make Home Page
