• 0

[Java + C#] Using generics types


Question

Hi, I am currently learning all the common sort algorithms, and the course is in Java. Now my difficulty is not about any sort algorithm in particular (well, as of yet), but how to write a generic implementation instead of hard-coding integers or doubles.

Consider this code :

public static <AnyType extends Comparable<? super AnyType>>
void insertionSort( AnyType[] a ) {
	...
}

I have two questions about this code :

- Is it normal that in order to instantiate an array of AnyType, I have to write AnyType[] a = (AnyType[])new Comparable ? This generates a warning.

- What does the bit between <> mean at the top of the method ? AnyType has to implement Comparable<T> where T derives from AnyType ? :wacko:

Now in C#, you can create generic arrays alright, but consider the following code:

		public bool IsSorted&lt;T&gt;(T[] Elements) {
			...
		}

Obviously, in order to test if Elements is sorted, I need to call CompareTo(T) on each Element[x]. That supposes T implements IComparable. Or is it IComparable<T> ? Or something as complicated as the Java syntax ? In any case, how do I tell the compiler that T implements the right interface ?

Thanks.

Edited by Dr_Asik
Link to comment
Share on other sites

9 answers to this question

Recommended Posts

  • 0
public static &lt;AnyType extends Comparable&lt;? super AnyType&gt;
void insertionSort( AnyType[] a ) {
	...
}

- What does the bit between <> mean at the top of the method ? AnyType has to implement Comparable<T> where T derives from AnyType ? :wacko:

<? extends AnyType>: Denotes a family of subtypes of type AnyType

With that in mind, (just to make sure) w/o the generics(<>) its

public static void insertionSort()

? (which doesnt make since to have a generic type specifier and a void)

or is it

public static classname&lt;AnyType extends Comparable&lt;? super AnyType&gt;&gt;{
void insertionSort(anytype[] a){}
}

if the latter is the case, it means that AnyType inherits from Comparable, subtypes of AnyType

mind boggling!

As for the rest, my knowledge stops there :(

Link to comment
Share on other sites

  • 0
Now in C#, you can create generic arrays alright, but consider the following code:

		public bool IsSorted&lt;T&gt;(T[] Elements) {
			...
		}

Obviously, in order to test if Elements is sorted, I need to call CompareTo(T) on each Element[x]. That supposes T implements IComparable. Or is it IComparable<T> ? Or something as complicated as the Java syntax ? In any case, how do I tell the compiler that T implements the right interface ?

Thanks.

You can add generic constraints.

		public bool IsSorted&lt;T&gt;(T[] elements) where T: IComparable
		{
			// do whatever
		}

Edit: Here's the msdn article. http://msdn.microsoft.com/en-us/library/d5x73970.aspx

Link to comment
Share on other sites

  • 0

Edited Java code : was missing a '>' in the method declaration. The "generic" part of the method declaration is really

<AnyType extends Comparable<? super AnyType>>

Ok so say it means "AnyType is a subclass of Comparable<T>, where T is a subclass of AnyType". What does that mean, really ? Why must AnyType extend Comparable<? super AnyType> and not simply Comparable<AnyType> ?

You can add generic constraints.
Thanks, that's exactly what I was looking for.
Link to comment
Share on other sites

  • 0

So I implemented MergeSort today and did some quick benchmarks. MergeSort supposedly runs in O(N logN) and is supposedly quite a fast algorithm, although not among the very fastest.

The class has a private array of integers, this is the data to be sorted. There are public methods for working with the class, namely IsSorted, which returns whether the array is in ascending order; GenerateValues which populates the array with random values; Display which shows a few values of the array; BuiltInSort which calls Array.Sort, for reference purposes; and MergeSort which calls my implementation of the algorithm.

So I compared the performance of my algorithm with .NET's Array.Sort, and HOLY CRAP, Array.Sort is FAST. Looking at Task Manager, it doesn't even seem to run on multiple cores, and yet it's much, much faster than my fancy little MergeSort.

For 100000000 (that's 100 millions) integers, my MergeSort runs in 1min50 seconds. Array.Sort runs in 23 seconds. :rofl:

On a side note, running MergeSort for 100 millions integers makes the process use 788MB of memory.

So apparently I still have much to learn. :laugh:

EDIT: That was in Debug mode. In Release mode, the results are far more encouraging : MergeSorts takes around 44 seconds, only twice as much as Array.Sort, instead of 1min50seconds. Array.Sort stays fixed at 23 seconds. Also, ILDASM reveals that in Release mode, the merge() routine, which should take most of the time, is cut down from 142 CIL lines to 112.

	class SortAlgorithms {

		int[] Elements;

		public bool IsSorted() {
			for (int i = 0; i &lt; Elements.Length - 1; i++) {
				if ( Elements[i] &gt; Elements[i + 1] ) {
					return false;
				}
			}
			return true;
		}

		/// &lt;summary&gt;
		/// Generates numValues random numbers between 0 and numValues.
		/// &lt;/summary&gt;
		/// &lt;param name="numValues"&gt;&lt;/param&gt;
		public void GenerateValues(int numValues) {
			Elements = new int[numValues];
			Random rand = new Random();
			for (int i = 0; i &lt; Elements.Length; i++) {
				Elements[i] = rand.Next(numValues);
			}
		}

		public void Display() {
			if (Elements.Length &lt;= 10) {
				foreach (int i in Elements) {
					Console.Write(i.ToString() + ", ");
				}
			}
			else {
				for (int i = 0; i &lt; 5; i++) {
					Console.Write(Elements[i].ToString() + ", ");
				}
				Console.Write("... ");
				for (int i = Elements.Length - 5; i &lt; Elements.Length; i++) {
					Console.Write(Elements[i].ToString() + ", ");
				}
			}
			Console.WriteLine();
		}

		public void BuiltInSort() {
			Array.Sort(Elements);
		}

		public void MergeSort() {
			int[] tmpArray = new int[Elements.Length];
			mergeSort(tmpArray, 0, Elements.Length - 1);
		}

		void mergeSort(int[] tmpArray, int low, int high) {
			if (high &gt; low) {
				int median = (high + low) / 2;
				mergeSort(tmpArray, low, median);
				mergeSort(tmpArray, median + 1, high);
				merge(tmpArray, low, median, median + 1, high);
			}
		}

		void merge(int[] tmpArray, int low1, int high1, int low2, int high2) {
			int index = low1;
			int lowBound = low1;
			while (low1 &lt;= high1 &amp;&amp; low2 &lt;= high2) {
				if (Elements[low1] &lt; Elements[low2]) 
					tmpArray[index++] = Elements[low1++];				
				else 
					tmpArray[index++] = Elements[low2++];
			}
			while (low1 &lt;= high1) 
				tmpArray[index++] = Elements[low1++];

			while (low2 &lt;= high2) 
				tmpArray[index++] = Elements[low2++];

			for (int i = lowBound; i &lt; index; i++ )
				Elements[i] = tmpArray[i];
		}
	}

Edited by Dr_Asik
Link to comment
Share on other sites

  • 0
- Is it normal that in order to instantiate an array of AnyType, I have to write AnyType[] a = (AnyType[])new Comparable ? This generates a warning.

- What does the bit between <> mean at the top of the method ? AnyType has to implement Comparable<T> where T derives from AnyType ?

AnyType[] a = new AnyType[]; you don't need the Comparable bit again because that's already part of the definition of AnyType.

The bit in <> means that AnyType is a class that extends (implements) the Comparable<? super AnyType> interface, where <? super AnyType> means any class that is a superclass of AnyType (or AnyType itself).

If it was <AnyType extends Comparable<AnyType>> then that would be more restrictive on the way the Comparable interface was implemented for AnyType.

eg if AnyType was Integer then in the restricted case it would have to implement compareTo(Integer i), whereas the original version would allow compareTo(Number n).

So: the <> reads "AnyType that implements the Comparable interface for that type, or any superclass of that type", which is as wide a spec as you can get while still having it work.

Maybe not the clearest prose I've ever written, but I just got up. Hope it helps anyway.

Edited by JamesCherrill
Link to comment
Share on other sites

  • 0

clarification of previous message after a cup of coffee:

So: the <> reads "AnyType is any type that implements the Comparable interface for (AnyType or any superclass of AnyType)".

Link to comment
Share on other sites

  • 0
AnyType[] a = new AnyType[]; you don't need the Comparable bit again because that's already part of the definition of AnyType.

The bit in <> means that AnyType is a class that extends (implements) the Comparable<? super AnyType> interface, where <? super AnyType> means any class that is a superclass of AnyType (or AnyType itself).

If it was <AnyType extends Comparable<AnyType>> then that would be more restrictive on the way the Comparable interface was implemented for AnyType.

eg if AnyType was Integer then in the restricted case it would have to implement compareTo(Integer i), whereas the original version would allow compareTo(Number n).

So: the <> reads "AnyType that implements the Comparable interface for that type, or any superclass of that type", which is as wide a spec as you can get while still having it work.

Maybe not the clearest prose I've ever written, but I just got up. Hope it helps anyway.

Thanks for the explanation, that makes it very clear.

But in Java, really I can't write AnyType[] a = new AnyType[] (where AnyType is a generic type), that's a compiler error. Hence the workaround creating an array of Comparable (or Object) and casting it to AnyType[]. I just wonder if that's really how I should get around the difficulty, since it generates a warning.

Link to comment
Share on other sites

  • 0

AnyType is a generic - a symbol that represents a class that will be specified when the method is called. AnyType doesn't even exist at runtime ("erasure"). You can't create an AnyType, you have to create an instance of a real class that satisfies the definition of AnyType (ie implements Comparable etc). So you will write

Integer[] data = new Integer[9]; data[0]= ....

insertionSort(data); // AnyType is replaced by Integer for this call

or

Double[] data = new Double[9]; data[0]= ....

insertionSort(data); // AnyType is replaced by Double for this call

Link to comment
Share on other sites

  • 0

ps. Sorry about "AnyType[] a = new AnyType[]" I was being too brief. I should really have said

AnyType[] a = new AnyType; // where "AnyType" is replaced by the name of a class that implements (or inherits an implementation of) Comparable

Link to comment
Share on other sites

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.