QSort 32 bit vs 64 bit FB

General FreeBASIC programming questions.
Dinosaur
Posts: 1186
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

Re: QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 24, 2016 14:54

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: 3128
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: QSort 32 bit vs 64 bit FB

Postby MrSwiss » Nov 24, 2016 15:50

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: 5828
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Postby dodicat » Nov 24, 2016 18:25

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: 1186
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

Re: QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 24, 2016 23:29

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: 5828
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Postby dodicat » Nov 25, 2016 1:19

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: 1186
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

Re: QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 25, 2016 2:41

Hi All

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

Regards
Dinosaur
Posts: 1186
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

Re: QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 26, 2016 0:43

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: 1186
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

Re: QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 27, 2016 1:58

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: 5828
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Postby dodicat » Nov 27, 2016 4:11

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: 2756
Joined: Jun 02, 2015 16:24

Re: QSort 32 bit vs 64 bit FB

Postby Tourist Trap » Nov 27, 2016 4:31

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

Postby MichaelW » Nov 27, 2016 7:58

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: 5828
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Postby dodicat » Nov 27, 2016 10:50

MichaelW
I think perhaps this is the qsort:
http://aturing.umcs.maine.edu/~sudarshan.chawathe/200801/capstone/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: 1186
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

Re: QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 27, 2016 16:31

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: 5828
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Postby dodicat » Nov 27, 2016 18:22

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.

Return to “General”

Who is online

Users browsing this forum: Linuxbob and 3 guests