Arrays in .Net can store an element at index 0. You decalre then with the upper bound, not the size. Hence:

Dim ints(0) As Integer

would have room for 1 element.

This just means your array is 1 element too big and has nothing at index 0, which isn't a big deal as you don't start at 0.

--------------------

Your error catching is a mix of old-style vb and vb.Net. You should use one or the other.

I'll just get rid of it for now.

--------------------

You don't need to pass the Array ByRef as it is a reference type. Changes to the array are propogated back to calling code.

--------------------

If you switch Option Strict Onand Option Explicit On, then you get a huge list of problems. (Always have these two options set).

There are two problems it detected, repeated many times:

--------------------

First accessing the Array like this:

key_father = key_array(i_father0)

Is not allowed, you must use:

key_father = key_array.GetValue(i_father0)

(this is what I was muttering about in an earlier post)

--------------------

Secondly, the type of the elements in the array is Object, and Object doesn't have a CompareTo method. At runtime then, it ishaving to find the CompareTo method using late binding.

You can't implement the generic Comparable(Of T), as you aren't using generics anywhere else. I'll show that later. So I changed it to the normal Comparable.

Now, to get around this late binding, you need to have a Type that DOES have a CompareTo method, and at the moment that type is either matrix_increment or IComparable. You can't go casting the objects to max_increment, as this method is supposed to be able to cope with different types. So you need to cast to IComparable.

--------------------

To follow:

A Demo of the problem.

A fixed, butugly,version.

Then a neater fixed version, using a separate comparer class and Object() instead of Array.

Then a generic version.

It should get faster with each one.

Here's the class we will sort

Here's an IComparer for it

And here's a form that does HeapSort

I'll mess with it later and see how other ways compare. It cries out forgeneric types.

Changing over to Array instead of Object() and accessing values with GetValue SetValue adds a couple of seconds (I get about 6s):

Using Generics is consistantly faster than using Object(), I've not tested extensively.

We need an IComparer(Of T) instead of a straight comparer.

And change all the methods to use generics.

Arrays in .Net can store an element at index 0. You decalre then with the upper bound, not the size. Hence:

Dim ints(0) As Integer

would have room for 1 element.

This just means your array is 1 element too big and has nothing at index 0, which isn't a big deal as you don't start at 0.

--------------------

Your error catching is a mix of old-style vb and vb.Net. You should use one or the other.

I'll just get rid of it for now.

--------------------

You don't need to pass the Array ByRef as it is a reference type. Changes to the array are propogated back to calling code.

--------------------

If you switch Option Strict Onand Option Explicit On, then you get a huge list of problems. (Always have these two options set).

There are two problems it detected, repeated many times:

--------------------

First accessing the Array like this:

key_father = key_array(i_father0)

Is not allowed, you must use:

key_father = key_array.GetValue(i_father0)

(this is what I was muttering about in an earlier post)

--------------------

Secondly, the type of the elements in the array is Object, and Object doesn't have a CompareTo method. At runtime then, it ishaving to find the CompareTo method using late binding.

You can't implement the generic Comparable(Of T), as you aren't using generics anywhere else. I'll show that later. So I changed it to the normal Comparable.

Now, to get around this late binding, you need to have a Type that DOES have a CompareTo method, and at the moment that type is either matrix_increment or IComparable. You can't go casting the objects to max_increment, as this method is supposed to be able to cope with different types. So you need to cast to IComparable.

--------------------

To follow:

A Demo of the problem.

A fixed, butugly,version.

Then a neater fixed version, using a separate comparer class and Object() instead of Array.

Then a generic version.

It should get faster with each one.

Here's a demo of the problem.

Generating data
Created data in: 1.1407463s
Starting to build heap
heap built in 18.1453599s
sorted in: 306.5314217s
total: 324.702742s

Here I switched on Option Strict and Option Explicit and fixed up the warnings.

This meant CompareTo couldn't be called directly on the items from the array, so they get cast to IComparable first.

And, GetValue and SetValue had to be used.

This eliminated LateBinding, and sped it up dramatically.

Generating data
Created data in: 1.1811032s
Starting to build heap
heap built in 0.3861724s
sorted in: 5.1919813s
total: 5.5784823s

Edit: Highlighted some of the changes.

Here I swapped to Object() instead of Array.

And I swapped to using a Comparer class instead of Comparable. This way we don't need to keep casting to IComparable.

I added a bit to check it actually was sorting!

Generating data
Created data in: 1.3212753s
Starting to build heap
heap built in 0.3126916s
sorted in: 4.1875777s
total: 4.5011018s

The speed increase comes from using Object() instead of Array.

And here's a complicated one with Generics, it's a bit slower than the one above.

Generating data
Created data in: 1.2289694s
Starting to build heap
heap built in 0.3783466s
sorted in: 4.7357952s
total: 5.1150947s

First we say the method is (Of T) to mean it is a generic method.

Now, we can swap back to using IComparable(Of T) as we are using generics.

If the method was just (Of T) then we still wouldn't be able to use CompareTo, as that is not a method of any Type, and T can stand for any Type. We need to make it a method (Of T but T must implement IComparable Of T). You can do that with a generic constraint. The syntax is:

Public Sub MySub(Of T As IComparable(Of T))

That hasn't got the parameters for the function yet, it is just stating that this is a generic Sub.

We can add more polymorphism to the sub, if we make keys_array of type IList(Of T). This means it can accept an array, a List(Of T), and anything other class that implements IList(Of T). So Yuo end up with a method sig like this:

Sub ao_heap_sort02(Of T As IComparable(Of T))(ByVal keys As IList(Of T), ByVal n As Int32)

So here's the Generic version.

I went through again and tested on a different (slower) computer. I removed the Stopwatch and Console.WriteLine stuff from the sorting sub as it takes time. I started the stopwatch before calling the sorting sub, and stopped it on return. I used the same random seed in each example, so they all sorted the same items. I ran the release build 20 times for each example (except the first, which would take too long), and picked the fastest.

Original problem code: 352.6s
First Fix: 6.72s
Object() and an IComparer: 5.47s
Generics, IComparable(Of T) constraint, keys As IList(Of T): 5.36s
Generics, IComparable(Of T) constraint, keys() As T: 3.87
Generics, no constraint on T, keys As IList(Of T), comparer As IComparer(Of T): 5.26
Generics, no constraint on T, keys() As T, comparer As IComparer(Of T): 3.78

So, I think it's best not to get overly fancy with generics. Using an array of T is definately faster than using an IList. I guess there's an extra cast for it to do. Asking the user of the sub to supply an IComparer(Of T) might be a tiny bit faster thanimplementing comparablein the class, but this test wasn't in the least bit thorough.

jo01s:

SUPER answers!

Thanks for

     Dim sw As New Stopwatch

So, once again I didn't have to write my own!

I also wrote my own for Copies("="c, 72) before I discovered
that this function was available!

Sometimes it's easier to write 10 lines of code than to find
something equivalent in the thousands of Web pages at MSDN!

Yes, on array subscript lower bounds, I was aware, as is
traditional in Basic, that Visual Basic .NET uses 0 instead of
1 as was long traditional and/or default in Fortran, PL/I,
etc.

But for heap sort, the algorithm makes heavy use of subscript
expressions such as

     i \ 2

which does work for i = 1, 2, ..., n but which I would have to
check for i = 0, 1, 2, ..., n - 1.

So, for simplicity and one less thing to think about, I just
kept the array indexing i = 1, 2, ..., n.  In doing this, I
waste the array component with subscript 0.

Since Visual Basic .NET is my first attempt at a Microsoft
Basic, I don't know about either "old" or "new" error handling
techniques!  I just looked a some of

     Jim Buyens, 'Web Database Development, Step by Step: .NET
     Edition', ISBN 0-7356-1637-X, Microsoft Press, Redmond,
     Washington, 2002.

found some simple things that appeared to work, and settled on
those.  So I just put each 'contiguous block of executable
code' in Try-Catch with something like

     error_code = 1001

     error_code = 1002

     ...

ahead of anything risky, and in the corresponding Catch-End
Try block put some simple code to 'percolate' the error to the
calling routine.

But in some of my sorting routines I did leave some
Console.Writeline statements in the Catch-End Try 'block', and
that was unintentional; with my little scheme, such print
statements are supposed to be only in the main routine and, in
production, write to a log file, use SNMP, or some such.

Okay, I'm starting to understand:  My class matrix_increment
does not inherit from a class that has a method CompareTo.

Since my code did run, I guessed that my code was okay.  That
my code ran at all sounds like 'late binding' did a lot.

I will start using

     Option Strict On
     Option Explicit On

nearly universally.  I am eager for all the help from the
compiler I can get.  Compiler messages about when my code is
using late binding might be helpful also!  I'm eager for the
power of late binding but only when I'm willing to pay the
price in execution time.

Gee, just now see from the VB compiler:

     error BC30574: Option Strict On disallows late binding.

So, can be told when there needs to be late binding!

How with my class definition array.sort still ran so well, I
don't know!  I did look at the C# code for array.sort and
didn't see anything very tricky with 'reflection' or using
actual memory addresses.

Maybe the big difference is that array.sort didn't try to do
the key comparisons with CompareTo and avoided this problem
with its statement

     if (comparer == null) comparer = Comparer.Default;

One of your points is to have

    Sub ao_heap_sort02(ByVal key_array() As Object, ByVal n As _
      Int32, ByVal comparer As IComparer)

that is, so that the sort routine can do its pair-wise
comparisons, just pass to the sort routine an instance of a
class that implements the interface IComparer.

Curious:  With your suggestions, I went ahead and wrote such
code.  I wrote two versions:  In one version I defined a class
that implements the interface IComparer and passed to the sort
routine the instance as an argument corresponding to a
parameter in the routine with type IComparer.  So, I was
passing an instance of a class to a parameter of type
interface.  Curious that I didn't get an error for this
'mismatch' between argument and parameter.

So, one lesson is NOT to complicate the definition of the
class, whose instances are being sorted in an array, with
comparison code.  GOOD.  Wondered about that.  One reason is
that in some applications might have a class with, say, seven
properties and for various purposes would want to sort on
different ones of the properties.  So, would want to have
several comparer classes, not just one, and certainly not just
one named CompareTo in the definition of the class of the
instances being sorted.

So, you showed me how to do that!  Good!

You have

     Public Class MatrixImcrementComparer
         Implements IComparer

         Public Function Compare(ByVal x As Object, ByVal y As Object) _
           As Integer Implements System.Collections.IComparer.Compare
             Dim matX As MatrixIncrement = DirectCast(x, MatrixIncrement)
             Dim matY As MatrixIncrement = DirectCast(y, MatrixIncrement)
             Return String.Compare(matX.key, matY.key)
         End Function

     End Class

Here maybe I understand:  This piece of code is particular to
class MatrixIncrement yet, still, its parameters are declared
Object instead of MatrixIncrement.  Maybe the reason is that
the polymorphic sort routine will pass arguments that are of
type Object so that having the parameters of type
MatrixIncrement would be a mismatch between arguments and
parameters and, possibly, an error, either in compilation or
execution.

But, inside the method, need to be particular to
MatrixIncrement.  So, do a DirectCast.  Here there is no issue
of 'how' the conversion is to be made because we are sure (we
could put in some code to check if we were not sure -- there
are examples on MSDN) that the actual arguments really are of
type MatrixIncrement.

Maybe this is what is going on.

I would guess that this polymorphic technique of doing all the
pair-wise comparisons would be horribly slow, but some of the
timings from both of us show that, somehow, the run time can
be commendably fast, maybe only a factor of 2 worse than with
no use of polymorphism.

Here is a summary of execution times on my computer for
sorting 500,000 strings of length 16 bytes where each array
component is either a string or an instance of a class where
one property of the class in such a string:

  629.4062500 seconds      own heap sort code sorting an array
                           of instances of a class where the
                           class has a messed up comparison
                           method definition

     7.5312500 seconds     own heap sort code sorting an array
                           of instances of a class where the
                           class and a comparison method are
                           defined following your suggestions

     3.8125000 seconds     array.sort sorting an array of
                           instances of a class where the
                           class has a messed up comparison
                           method definition

     2.9218750 seconds     own non-polymorphic heap sort code
                           sorting an array of strings by
                           surrogate

     2.5312500 seconds     own non-polymorphic heap sort code
                           soring an array of strings not by
                           surrogate

So your suggestions worked!  Success!  Now at least for simple
things I can write Visual Basic .NET polymorphic code as the
language designers intended and get decent performance!

You have shown me a LOT.  THANKS!

The purpose of this project was to get me to understand how to
write polymorphic code, but for sorting more could be done:

     o    When sorting by surrogate, it is possible to write
          the code to do a 'stable' sort, and that can be a
          nice tool when sorting on a sequence of keys.
          Sorting by surrogate might often be better when
          sorting large or complicated objects.

     o    Sorting exploiting multiple processor cores should
          soon be of importance.

For generics, I read the chapter in

     Francesco Bolena, 'Programming Microsoft Visual Basic
     2005:  The Language', Microsoft Press, Redmond,
     Washington, 2006.

didn't get even 10% of your understanding, and will have to
read the chapter again even to understand your use of the
syntax "Of T"!

For now, polymorphism will be enough for the real work.

Beyond sorting, the software development project plans include
a large scale use of collection classes -- 64 bit computing on
computers with 256 GB of main memory, hopefully more -- where
we will either have to make polymorphic code fast or write our
own AVL tree code, and very much would prefer just to use what
Microsoft already has in collection classes.

Back of the envelop arithmetic starting with k*n*log(n) from
the heap sort timings indicates that the collection class code
really MUST be able to exploit multiple cores, and not sure
that has been done yet or just how to do it.  Hmm ....

Many thanks!