Computer Science Canada

Sorting in Turing and Returning Arrays from Function
Author:  andytyk [ Mon Jul 19, 2004 11:40 pm ]
Post subject:  Sorting in Turing and Returning Arrays from Function
I was playing with different sorts in Turing, and list operations such as Merge Sort, Quick Sort etc. and needed to pass arrays in recursion to functions and return them as well.

I tried the obvious first and found out that Turing will not permit it. So after digging through the Reference manual and finding nothing that will help, I decided to write a class that simply consists of a flexible array and some basic array functions (add, count members, etc.) and had a flexible array of pointers. So the functions simply returned the index in which the pointer lay for the result.

This resulted in a horrendously low sorting speed. Using Quicksort and a pregenerated list of 1000 Rand.Real s. Sorting using the first term of the set as the pivot resulted in 288ms while using the average as the pivot resulted in 277ms. Is there a better way to handle this, or are there better ways to sort in Turing?
Author:  Dan [ Tue Jul 20, 2004 11:02 am ]
Post subject: 
While bubble sort may not be the fastested but it is easy and i know will work in turing for shure.

this is bubble sort in c++

code:

for (i=0; i<n-1; i++)
{
  for (j=0; j<n-1-i; j++)
  {
     if (a[j+1] < a[j])
     { 
         tmp = a[j];         
         a[j] = a[j+1];
         a[j+1] = tmp;
      }
  }
}


Where a is the array and n is the number if elments in the array. The -i part in the 2nd for is not need but incereces the speed. a smiple verson in turing whould be:

code:

for i : 1 .. numOfElements
        for ii : 2 .. numOfElements
            if myArray(ii - 1) < myArray(ii) then
                %switchs the values
                var temp : int := myArray(ii - 1)
                myArray(ii - 1) := myArray(ii)
                myArray(ii) := temp
            end if
        end for
end for
Author:  andytyk [ Tue Jul 20, 2004 12:18 pm ]
Post subject: 
Hmm... I'm just thinking about the speed, sorting 100,000 Rand.Reals I can get around 3000-4000 sorts per second using Quicksort without a combo with Insertion.

This is the code I wrote:

code:

class arrays

    export addterm, avg, quickavg, numterms, getterm

    var core : flexible array 1 .. 0 of real

    function getterm (termno : int) : real
        result core (termno)
    end getterm

    function addterm (a : real) : boolean
        new core, upper (core) + 1
        core (upper (core)) := a
        result true
    end addterm

    function avg : real
        var sum : real := 0
        for k : 1 .. upper (core)
            sum := core (k) + sum
        end for
        result sum / upper (core)
    end avg

    function quickavg (a : int) : real
        var sum : real := 0
        for k : 1 .. a
            sum := core (k) + sum
        end for
        result sum / a
    end quickavg

    function numterms : int
        result upper (core)
    end numterms

end arrays

var pseudoarray : flexible array 1 .. 0 of pointer to arrays
var dummy : boolean

function newarray : int
    new pseudoarray, upper (pseudoarray) + 1
    new pseudoarray (upper (pseudoarray))
    result upper (pseudoarray)
end newarray

var test1, test2 : int

test1 := newarray
test2 := newarray

var size := 50000
var tempreal : real

for abc : 1 .. size
    tempreal := Rand.Real
    dummy := pseudoarray (test1) -> addterm (tempreal)
    dummy := pseudoarray (test2) -> addterm (tempreal)
end for

function join (a : int, b : int) : int
    var newtarget : int := newarray
    for m : 1 .. pseudoarray (a) -> numterms
        dummy := pseudoarray (newtarget) -> addterm (pseudoarray (a) -> getterm (m))
    end for
    for n : 1 .. pseudoarray (b) -> numterms
        dummy := pseudoarray (newtarget) -> addterm (pseudoarray (b) -> getterm (n))
    end for
    free pseudoarray (a)
    free pseudoarray (b)
    result newtarget
end join

function merge (a : int, b : int) : int
    var m, n : int := 1
    var ai, bi : boolean
    var newtarget : int := newarray
    loop
        if pseudoarray (a) -> getterm (m) >= pseudoarray (b) -> getterm (n) then
            dummy := pseudoarray (newtarget) -> addterm (pseudoarray (b) -> getterm (n))
            n := n + 1
        else
            dummy := pseudoarray (newtarget) -> addterm (pseudoarray (a) -> getterm (m))
            m := m + 1
        end if
        ai := m - 1 = pseudoarray (a) -> numterms
        bi := n - 1 = pseudoarray (b) -> numterms
        exit when ai or bi
    end loop
    if not ai then
        for k : 1 .. pseudoarray (a) -> numterms - (m)
            dummy := pseudoarray (newtarget) -> addterm (pseudoarray (a) -> getterm (m + k))
        end for
    elsif not bi then
        for k : 1 .. pseudoarray (b) -> numterms - (n)
            dummy := pseudoarray (newtarget) -> addterm (pseudoarray (b) -> getterm (n + k))
        end for
    end if
    free pseudoarray (a)
    free pseudoarray (b)
    result newtarget
end merge

function quicksort (a : int) : int
    if pseudoarray (a) -> numterms <= 1 then
        result a
    else
        var ara, arb, arc : int
        var avg : real := pseudoarray (a) -> getterm (1)
        ara := newarray
        arb := newarray
        arc := newarray
        for k : 1 .. pseudoarray (a) -> numterms
            if pseudoarray (a) -> getterm (k) < avg then
                dummy := pseudoarray (ara) -> addterm (pseudoarray (a) -> getterm (k))
            elsif pseudoarray (a) -> getterm (k) = avg then
                dummy := pseudoarray (arb) -> addterm (pseudoarray (a) -> getterm (k))
            else
                dummy := pseudoarray (arc) -> addterm (pseudoarray (a) -> getterm (k))
            end if
        end for
        free pseudoarray (a)
        result join (join (quicksort (ara), arb), quicksort (arc))
    end if
end quicksort

function quicksortb (a : int) : int
    if pseudoarray (a) -> numterms <= 1 then
        result a
    else
        var ara, arb, arc : int
        var avg : real := pseudoarray (a) -> avg
        ara := newarray
        arb := newarray
        arc := newarray
        for k : 1 .. pseudoarray (a) -> numterms
            if pseudoarray (a) -> getterm (k) < avg then
                dummy := pseudoarray (ara) -> addterm (pseudoarray (a) -> getterm (k))
            elsif pseudoarray (a) -> getterm (k) = avg then
                dummy := pseudoarray (arb) -> addterm (pseudoarray (a) -> getterm (k))
            else
                dummy := pseudoarray (arc) -> addterm (pseudoarray (a) -> getterm (k))
            end if
        end for
        free pseudoarray(a)
        result join (join (quicksortb (ara), arb), quicksortb (arc))
    end if
end quicksortb

var testabc : int := Time.Elapsed
var result1 := quicksort (test1)
put "Sorted using the first term as the dividing factor in Quicksort: ", round (1000 / (((Time.Elapsed - testabc) / size) / 2)), " sorts per second."

testabc := Time.Elapsed
var result2 := quicksortb (test2)
put "Sorted using the average as the dividing factor in Quicksort: ", round (1000 / (((Time.Elapsed - testabc) / size) / 2)), " sorts per second."




Since I'm a novice at this, I'm sure there are plenty of ways to speed up the code, or a better way to handle the arrays. Memory usage is also a problem. I left out a free statement in one of the quicksorts and ended up with a 2 gig pagefile usage when sorting 1 million Rand.Real s. Memory usage is down to around 200-300 MBs when sorting 1 million Rand.Reals.

Any suggestions or comments?
Author:  Tony [ Tue Jul 20, 2004 1:44 pm ]
Post subject: 
instead of making up an array class (known as vector in C++ and ArrayList in Java I belive), why not just stick to the basics?

rether then passing the entire array back and forth, can't you just declear it as global where every function can access it? I think your bottleneck is that you have to pass the entire array to the next function on each pass of the loop or whatever. This would slow down your program exponensially, and you always want to avoid that.
Author:  andytyk [ Tue Jul 20, 2004 2:53 pm ]
Post subject: 
Hmm... if we just declared the arrays as globals (which means there will be a predefined number of them), we'll be stuck with using in-place sorting algorithms then..

And Bubblesort is great for small arrays (such as those with less than 100 values), its speed matches the Quicksort (avg) at around 5000 sorts per second. But if we're going to be sorting larger arrays... Confused

Array Size - BubbleSort - Quicksort (using average pivot) (sorts per second)
--------------------------------------------------------------------
50 - 11000 - 6250
100 - 6250 - 5000
500 - 1114 - 4065
2500 - 226 - 3374
3000 - 185 -3398

I'll play around with it to see where the bottleneck is.
Author:  Dan [ Tue Jul 20, 2004 4:16 pm ]
Post subject: 
Just whondering, what are u making that u need to sort an array of 3000? or are you just trying to find the best posable method of sorting?

It realy is to bad turing dose not have lists or vectors like java and c++.
Author:  andytyk [ Tue Jul 20, 2004 5:28 pm ]
Post subject: 
Well, a little of both, I want to find the fastest sorting method in Turing as well as finding which triangles to draw first in my 3d engine by sorting the z-values.

Coming from C++, PHP, etc. getting Turing to do what you want is a pain.

Using a QuickBubble sort (Quick sort for initial breaking down of arrays to small arrays of 20 or less then bubble sorting) yields pretty good results, I think I'll do a QuickInsertion and then compare.


Array size -> QuickBubble (sorts per second)
50 - 12500
100 - 11111
1000 - 5952
10000 - 4492
100000 - 3364
Author:  Catalyst [ Wed Jul 21, 2004 1:20 am ]
Post subject: 
well if ur using it for a 3d engine then you can sometimes get away with a bubble if u do maybe ten passes (and the rest is fast) because of temporal coherence
Author:  Catalyst [ Wed Jul 21, 2004 1:26 am ]
Post subject: 
would this do for a quicksort for your needs? (my tests get 9k-10k sorts per second)

code:

procedure qSort (var a : array 1 .. * of real, var b : array 1 .. * of int, l, h : int)
    if l < h then
        var aH : real
        var bH : int
        var i : int := l
        var j : int := h
        var mid : real := a (l)
        loop
            loop
                exit when a (i) >= mid
                i += 1
            end loop
            loop
                exit when a (j) <= mid
                j -= 1
            end loop
            if i <= j then
                aH := a (i)
                a (i) := a (j)
                a (j) := aH
                bH := b (i)
                b (i) := b (j)
                b (j) := bH
                i += 1
                j -= 1
            end if
            exit when i > j
        end loop
        qSort (a, b, l, j)
        qSort (a, b, i, h)
    end if
end qSort

Author:  andytyk [ Wed Jul 21, 2004 11:49 am ]
Post subject: 
That's interesting partitioning the array like that, never thought to do it that way. Thanks, I think I can get it up to 15k sorts per second now Smile

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy