Sorting Arrays

[Element6]

Ok well .NET definately makes sorting Arrays easy. I have a quick question though if anyone knows.

I am using the Array type .Sort function to sort my array.

By default it places the result Array into Ascending order Least to Greatest

How do I change that to Descending order Greatest to Least?
and
How do I change it to Closest to logic? or does that not exist?

Assume there is an Array of Numbers 0,13,21,-2,4,5,1.34 and I want them to sort closest to 0 or some other arbitray value; the Output should look similar to:

0,1.34,-2,4,5,13,21

Is there anyway of doing this? or do I have to write the routine?

 

[Element6]

How am I passing N into the AbsSort?

That was my first impression mathematically.

But, I don't know if AbsSort will be handled correctly.

Is the order of operation value1 (Required) value2 (Required) n (optional = 0) or
reversed?

 

[Element6]

Just checked; if I pass N as optional

Error 2 Overload resolution failed because no accessible 'Sort' can be called with these arguments:

'Public Shared Sub Sort(Of T)(array() As T, comparison As System.Comparison(Of T))': Method 'Public Shared Function AbsSort(x As Decimal, y As Decimal, n As Decimal) As Integer' does not have a signature compatible with delegate 'Delegate Function Comparison(Of T)(x As T, y As T) As Integer'.
'Public Shared Sub Sort(Of T)(array() As T, comparison As System.Comparison(Of T))': Data type(s) of the type parameter(s) cannot be inferred from these arguments. Specifying the data type(s) explicitly might correct this error.
'Public Shared Sub Sort(Of Decimal)(array() As Decimal, comparer As System.Collections.Generic.IComparer(Of Decimal))': 'AddressOf' expression cannot be converted to 'System.Collections.Generic.IComparer(Of Decimal)' because 'System.Collections.Generic.IComparer(Of Decimal)' is not a delegate type.
'Public Shared Sub Sort(Of TKey, TValue)(keys() As TKey, items() As TValue)': Type parameter 'TValue' cannot be inferred.
'Public Shared Sub Sort(array As System.Array, comparer As System.Collections.IComparer)': 'AddressOf' expression cannot be converted to 'System.Collections.IComparer' because 'System.Collections.IComparer' is not a delegate type.
'Public Shared Sub Sort(keys As System.Array, items As System.Array)': 'AddressOf' expression cannot be converted to 'System.Array' because 'System.Array' is not a delegate type. ..\GlobalFunctions.vb 605 9 AISystem

 

[JohnH]

How am I passing N into the AbsSort?

If you have to use the explicit function you have to declare 'n' as a private field so that the function can access it (inline any local variable will do). The Comparison(Of T) delegate signature can't be changed.

You don't know how to declare a private field? This is also sometimes referred to as "module level scope", see Scope in Visual Basic

Private n As Single

 

[Element6]

Thats a hack and you know it.

Of course I know how to, but the implementation I am using is being called as a form of a delegate and the function cannot use global passes in this case.

This works, but not for my implementation

 Public SortN As Decimal = 0.0

    Public Function AbsSortOfN(ByVal x As Decimal, ByVal y As Decimal) As Decimal
        Return Math.Abs(x - SortN).CompareTo(Math.Abs(y - SortN))
    End Function

    Public Function SortClosestToN(ByVal AnArrayOfNumbers As Decimal(), ByVal n As Decimal) As Decimal()
        SortN = n
        Array.Sort(AnArrayOfNumbers, AddressOf AbsSortOfN)

        Return AnArrayOfNumbers
    End Function

Let me give you some background on what I am doing; it should make it easier to understand why this won't work.

I am calling code from outside the application and multi-threaded. So private declares wouldn't work because I might end up with instances overlapped; I need to pass it as a function parameter per instance per compare.

So the logical step is passing the value as N; not referring it, to guarentee that each invoke contains the correct data. Otherwise I can end up with multiple calls changing the private global value and messing up the threading returns. If that makes sense.

The only other solution is keep the value of N in a per thread global param; and that becomes memory intensive after a while as a matter of principal. It's just simpler to pass N.

Do I have to create state data to represent a value of N per thread or is there a way of blending the data so the value of N can be extrapulated?

 

[Element6]

This is the other solution and it is very ugly in my opinion

    Public SortN As Decimal = 0.0

    Public Function AbsSortOfN(ByVal x As Decimal, ByVal y As Decimal) As Decimal
        Dim localN As Decimal = SortN
        Dim Value As Decimal

        Value = Math.Abs(x - localN).CompareTo(Math.Abs(y - localN))
        SortN = localN

        Return Value
    End Function

    Public Function SortClosestToN(ByVal AnArrayOfNumbers As Decimal(), ByVal n As Decimal) As Decimal()
        SortN = n
        Array.Sort(AnArrayOfNumbers, AddressOf AbsSortOfN)
        Return AnArrayOfNumbers
    End Function

Yikes!

 

[JohnH]

Thats a hack and you know it.

It is not. If you need to sort asynchronous with an instance dependency you can't use the IComparable(Of T) delegate, you have to define the IComparer(Of T) class, this is what jmcilhinney recommended you read about in his blog.

Public Class AbsSorter
    Implements IComparer(Of Single)

    Private _n As Single
    Public Property N() As Single
        Get
            Return _n
        End Get
        Set(ByVal value As Single)
            _n = value
        End Set
    End Property

    Public Function Compare(ByVal x As Single, ByVal y As Single) As Integer Implements System.Collections.Generic.IComparer(Of Single).Compare
        Return Math.Abs(x - N).CompareTo(Math.Abs(y - N))
    End Function
End Class

Now you can create multiple instances and use them async:

Array.Sort(num, New AbsSorter With {.N = 4})

"New AbsSorter With" - not sure if you support this coding style now, if not I'm sure you know how to work this. Using a constructor is also an option.

 

[Element6]

EDITED MY POST

Didn't see your post until after I clicked save. I think both these solutions work.
Need to do a Benchmark to see which is better in threading.

Public Function AbsSort(ByVal x As Decimal, ByVal y As Decimal) As Decimal
        Return Math.Abs(x).CompareTo(Math.Abs(y))
    End Function

    Public Function SortClosestToN(ByVal AnArrayOfNumbers As Decimal(), ByVal n As Decimal) As Decimal()
        For x = 0 To AnArrayOfNumbers.Length - 1
            AnArrayOfNumbers(x) = AnArrayOfNumbers(x) - n
        Next

        Array.Sort(AnArrayOfNumbers, AddressOf AbsSort)

        For x = 0 To AnArrayOfNumbers.Length - 1
            AnArrayOfNumbers(x) = AnArrayOfNumbers(x) + n
        Next
        Return AnArrayOfNumbers
    End Function

    Sub Main()
        Dim num() As Decimal = {3, 12, -0.123, 5.1, 1002, 50, 23, 33, 41, 8836, 2, 23}

        num = SortClosestToN(num, 50)
        For x = 0 To num.Length - 1
            Debug.WriteLine(num(x))
        Next
    End Sub

Immediate view is my solution is shareable and flat.

 

[Element6]

His solution would be :

Public Class AbsSorter
    Implements IComparer(Of Single)

    Private _n As Single
    Public Property N() As Single
        Get
            Return _n
        End Get
        Set(ByVal value As Single)
            _n = value
        End Set
    End Property

    Public Function Compare(ByVal x As Single, ByVal y As Single) As Integer Implements System.Collections.Generic.IComparer(Of Single).Compare
        Return Math.Abs(x - N).CompareTo(Math.Abs(y - N))
    End Function
End Class

Module Module1
    Public Function SortClosestToN(ByVal AnArrayOfNumbers As Decimal(), ByVal n As Decimal) As Decimal()
        Dim CompareAbsSort as New AbsSorter
        CompareAbsSort.N = 50

        Array.Sort(AnArrayOfNumbers, AddressOf CompareAbsSort.Compare)

        Return AnArrayOfNumbers
    End Function

    Sub Main()
        Dim num() As Decimal = {3, 12, -0.123, 5.1, 1002, 50, 23, 33, 41, 8836, 2, 23}

        num = SortClosestToN(num, 50)
        For x = 0 To num.Length - 1
            Debug.WriteLine(num(x))
        Next
    End Sub
End Module

Either way they both work; his is designed from Microsoft's point of view on coding; mine is designed from Cross Platform functionality.

I think mine will win in the Benchmark test though, because it's only taking an extra nanosecond or 2 do the array additions/subtractions which is geometric of course. So in larger arrays his solution might be more adequate I don't know until I do the benchmark; my first impression is because I have fewer accessors and accessor layers mine is faster; we'll find out I'll do a timed test on a 100,000,000 element array and see what happens.

 

[MattP]

Assuming he can use LINQ another option would be using OrderBy.

num = num.OrderBy(Function(x) Math.Abs(x - 4)).ToArray

As an extension method I can see this being useful.

Public Module Extensions

    <System.Runtime.CompilerServices.Extension()>
    Public Function OffsetSort(ByVal sourceArray As Single(), ByVal offset As Single) As Single()
        sourceArray = sourceArray.OrderBy(Function(x) Math.Abs(x - offset)).ToArray()
        Return sourceArray
    End Function

End Module

num.OffsetSort(4)

The performance will be slower than calling just Array.Sort since LINQ will create intermediate arrays and invoke a delegate to obtain a sorting key.

I'm still able to sort a million elements in under a second w/ my POS work computer so I'd consider it a moot point unless you're dealing with extremely large sets of data.

 

[Element6]

Well I can admit my error when I am wrong! Wow .NET just impressed me.

Array length of 9999999 with random numbers generated

Test 1 is Johns Method

Test 1 = 3/3/2010 4:07:51 PM
3/3/2010 4:08:28 PM
Elapsed Time = 37 seconds to sort
CPU 50-52% at about 150mb's of memory

Test 0 is My Method
test 0 = 3/3/2010 4:08:44 PM
3/3/2010 4:09:39 PM
Elapsed Time = 55 seconds to sort
CPU 49-51% at about 150mb's of memory

That means the for loops take about 9 seconds each to run.

And yes, I'll be sorting billions of records; so it does make a difference. I am working on systems which predict trends at very small levels both positive and negative; so bad data = useful even though we can generate a lot more garbage data then useful data. If my ratio is 2% useful and 98% garbage; I still have to sort through the garbage to determine if a trend is established.

So ClosestToN is a normal thought process to me; Especially when doing fractals on numbers and trying to find relationships that are arbitrary.

 

[Element6]

BTW take into account that the Benchmark is run as :

1 Thread to 99999999 elements in Test 0
or
1 Thread to 1 Instance Created and 99999999 Elements in Test 1

When I do a more likely scenario of :

99999999 Threads to 10 element in Test 0
or
99999999 Threads to 1 Instance and 10 Elements in Test 1

The difference in performance will be dramatic. However, on the low end his solution works better because he is passing the value of N as a Property in an initiated class reference so the mathematics is much faster.

I think my solution will be more applicable still but I have to test to see if Constructing and DeConstructing Object instances on the fly will be a significant delay; personally; I think it will because most of my threads are created Ad-Hoc.

This becomes a design issue : and I should move the conversation to another thread.

"When to use Shared vs Instance References"

 

[JohnH]

Elapsed Time = 37 seconds to sort

My three years old comp do this in 17 seconds.

The performance will be slower than calling just Array.Sort since LINQ will create intermediate arrays and invoke a delegate to obtain a sorting key.

Not necessarily, the comparable result I get is 9 seconds ('Array length of 9999999'), which is way faster.

99999999 Threads

Bad idea. Look to ThreadPool.

 

[Element6]

Well I got some issues then if yours ran in 17 seconds; you just debunked my test.

Whats your 3 year old machine? Because I ran my test on a duel core Intel(laptop not desktop). Plugged in. With 40MB Hardware reserved 1612 MB inuse 36MB Modified (OS) 1067MB on Standby and 328MB Free. 3.07Gigs total

with Windows 7; it would not suprise me if windows 7 was doing poor memory management here.

Please, help me identify the hardware problem here because a 50% margin is way significant are you overclocked or standard?

Why did yours run in 17secs? because that is 1/2 the time of my test.

It might be the busing on the laptop... Hmm. 50% seems to be a high error threshold though for speed.

 

[Element6]

Ah the inevitable Managed Resources discussion! No. I do not use Microsoft Managed Resources. It's a really good ideaa, that went really bad and my program is expected to be ported to a none windows environment can't use it, I need to stay relatively independant of Microsoft specifics and keep a logic flow that is easily portable to Java or ASM at a later date; using .NET for prototype development not production.

 

[JohnH]

Well I got some issues then if yours ran in 17 seconds; you just debunked my test.

Whats your 3 year old machine? Because I ran my test on a duel core Intel(laptop not desktop). Plugged in. With 40MB Hardware reserved 1612 MB inuse 36MB Modified (OS) 1067MB on Standby and 328MB Free. 3.07Gigs total

with Windows 7; it would not suprise me if windows 7 was doing poor memory management here.

Please, help me identify the hardware problem here because a 50% margin is way significant are you overclocked or standard?

Why did yours run in 17secs? because that is 1/2 the time of my test.

It might be the busing on the laptop... Hmm. 50% seems to be a high error threshold though for speed.

It's a dual core, core @ 3.16 GHz. Laptops are usually slow, unless you have the latest Intel i-type cpus.

Ah the inevitable Managed Resources discussion! No. I do not use Microsoft Managed Resources. It's a really good ideaa, that went really bad and my program is expected to be ported to a none windows environment can't use it, I need to stay relatively independant of Microsoft specifics and keep a logic flow that is easily portable to Java or ASM at a later date; using .NET for prototype development not production.

Hate to break it to you, but .Net is a managed development platform, it performs really well too. That you (or someone) have to port some solution to a different platform is not our problem. It's like saying the cars of the future don't need to be designed with engines because the future drivers don't have a driving license now anyway. When you develop with .Net you have to make viable solutions with the tools at hand. Disregarding, the key factors of how Threadpool is working with threads is the prime example if you should need to manage threads yourself.