Tweet
Hi everybody,
They said "It could not be done"
But I finally got my SmartSort alpha version running.
It is FAST, blazingly FAST.
How about sorting 16 millions 4 bytes Alpha keys from A to Z in 1.68 seconds while ARRAY SORT take 30.18 seconds for the same work ?
It is very easy to scale up, if you have enough memory, to all 256 Asc codes.
Same thing for the number of bytes in the key.
This is the first working version so it can probably be improved yet.
Comments welcomed.
I wonder if M. Zale would be willing to be my Agent as I would not know how to present this program to Microsoft or Google ?
They said "It could not be done"
But I finally got my SmartSort alpha version running.
It is FAST, blazingly FAST.
How about sorting 16 millions 4 bytes Alpha keys from A to Z in 1.68 seconds while ARRAY SORT take 30.18 seconds for the same work ?
It is very easy to scale up, if you have enough memory, to all 256 Asc codes.
Same thing for the number of bytes in the key.
This is the first working version so it can probably be improved yet.
Comments welcomed.
I wonder if M. Zale would be willing to be my Agent as I would not know how to present this program to Microsoft or Google ?
Code:
'SmartAlphaSort.bas by Guy Dombrowski (all rights reserved)
'Developped using my 1980 SmartSort, for numeric only, as a template
'A new kind of algorithm for sorting alpha keys without moving string around
'It is many times faster than existing algorithm and easy to scale up
#COMPILE EXE
#BREAK ON
DEFLNG a-z
FUNCTION PBMAIN () AS LONG
LOCAL t1,t2 AS SINGLE: RANDOMIZE CVS(CHR$(255,255,255,255))
M=2000000 ' Maximum number of keys to be sorted
N=4 ' Number of bytes in keys
L=65: U=90 ' Lower and Higher ASC value to be sorted between A and Z for now
R=U-L ' Range limit for test 0 to 25 A=0 Z=25
B=1000000 ' Basic array size for 4 byte key
K=(B*(R+1)) ' Maximum array size
F=0 ' Index pointer
P=0 ' Index pointer
Y=0 ' Index pointer
DIM tot(k) ' Total instance of each character per row
DIM jrx(k) ' Index for big array
DIM jrp(k) ' Pointer for building index
DIM jrs(m,n) ' Sorted Asc value minus Lbound by column
DIM a(n) ' Array for column Asc value
DIM k(n) ' Array for Modulo math
k(0)=1000000
k(1)=10000
k(2)=100
k(3)=0
PRINT "Building Test file...";
GOSUB MakeTrs ' Make dummy transactions
PRINT "Smart Sorting";m;"Alpha keys..."
'Reading file from simulated hard disk and counting each characters per column
t1=TIMER: FOR t=0 TO m: GOSUB ReadTrs: NEXT: t2=TIMER
'Building index while checking for multiple keys
FOR x=0 TO k
IF tot(x)>0 THEN
q=tot(x): WHILE q>0: jrx(f)=x: DECR q: INCR f: WEND
jrp(x)=p: p=p+tot(x)
END IF
NEXT
'Building sorted array from scratch using computed Asc values
FOR t=0 TO m
z=jrx(t): FOR y=0 TO n-2: a(y)=z\k(y): z=z MOD k(y): NEXT: a(y)=z
FOR x=0 TO n-1: jrs(t,x)=a(x): NEXT ' You can write sorted keys to disk here
NEXT
t3=TIMER ' For total time
'Show time elapsed for SmartSort and 100 first keys
PRINT "Reading and counting ="; t2-t1; " Actual sorting =";t3-t2;" Total =";t3-t1: PRINT
FOR t=0 TO 99: PRINT CHR$(jrs(t,0)+L);CHR$(jrs(t,1)+L);CHR$(jrs(t,2)+L);CHR$(jrs(t,3)+L);" ";: NEXT
PRINT: PRINT: PRINT "Now do a PB ARRAY SORT on the same starting data..."
t1 = TIMER: ARRAY SORT test$(): t2=TIMER
'Show time elapsed for PB Array Sort and 100 first keys
PRINT "Time for ARRAY SORT is "; t2-t1; " secs, and the 1st 100 sorted values are: ": PRINT
FOR x=0 TO 99: PRINT test$(x);" ";: NEXT
PRINT: PRINT: PRINT "The results should match. Press a key or clic [x] to END...";
WAITKEY$: END
ReadTrs:REM Build numeric arrays with ASC value minus lbound of all alpha keys
FOR c=0 TO n-1: a(c)=ASC(MID$(test$(t),c+1))-L: NEXT
w=(a(0)*1000000)+(a(1)*10000)+(a(2)*100)+a(3)
INCR tot(w)
RETURN
MakeTrs:REM Big random 4 byte alpha key array...
REDIM test$(m), t1(m),t2(m),t3(m),t4(m)
FOR y=0 TO m: t1(y)=RND(L,U):t2(y)=RND(L,U): t3(y)=RND(L,U):t4(y)=RND(L,U): NEXT
FOR x=0 TO m: test$(x)=CHR$(t1(x),t2(x),t3(x),t4(x)): NEXT
ERASE t1(),t2(),t3(),t4()
RETURN
END FUNCTION
Comment