QSort 32 bit vs 64 bit FB

General FreeBASIC programming questions.
Dinosaur
Posts: 1478
Joined: Jul 24, 2005 1:13
Location: Hervey Bay (.au)

Re: QSort 32 bit vs 64 bit FB

Post by Dinosaur »

Hi All

At the moment I sort the filename as a string, by using the whole string.
ie: "2154.jvp" or "32.jvp"

The disadvantage of that is, that 32 gets put later on the screen then 2154, but it is predictable.
Changing it to numeric, would involve extracting everything to the left of .jvp and converting string to number.

Am I going to make things worse (Time wise) ?

Regards
MrSwiss
Posts: 3910
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: QSort 32 bit vs 64 bit FB

Post by MrSwiss »

Dinosaur wrote:Am I going to make things worse (Time wise) ?
That is a YES.
Dinosaur wrote:Changing it to numeric, would involve extracting everything to the left of .jvp and converting string to number.
Definitely a preferred approach, if you require a fast sort!
(sorting routine for Long/LongInt, is far simpler than a String sort)
See MichaelW's example in this thread.
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Post by dodicat »

Integers / longs will obviously be a faster Qsort than strings.
But using strings gives more flexibility for a specific result.
For instance for strings starting with a number then a sequence of letters (as in your given clue- "2154.jvp" or "32.jvp"),a further customisation of the callback function is required.

Code: Select all


#include "crt/stdlib.bi"

Function callback Cdecl(n1 As Any Ptr,n2 As Any Ptr) As Long
     dim as string tmp1,tmp2
     dim as long V1=vallng(*Cptr(string Ptr,n1))
     dim as long V2=vallng(*Cptr(string Ptr,n2))
    if V1>V2 then  tmp1=chr(255)+*Cptr(string Ptr,n1):n1=@tmp1
    if V1<V2 then  tmp2=chr(255)+*Cptr(string Ptr,n2):n2=@tmp2
    If *Cptr(string Ptr,n1) < *Cptr(string Ptr,n2) Then Return -1  'CHANGE TO  1 FOR SORTING DOWN
    If *Cptr(string Ptr,n1) > *Cptr(string Ptr,n2) Then Return  1  'CHANGE TO -1 FOR SORTING DOWN
End Function

sub sort(s() as string)  
qsort( @s(Lbound(s)),(Ubound(s)-Lbound(s)+1),Sizeof(s),@callback)
end sub


#define Intrange(f,l) int(Rnd*((l+1)-(f))+(f))

#define P IntRange(97,122) 
#define RandomStringS chr(p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p,p)

function randominteger as string
    select case IntRange(1,4)
    case 1 :return "8."
    case 2:return "32."
    case 3:return "2154."
    case 4:return "10004."
    end select
    end function
  
                print "__________original _____________"
                Dim As Long num=150
                dim as long n
                
                Redim As string s(num)
                
                For n =lbound(s) To ubound(s)
                    s(n)=Randominteger
                    s(n)+=RandomStringS
                    s(n)=(mid(s(n),1,Intrange(8,38)))
                    print s(n)
                Next n
                print
                print "__________sorted _______________"
                print
                dim as double t1=timer
                sort(s())
                dim as double t2=timer
                For n =lbound(s) To ubound(s)
                    Print s(n)
                Next
                print
                print "Time taken "; t2-t1
                Sleep   
  
To sort a million of these takes about 5 seconds.
I am only guessing what your required sort should be.
"2154.jvp" or "32.jvp" is a strange clue.
Dinosaur
Posts: 1478
Joined: Jul 24, 2005 1:13
Location: Hervey Bay (.au)

Re: QSort 32 bit vs 64 bit FB

Post by Dinosaur »

Hi All

Thanks for the responses, they are really informative.

dodicat, the idea is that I create small buttons on the screen with the file number on the button.
But we dont want the operator to search for the correct number, so if the top left button is the lowest number, and the lower right
is the highest, then they can very quickly pick the one they want.

My current routine only sorts by the first character, that is why 2154 appears before 32. So the sort is not truly numerical (via string)
Time taken to sort, is critical as a lot of I/O is going on in the background.

Maximum number of filenames is 500, so perhaps a numerical sort could be faster then my current sort.

Regards
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Post by dodicat »

If you sort by valint(filename) only, then Qsort runs quite fast.
(I use Valint -- it is faster than vallng) even with the 64 bit compiler!
Assuming that your file names are some number and some extension, then for 504 files:

Code: Select all



#include "crt/stdlib.bi"

Function callback Cdecl(n1 As Any Ptr,n2 As Any Ptr) As Long
    Return Valint(*Cptr(String Ptr,n1)) - Valint(*Cptr(String Ptr,n2))
End Function

Sub sort(s() As String)  
    qsort( @s(Lbound(s)),(Ubound(s)-Lbound(s)+1),Sizeof(s),@callback)
End Sub


#define Intrange(f,l) int(Rnd*((l+1)-(f))+(f))


Function FileExtension As String
    Select Case IntRange(1,4)
    Case 1 :Return ".bas"
    Case 2 :Return ".jvp"
    Case 3 :Return ".cpp"
    Case 4 :Return ".png"
    End Select
End Function


Sub generaterandomintegers(s() As String,num As Long=500)
    Redim  s(1 To num)
    For n As Long=1 To num
        s(n)=Str(n)
    Next n
    For n As Long=1 To num
        Swap s(IntRange(1,num)),s(IntRange(1,num))
    Next n
End Sub

'set console/screen
Width 100,600
Dim As Long xres=108*8,yres=50*16

Print "__________original _____________"

Dim As Long num=504

Dim As String FileNumber(1 To num)
generaterandomintegers(FileNumber(),num)
Dim As Long n

Redim As String s(1 To num)

For n =Lbound(s) To Ubound(s)
    Var rs=FileNumber(n)
    rs=String(3-Len(rs),"0")+rs
    s(n)=rs
    s(n)+=FileExtension
    Print s(n)
Next n
Print
Print "__________sorting _______________"
Print
Dim As Double t1=Timer
sort(s())
Dim As Double t2=Timer
Screenres xres,yres
screencontrol 100,0,0
Width xres\8,yres\16
For n =Lbound(s) To Ubound(s)
    Color 0,Iif(n Mod 2=0,15,7)
    Print s(n)+"  ";
Next
Print
Print
Print "Time taken "; t2-t1
Sleep    
Most of the above code is to create file names, the sorting is trivial.
I hope the screen resolution fits your monitor, otherwise I don't know what you will see.
Dinosaur
Posts: 1478
Joined: Jul 24, 2005 1:13
Location: Hervey Bay (.au)

Re: QSort 32 bit vs 64 bit FB

Post by Dinosaur »

Hi All

Many thanks for that dodicat, I will implement it and see how it goes.

Regards
Dinosaur
Posts: 1478
Joined: Jul 24, 2005 1:13
Location: Hervey Bay (.au)

Re: QSort 32 bit vs 64 bit FB

Post by Dinosaur »

Hi All

Just an update.
Running this on a Fitlet Industrial PC (AMD A4 Micro-6400T) with Linux Mint 17.3 64 Bit.
Converted to sorting by numbers by changing:

Code: Select all

Function String_Compare Cdecl ( Byval lh As Any Ptr = 0, Byval rh As Any Ptr = 0 ) As Long
	Dim As String Ptr lhs = lh, rhs = rh
	Select Case *lhs
		Case Is > *rhs
			Return 1
		Case Is < *rhs
        	Return -1
		Case Else
        	Return 0
	End Select
End Function
To:

Code: Select all

Function String_Compare Cdecl ( Byval lh As Any Ptr = 0, Byval rh As Any Ptr = 0 ) As Long
    Return Valint(*Cptr(String Ptr,lh)) - Valint(*Cptr(String Ptr,rh))
End Function
Leaving all other code the same, I had a gain of about 200 micro sec.
303 files took 8.9 mSec
Then decided to reduce the File String length (55 bytes) by:
changing directories to the folder
reducing the filename string in the Array to 15 (by removing the path)

This resulted in:
303 files took 7.2 mSec

Tried Redim Array to actual number of files (instead of 500) but that didn't seem to make any difference.

All in all happy with the result

Once again, thanks to all.

Regards
Dinosaur
Posts: 1478
Joined: Jul 24, 2005 1:13
Location: Hervey Bay (.au)

Re: QSort 32 bit vs 64 bit FB

Post by Dinosaur »

Hi All

Discovered that not all files were being displayed with the above mods.
There was about 50 or more files not showing up.
After some experimentation I found the following.

If I read the Directory and load the filenames into one array, then pass that array to QSort
there is a problem. That is; when I print the Array before and after Qsort, I get 352 files before QSort (the correct number)
and 302 files after Qsort with the first 50 filenames showing up as blank.

If on the other hand I simply copy the contents of the first Array into a second Array, which is then passed to Qsort
then all is ok.

Code: Select all

Sub GetFileList
    ChDir("/home/barfresh/conchmi/recipes")			'
    Dim FileNaam As ZString * 9						'largest number expected
    Dim FileSpec As String 
    Dim As Long FileCount,Xr
    Dim As String SortArray(500)					'500 is max screen Buttons
    Times.StartTime = Timer
    FileSpec = "*"									'all files
    FileNaam = Dir(FileSpec,fbnormal)
    FileCount = 0
    Do	While Len(FileNaam) > 0						'Quit when last file Read
        SortArray(FileCount) = FileNaam				'save each FileName
        FileNaam = Dir()                 			'look for next FileNaam
        FileCount += 1                              'update number of files found.    	
    Loop
    '----------If not put into second Array, then sort fails-------------------
    Dim As String SortArray2(FileCount)
    For Xr = 1 to Filecount
		SortArray2(Xr) = SortArray(Xr)
	Next
	'----------But this Array is exact length required-------------------------
	Sort (SortArray2())
	If FileCount > 0 Then
        If FileCount < 501 Then 	
           	For Xr = 1 To FileCount
   		        FileArray.Name(Xr) = SortArray(Xr)
   	        Next
   	    Endif
   	EndIf 
   	FileArray.Nbr = FileCount
    ChDir("/home/barfresh/conchmi")
    Print "Elapsed;";Timer - Times.StartTime
End Sub
The only difference in the Array's that I can see are that the first Array is 500 elements long (not knowing how many I will need)
and the second is the exact length of 352 elements. If I make the second Array 500 elements long and copy the filecount (352)
into it, it fails as well.

What have I missed here.????

Regards
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Post by dodicat »

Try the other qsort (independent of C).

Code: Select all



'=================  OTHER QSORT ==============================
Sub sort(array() As string,begin As Long=0,Finish As Long=-1)
            If begin>finish Then begin=Lbound(array):Finish=Ubound(array)
            Dim As Long i=begin,j=finish
            static As long x :x=valint(array(((I+J)\2)))
                While I <= J
                While valint(array(I)) < X :I+=1:Wend 'CHANGE TO > FOR SORTING DOWN
                While valint(array(J)) > X :J-=1:Wend 'CHANGE TO < FOR SORTING DOWN
                        If I<=J Then Swap array(I),array(J): I+=1:J-=1
                Wend
                    If J >begin Then  sort(array(),begin,J)
                    If I <Finish Then sort(array(),I,Finish)
End Sub
'============================================================

#define Intrange(f,l) int(Rnd*((l+1)-(f))+(f))


Function FileExtension As String
    Select Case IntRange(1,4)
    Case 1 :Return ".bas"
    Case 2 :Return ".jvp"
    Case 3 :Return ".cpp"
    Case 4 :Return ".png"
    End Select
End Function


Sub generaterandomintegers(s() As String,num As Long=500)
    Redim  s(1 To num)
    For n As Long=1 To num
        s(n)=Str(n)
    Next n
    For n As Long=1 To num
        Swap s(IntRange(1,num)),s(IntRange(1,num))
    Next n
End Sub

'set console/screen
Width 100,600
Dim As Long xres=108*8,yres=50*16

Print "__________original _____________"

Dim As Long num=504

Dim As String FileNumber(1 To num)
generaterandomintegers(FileNumber(),num)
Dim As Long n

Redim As String s(1 To num)

For n =Lbound(s) To Ubound(s)
    Var rs=FileNumber(n)
    rs=String(3-Len(rs),"0")+rs
    s(n)=rs
    s(n)+=FileExtension
    Print s(n)
Next n
Print
Print "__________sorting _______________"
Print
Dim As Double t1=Timer
sort(s())
Dim As Double t2=Timer
Screenres xres,yres
screencontrol 100,0,0
Width xres\8,yres\16
For n =Lbound(s) To Ubound(s)
    Color 0,Iif(n Mod 2=0,15,7)
    Print s(n)+"  ";
Next
Print
Print
Print "Time taken "; t2-t1
Sleep    
But I think your problem is blank elements of your array.
Remember valint("") is zero, so all your blanks are sorted to the top, and the printout for these is nothing.
By transferring to another array you are getting filecount of non blank strings.
In other words, some of your original (0 to 500) array will be blank, and thus unsuitable/void.

Perhaps you could try:

Code: Select all

Sub GetFileList
    ChDir("/home/barfresh/conchmi/recipes")         '
    Dim FileNaam As ZString * 9                  'largest number expected
    Dim FileSpec As String 
    Dim As Long FileCount,Xr
    reDim As String SortArray(500)               '500 is max screen Buttons
    Times.StartTime = Timer
    FileSpec = "*"                           'all files
    FileNaam = Dir(FileSpec,fbnormal)
    FileCount = 0
    Do   While Len(FileNaam) > 0                  'Quit when last file Read
        SortArray(FileCount) = FileNaam            'save each FileName
        FileNaam = Dir()                          'look for next FileNaam
        FileCount += 1                              'update number of files found.       
    Loop
    redim preserve SortArray(0 to Filecount)
    
    
    '----------If not put into second Array, then sort fails-------------------
   ' Dim As String SortArray2(FileCount)
    'For Xr = 1 to Filecount
      'SortArray2(Xr) = SortArray(Xr)
   'Next
   '----------But this Array is exact length required-------------------------
   Sort (SortArray))
   If FileCount > 0 Then
        If FileCount < 501 Then    
              For Xr = 1 To FileCount
                 FileArray.Name(Xr) = SortArray(Xr)
              Next
          Endif
      EndIf 
      FileArray.Nbr = FileCount
    ChDir("/home/barfresh/conchmi")
    Print "Elapsed;";Timer - Times.StartTime
End Sub 
Tourist Trap
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: QSort 32 bit vs 64 bit FB

Post by Tourist Trap »

dodicat wrote:Try the other qsort (independent of C).
We had discussed how to remove efficiently blank strings in an array. Do you remember this? You were using memcopy (with some crash), maybe august 2015... I can't remember too well.
MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: QSort 32 bit vs 64 bit FB

Post by MichaelW »

dodicat wrote:The qsort routine lies deep within a C compiler or a C runtime.
It lies mysteriously out of our reach (or most of our reaches anyways)...
Yes, but the C source code for it is included in the src\crt directory of the Microsoft Platform SDKs, at least up through the Windows Server 2003 SP1 version, available here.
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Post by dodicat »

MichaelW
I think perhaps this is the qsort:
http://aturing.umcs.maine.edu/~sudarsha ... /n/qsort.c

Not really a recursive quicksort at all.

T.T.
Using a standard quicksort, you can of course sort only the part of the array you need to sort.

Code: Select all


'=================  OTHER QSORT ==============================
Sub sort(array() As string,begin As Long=0,Finish As Long=-1)
            If begin>finish Then begin=Lbound(array):Finish=Ubound(array)
            Dim As Long i=begin,j=finish
            static As long x :x=valint(array(((I+J)\2)))
                While I <= J
                While valint(array(I)) < X :I+=1:Wend 'CHANGE TO > FOR SORTING DOWN
                While valint(array(J)) > X :J-=1:Wend 'CHANGE TO < FOR SORTING DOWN
                        If I<=J Then Swap array(I),array(J): I+=1:J-=1
                Wend
                    If J >begin Then  sort(array(),begin,J)
                    If I <Finish Then sort(array(),I,Finish)
End Sub
'============================================================
#define range(f,l) int(Rnd*((l+1)-(f))+(f))
dim as string s="1234567890"
#define q s[range(0,9)]
 
dim as string array(50)
print "Before"
for n as long=0 to 25
    array(n)=chr(q,q,q,q)
    print n,array(n) 
next
print

sort(array(),0,25)
print "After"
for n as long=0 to 50
    print n, array(n) 
next
sleep


 
Dinosaur
Posts: 1478
Joined: Jul 24, 2005 1:13
Location: Hervey Bay (.au)

Re: QSort 32 bit vs 64 bit FB

Post by Dinosaur »

Hi All

Yes, the reDim fixed the problem.
I had to get a bit more inventive to reduce the time.
The number of files don't normally change during the day, unless the operator adds one or deletes one.
So, I check for that and don't do another Qsort if not needed.
With Qsort it takes 6mSec and without 3.2mSec

Code: Select all

Sub GetFileList
    ChDir("/home/barfresh/conchmi/recipes")			'
    Dim FileNaam As ZString * 9						'largest number expected
    Dim FileSpec As String 
    Dim As Long FileCount,Xr
    reDim As String SortArray(500)					'500 is max screen Buttons
    FileSpec = "*"									'all files
    FileNaam = Dir(FileSpec,fbnormal)
    FileCount = 0
    Do	While Len(FileNaam) > 0						'Quit when last file Read
        SortArray(FileCount) = FileNaam				'save each FileName
        FileNaam = Dir()                 			'look for next FileNaam
        FileCount += 1                              'update number of files found.    	
    Loop
	If (FileArray.Flag < 1) Or (FileCount <> FileArray.Nbr) Then    
		redim preserve SortArray(Filecount)			'must have added or deleted a file.
		Sort (SortArray())
		If FileCount > 0 Then
			If FileCount < 501 Then 	
				For Xr = 1 To FileCount
					FileArray.Name(Xr) = SortArray(Xr)
				Next
				FileArray.Flag = 1
			Endif
		EndIf 
   	EndIf
   	FileArray.Nbr = FileCount
    ChDir("/home/barfresh/conchmi")
End Sub
I still don't know which QSort I am using.

Code: Select all

#Include once "allegro.bi"
#Include once "cgui.bi"
#include once "vbcompat.bi"
#Include once "types.bi"
#Include once "declares.bi"
#Include once "presets.bi"
and my .bas files
crt.bi or dir.bi are not included.
However, if I do, it seems to make little diference.
Perhaps the appropriate file is added during compile.
compiling C: gcc -m64 -march=x86-64 -S -nostdlib -nostdinc -Wall -Wno-unused-label -Wno-unused-function -Wno-unused-variable -Wno-unused-but-set-variable -Wno-main -Werror-implicit-function-declaration -O0 -fno-strict-aliasing -frounding-math -fno-math-errno -fno-exceptions -fno-unwind-tables -fno-asynchronous-unwind-tables -g -masm=intel "Win00.c" -o "Win00.asm"
linking: ld -m elf_x86_64 -o "Win00" -dynamic-linker /lib64/ld-linux-x86-64.so.2 "/usr/local/bin/../lib/freebasic/linux-x86_64/fbextra.x" -L "/usr/local/bin/../lib/freebasic/linux-x86_64" -L "." -L "/usr/lib/gcc/x86_64-linux-gnu/4.8" "/usr/lib/gcc/x86_64-linux-gnu/4.8/../../../x86_64-linux-gnu/crt1.o" "/usr/lib/gcc/x86_64-linux-gnu/4.8/../../../x86_64-linux-gnu/crti.o" "/usr/lib/gcc/x86_64-linux-gnu/4.8/crtbegin.o" "/usr/local/bin/../lib/freebasic/linux-x86_64/fbrt0.o" "Win00.o" "-(" -lalleg -lX11 -lXext -lXpm -lXxf86vm -lXcursor -lcgui -lfb -ltinfo -lm -ldl -lpthread -lgcc -lgcc_eh -lc "-)" "/usr/lib/gcc/x86_64-linux-gnu/4.8/crtend.o" "/usr/lib/gcc/x86_64-linux-gnu/4.8/../../../x86_64-linux-gnu/crtn.o"
Regards
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Post by dodicat »

If you are using:

Sub sort(array() As string,begin As Long=0,Finish As Long=-1)
...
end sub


This is a standalone sort, independent of any library.
It is slightly faster than the qsort from C.
Post Reply