Archive

Archive for May, 2010

What’s GMail doing?

May 24, 2010 1 comment

See the screenshot below and do you know if my gmail session is secure or not?

Advertisements
Categories: Uncategorized

Google Calendar Bug on Mac OS X

This was really surprising that Google missed this. Apple always surprises me when it doesn’t provide basic computer features and when it does do so then it is hailed as ‘magic’ or some other kind of break through. Meanwhile, other operating systems have been providing that feature for decades. Some examples are:

– Spaces on OS X, well having multiple screens has been provided by solaris and linux for years and years
– Multithreading on iphone. This is such an old concept and is a highly studied and solved problem. It was introduced first with the earliest preemptive kernels. Why is it so new on iphone? Maybe someone in the marketing department knows.

Anyway, I digressed. The bug is that Google Calendar relied on local OS to see what time it is. Normally this would be fine. But when travelling across timelines it caused a problem. I went from the East coast to the West and while I do have internet here, OS X did not bother to update the clock by subtracting 3 hours (though Windows XP would have, I have not used Win7 but I imagine it does too). Now my google calendar events started alerting me to events based on my computer clock which is 3 hours ahead of what it should be. And for a few seconds I entered panic mode that missed my events for last 3 hours till I noticed the issue :).

Google Calendar should go to a time server for current time when an internet connection is available. They don’t even have to maintain one, just use the one provided by US Navy which is the official one anyway. If there is no internet connection available then it is a harder problem. But at least solve the the former of the two use cases.

I have updated my OS X clock manually and things are in order once again. Thanks for reading.
* I know you can set the clock to update automatically but why isn’t it checked to true by default. Who wants an inaccurate clock. Plus, the bug is not in OS X it is in Google Calendar.

Bubble sort in Java

Bubblesort is one of the simplest sorting methods. It also very inefficient. Though in the best case when the elements are already sorted, then its run time is O(n). Otherwise it is O(n^2).

package com.labeltop.sort;

public class BubbleSort {
	public void sort(Comparable[] comparables) {

		int size = comparables.length;

		// loop till swaps are being done
		while (true) {
			// reset it
			boolean foundSwap = false;

			// loop over values
			int i = 0;
			while (i < size) {
				// don't care about last value
				if (i == size - 1)
					break;

				// check for swap i.e. c1 > c2
				if (comparables[i].compareTo(comparables[i + 1]) > 0) {
					Comparable temp = comparables[i];
					comparables[i] = comparables[i + 1];
					comparables[i + 1] = temp;
					foundSwap = true;
				}

				// keep on...
				i++;
			}

			// check if there were any swaps
			if (!foundSwap)
				break;
		}
	}
}
Categories: Java, Java Misc, Java Sorting

Quicksort in Java

QuickSort is one of best sorting algorithms. While the worst case scenario is O(n^2), the average case is O(nlgn). Additionally, it is possible to implement in highly optimized way as well do several of its parts in parallel.

package com.labeltop.sort;

public class QuickSort {

	public void sort(Comparable[] c) {
		quicksort(c, 0, c.length-1);
	}

	private void quicksort(Comparable[] comparables, int start, int end) {

		// get a pivot point
		int pivot = start + ((int) (Math.random() * (end - start)));
		Comparable cPivot = comparables[pivot];

		// where to start on either side of pivot
		int left = start;
		int right = end;

		// loop till they overlap
		while (left <= right) {
			// find first on left that is bigger than pivot
			while (cPivot.compareTo(comparables[left]) > 0) {
				// more towards pivot
				left++;
			}

			// find first on right that is less than pivot
			while (cPivot.compareTo(comparables[right]) < 0) {
				// more towards pivot
				right--;
			}

			// exchange them
			if (left <= right) {
				Comparable temp = comparables[left];
				comparables[left] = comparables[right];
				comparables[right] = temp;
				//go to next ones towards the pivot
				left++;
				right--;
			}			
		}
		
		//recurse on left
		if (right > start) {
			quicksort(comparables, start, right);
		}
		//recurse on right
		if (left < end) {
			quicksort(comparables, left, end);
		}
	}

}
Categories: Java, Java Misc, Java Sorting

Merge Sort in Java

Here it is:

package com.labeltop.sort;

public class MergeSort {

	public void sort(Comparable[] c) {
		mergesort(c, 0, c.length-1);
	}

	private void mergesort(Comparable[] c, int start, int end) {
		//check if sort is needed
		if (c.length <= 1)
			return;
		
		//find middle
		int middle = start + ((end-start)/2);
		
		//create left list
		Comparable[] cLeft = new Comparable[middle-start+1];
		
		//create right list
		Comparable[] cRight = new Comparable[end-middle];
		
		//sort first half
		mergesort(cLeft, 0, cLeft.length-1);
		//sort second half
		mergesort(cRight, 0, cRight.length-1);
		
		//check the last on left iwth first on right to see if we need to merge
		if (cLeft[cLeft.length-1].compareTo(cRight[0]) <= 0) {
			System.arraycopy(cLeft, 0, c, 0, cLeft.length);
			System.arraycopy(cRight, 0, c, cLeft.length, cRight.length);
		}
		else {
			//now merge left and right
			mergeIt(c, cLeft, cRight);	
		}
	}
	
	private void mergeIt(Comparable[] merged, Comparable[] cLeft, Comparable[] cRight) {		
		//loop till both are done
		int iMerged = 0;
		int iLeft = 0;
		int iRight = 0;
		while (iLeft < cLeft.length && iRight < cRight.length)
		{
			if (cLeft[iLeft].compareTo(cRight[iRight]) <= 0)
			{
				//copy from left
				merged[iMerged] = cLeft[iLeft];
				iLeft++;				
			}
			else
			{
				//copy from right
				merged[iMerged] = cRight[iRight];
				iRight++;
			}
			
			iMerged++;
		}
		
		//check for remaining elements on left
		if (iLeft <= cLeft.length-1) {
			System.arraycopy(cLeft, iLeft, merged, iMerged, cLeft.length-iLeft);
			iMerged = iMerged + (cLeft.length-1-iLeft);
		}
		//check for remaining elements on right
		if (iRight <= cRight.length-1) {
			System.arraycopy(cRight, iRight, merged, iMerged, cRight.length-iRight);
			iMerged = iMerged + (cRight.length-1-iRight);
		}		
	}
}
Categories: Java, Java Misc, Java Sorting

Java Native Access, JNA, thoughts

In order to get system information, you almost certainly have to go to some platform specific functions. I’m referring to something that in non-trivial, the Java API is great but it really does fall short when you need to interact with OS kernel functions. The old (well older) way to do so would be to use JNI (Java Native Interface). With JNI, you would generate a client stub in Java and essentially link it to the implementation which is in C (or any other language you have bindings for). The keyword ‘native’ in Java tells the compiler of your intentions and that leads to good relative performance because the compiler is able to do static linking.

There are books written on the subject and there is not much to it but JNI is certainly a way to get Java to interact with win32 api. During developing LabelTop (see Links), I wanted to interact on a low level with the OS. I wanted to get processor usage information and memory usage information. My experience that I mention here is almost equally applicable to Mac OS X where I called Obj-C functions from the Cocoa API. I decided to use JNA instead of JNI.

JNA is a project which is (was) in incubation at java.net. It always dynamic linking with native resources. The benefit of that is that you have a lot less compile time stuff to do as a programmer. Though, the cost is that you do lose some performance. While I haven’t done a detailed empirical study of the amount of performance loss, my experience is that the loss is hardly noticeable, after having used JNA quite a bit.

A big benefit is that I’m able to represent the underlying ‘struct’ as a simple Java class, an interface with signatures of functions that I want to call in Java. I can then load a dll file that I didn’t write and call its functions. JNA will take an input the function I’m calling and its input parameters, convert the function call to a C function call and convert the class to struct, then I will execute the function using the dll, it will take the results and convert that to Java types and return them to me.

Equivalently, with JNI, I would to write my interface, declare methods as native, write my C program which would then call functions in the dll. Get the results back from dll and return them myself. So JNA, does a lot of the heavy lifting for me.

The kernel32.dll is huge! I don’t need to call every function. So in my interface I declare the functions that I will want to use and just call those. If I need another function then I can declare that in my interface too. Thus, integration can be done iteratively which saves a lot of time. JNA uses a mapping of primitive types from Java to C which is very clear and straightforward. Have fun!

Categories: Java, Java Misc Tags: , , , , ,