Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
radix vs quiksort
#31
Quote:are we talking qb or fb here?
We've been talking QB up to now, but if you want to run some sort testing and timing in FB, that'll be fine.
*****
Reply
#32
i've been testing in FB, comparing against the Ethan Winer QuickSort(), and the C Runtime qsort()

it seems like it would be slow. on my 5000 string data with the Winer QuickSort 48,152 string comparisions are performed, with the Moneo Selection Sort 12,497,500 string comparisons occur.
EVEN MEN OF STEEL RUST.
[Image: chav.gif]
Reply
#33
Quote:i've been testing in FB, comparing against the Ethan Winer QuickSort(), and the C Runtime qsort()

it seems like it would be slow. on my 5000 string data with the Winer QuickSort 48,152 string comparisions are performed, with the Moneo Selection Sort 12,497,500 string comparisons occur.
The timing criteria used by the original SortDemo program is based on the number of times that elements are swapped, not on the number compared. I used the same criteria in the test program that I wrote. Maybe that has something to do with it.

As you probably already know, the beginning random order of the elements in the array must be exactly the same for each sort algorithm applied. This can be done by generating the random numbers each time WITHOUT having done a RANDOMIZE TIMER statement.

If your program is not too long, why don't you post it so I can try it.
*****
Reply
#34
i tested string compares as i thought this would be the most processor intensive part, in an ideal world i would just be swapping pointers to strings so to me the number of swaps was not as important

ok, stripped out some of the the fluff and here it is.

Code:
#include "crt.bi"

#define GetRandInt(nmin,nmax) Int((nmax - nmin + 1) * rnd + nmin)

Option Explicit

Const NUM_TESTRECORDS As Integer = 5000

Dim Shared Test_Array(NUM_TESTRECORDS) As String
Dim Shared NumCompares As Integer
Dim Shared NumSwaps As Integer

Function String_Compare(a As String, b As String) As Integer
  NumCompares += 1
  Return strcmp(strptr(a), strptr(b))
End Function

Sub String_Swap(a As String, b As String)
  Dim Temp As String
    NumSwaps += 1
    Temp = a : a = b : b = Temp
End Sub

Sub Winer_QSort(ArrayToSort() As String, StartEl As Integer, NumEls As Integer)
  ' Winer QuickSort Routine
  Dim Temp As String
  Dim First, Last, i, j, StackPtr As Integer
  ReDim QStack(NumEls \ 5 + 10)
    First = StartEl
    Last = StartEl + NumEls - 1
    Do
      Do
        Temp = ArrayToSort((Last + First) \ 2)
        i = First
        j = Last
        Do
          While (String_Compare(ArrayToSort(i), Temp) < 0) 'ArrayToSort(i) < Temp
            i = i + 1
          Wend
          While (String_Compare(ArrayToSort(j), Temp) > 0) 'ArrayToSort(j) > Temp
            j = j - 1
          Wend
          If i > j Then Exit Do
          If i < j Then String_Swap(ArrayToSort(i), ArrayToSort(j))
          i = i + 1
          j = j - 1
        Loop While i <= j
        If i < Last Then
          QStack(StackPtr) = i
          QStack(StackPtr + 1) = Last
          StackPtr = StackPtr + 2
        End If
        Last = j
      Loop While First < Last
      If StackPtr = 0 Then Exit Do
      StackPtr = StackPtr - 2
      First = QStack(StackPtr)
      Last = QStack(StackPtr + 1)
    Loop
  Erase QStack
End Sub

Sub Moneo_SSort(ArrayToSort() As String, StartEl As Integer, NumEls As Integer)
  ' Moneo Selection Sort Routine
  Dim As Integer i, j, m
    For i = StartEl To NumEls + StartEl - 1
      m = i
      For j = i + 1 To NumEls + StartEl - 1
        If String_Compare(ArrayToSort(j), ArrayToSort(m)) < 0 Then m = j
      Next j
      String_Swap(ArrayToSort(i), ArrayToSort(m))
    Next i
End Sub

Function GenerateFakeData()
  Dim tmpRec, T, RandomStringSize As uInteger
    Randomize 1 ' Force the same set every time
    For tmpRec = 0 To NUM_TESTRECORDS - 1
      Test_Array(tmpRec) = ""
      RandomStringSize = GetRandInt(4, 8)
      For T = 1 To RandomStringSize
        Test_Array(tmpRec) = Test_Array(tmpRec) + chr(GetRandInt(65, 90))
      Next T
    Next tmpRec
End Function

Sub Main()
  Dim tmpRec As uInteger
  Dim As Double st, et, tt
    
    ' TEST 1
    NumCompares = 0
    NumSwaps = 0
    Print "**************** Test 1 ****************"
    Print "- Generating";NUM_TESTRECORDS;" test strings..."
    GenerateFakeData
    Print
    Print "- Sorting using Winer QuickSort..."
    st = Timer
    Winer_QSort(Test_Array(), 0, NUM_TESTRECORDS)
    et = Timer
    tt = (et - st)
    Print
    Print "  Time taken                   : ";
    printf("%1.3f", tt)
    Print " seconds."
    Print "  Number of string comparisons :";NumCompares
    Print "  Number of string swaps       :";NumSwaps    
    Print
    
    ' TEST 2
    NumCompares = 0
    NumSwaps = 0
    Print "**************** Test 2 ****************"
    Print "- Re-Generating";NUM_TESTRECORDS;" test strings..."
    GenerateFakeData
    Print
    Print "- Sorting using Moneo Selection Sort..."
    st = Timer
    Moneo_SSort(Test_Array(), 0, NUM_TESTRECORDS)
    et = Timer
    tt = (et - st)
    Print
    Print "  Time taken                   : ";
    printf("%1.3f", tt)
    Print " seconds."
    Print "  Number of string comparisons :";NumCompares
    Print "  Number of string swaps       :";NumSwaps  
    Print
    
    Print "Press any key to continue . . . ";
    Sleep
    End

End Sub

Main
EVEN MEN OF STEEL RUST.
[Image: chav.gif]
Reply
#35
Yetifoot,
Nice piece of code. I'll try to figure it out and do some testing.
*****
EDIT: Dec 26, 2005, 1:00 pm.
First of all, your program issued compile errors. I still have FB version 13, but that shouldn't matter. In several places you used an ampersand (&) instead of a plus sign (+), and on PRINT lines you also used ampersand which I had to replace with a semicolon.

When it finally compiled and ran, it printed the following results which I don't really understand.
Code:
*** For Winer's Quick Sort
Generating  5000 fake records...OK

Sorting by FirstName...OK
Time Taken  7.272991399077e-003

Test Data : FirstName
AAAJNX
AAGWAHS
AALWY
AAPQMFTZ
AAPQX
Press any key to continue . . .
*** For Moneo Selection Sort, all of the above was the same except:
Time Taken  0.8795838577252653
I don't understand the "Time Taken" because the Winer sort time has an expontent "e". How do you compare these times? Is 0.87 seconds? I'm using a 2.4 ghz machine which may vary from yours.

Maybe you did some last minute enhancements before posting the code. Trying to get your code to work has steered me away from the original issue, that is, comparing the timing of sort algorithms. If you would be so kind, please post a workable version with understandable output.
*****
Reply
#36
Quote:First of all, your program issued compile errors. I still have FB version 13, but that shouldn't matter. In several places you used an ampersand (&) instead of a plus sign (+), and on PRINT lines you also used ampersand which I had to replace with a semicolon.
This is in fact a new feature of FB version 0.15 (it's borrowed from VB) - & is string concatenation with automatic conversion to string of any other datatype.
Reply
#37
apologies if you had trouble with the code, it wasn't really intended for release, it was my private test. I have now updated the test code in my previous post. The program now runs both tests (Using Randomize 1 to force the same set of data) the ampersand character has now gone replaced with semi-colon (changing to a + causes type mismatch on 0.15) also i have used format to print the time without e form.
EVEN MEN OF STEEL RUST.
[Image: chav.gif]
Reply
#38
Quote:apologies if you had trouble with the code, it wasn't really intended for release, it was my private test. I have now updated the test code in my previous post. The program now runs both tests (Using Randomize 1 to force the same set of data) the ampersand character has now gone replaced with semi-colon (changing to a + causes type mismatch on 0.15) also i have used format to print the time without e form.
Hey, no problem.
I got an error compiling the new version. I don't have the include file called vbcompat.bi.
Does the program really need it? What's it for?
If you need it, where can I get it, and into which subdirectory of Freebasic do I put it?
*****
Reply
#39
Quote:......
This is in fact a new feature of FB version 0.15 (it's borrowed from VB) - & is string concatenation with automatic conversion to string of any other datatype.

DrV,
Would you kindly provide me with a link where I can download FB version 0.15 for Windows, including the latest version of the FBIDE.

Thanks.
*****
Reply
#40
I'm not an FBIDE user myself, but apparently there hasn't been a packaged release with 0.15 yet; luckily, it's relatively simple to get the two separately and configure FBIDE to use the new fbc release.

Get the latest FBIDE installer from here: http://prdownloads.sourceforge.net/fbide...e?download
(You can see all the releases here: http://sourceforge.net/project/showfiles...5923#files )

Get fbc 0.15 for Windows here: http://prdownloads.sourceforge.net/fbc/F...e?download

Run the fbc installer first, then run the FBIDE installer and specify the path to fbc.exe (where you installed fbc 0.15) when prompted.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)