QSort 32 bit vs 64 bit FB
Re: QSort 32 bit vs 64 bit FB
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
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
Re: QSort 32 bit vs 64 bit FB
That is a YES.Dinosaur wrote:Am I going to make things worse (Time wise) ?
Definitely a preferred approach, if you require a fast sort!Dinosaur wrote:Changing it to numeric, would involve extracting everything to the left of .jvp and converting string to number.
(sorting routine for Long/LongInt, is far simpler than a String sort)
See MichaelW's example in this thread.
Re: QSort 32 bit vs 64 bit FB
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.
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.
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
I am only guessing what your required sort should be.
"2154.jvp" or "32.jvp" is a strange clue.
Re: QSort 32 bit vs 64 bit FB
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
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
Re: QSort 32 bit vs 64 bit FB
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:
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.
(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
I hope the screen resolution fits your monitor, otherwise I don't know what you will see.
Re: QSort 32 bit vs 64 bit FB
Hi All
Many thanks for that dodicat, I will implement it and see how it goes.
Regards
Many thanks for that dodicat, I will implement it and see how it goes.
Regards
Re: QSort 32 bit vs 64 bit FB
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:
To:
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
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
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
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
Re: QSort 32 bit vs 64 bit FB
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.
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
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
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
Re: QSort 32 bit vs 64 bit FB
Try the other qsort (independent of C).
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
'================= 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
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
-
- Posts: 2958
- Joined: Jun 02, 2015 16:24
Re: QSort 32 bit vs 64 bit FB
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.dodicat wrote:Try the other qsort (independent of C).
Re: QSort 32 bit vs 64 bit FB
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 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)...
Re: QSort 32 bit vs 64 bit FB
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.
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
Re: QSort 32 bit vs 64 bit FB
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
I still don't know which QSort I am using.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.
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
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
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"
Regardslinking: 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"
Re: QSort 32 bit vs 64 bit FB
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.
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.