Here is a little test program I threw together to benchmark the 16 bit string compare code I'm preparing for a future ROM version. A little bonus here is a sort implementation you may not have seen before.
Back in the 90s I was working on a project I inherited from someone else. It involved nightly data dumps from a production system to a local server that made the data accessible to customers via modem, using custom software. The process was rather labor intensive. The operator had to run the data extraction, ftp the data to a PC, which was then imported by a custom VB application that required multiple starts, executing other program, then continuing, etc... It was impossible to automate the way it was.
Upon investigation, the original programmer did not know how to implement a sort, so he was using an external utility. (he also didn't seem to know how to take a shower... but that's another topic)
After a quick search on Yahoo, no VB sorts turned up (I think the search engine was undergoing maintenance), so I threw in a bubble sort and went home. Some 12 hours later, the sort was still going so I killed it, wrote a more optimal version, and on the first try it took about 18 minutes to sort the 80,000+ records, and it didn't require human intervention so it could be launched automatically.
Anyway, a more polished version of that sort is below. This has some optimizations that weren't in the original as it's aimed at the Microsoft BASIC interpreter.
The sort is, at the very least, a really improved version of the bubble sort. It functions a bit like a comb or shell sort, so I'm not sure what you'd call it. It's easy to implement, pretty fast, and it's fairly small. Taking a hint from the comb sort, dividing the gap by two may not be the most efficient, but it works pretty well for something I came up with off the top of my head in my 20s.
The data comes from a list of the 1000 most common surnames, and it is truncated here for space. The data includes a few other numbers with it that I didn't waste time removing. With all the additional data, only 894 names fit in memory, but that provides a really good workout for the interpreter and sort. Sorting takes over 10 minutes on a regular MC-10, but I'm hoping the new string comparison cuts that by at least 20%, which is about what you can expect from unrolling a loop once.
0 I=0:N=1000:C=0:D=0:E=0:NW=0
'initialize the index array, and read in the names. Skip the other data.
'scans through the data to determine the array sizes before dimensioning the arrays.
'The most heavily use variables are initialized on the first like to insure they are
' at the start of the variable table
'
10 I=0:J=0:G=0:N=0:Q=0
15 PRINT"SCANNING FOR END OF DATA"
20 READ K$,C,D,E:IF K$<>"" THEN N=N+1:GOTO 20
30 RESTORE
40 DIM A$(N),B(N)
45 PRINT"INITIALIZING ARRAYS"
50 FORI=1TON:READ A$(I),C,D,E:B(I)=I:NEXT
60 PRINT:PRINT N" MOST POPULAR SIR NAMES FROM MOST TO LEAST POPULAR"
70 GOSUB 2000
80 PRINT:PRINT "SORTING"N"NAMES":GOSUB 10000
90 PRINT:PRINT N" MOST POPULAR SIR NAME IN ALPHABETICAL ORDER"
95 GOSUB 2000
96 END
'print out the names based on the array index
2000 FOR I=1 TO N:PRINT A$(B(I))" ";:NEXT:RETURN
'optimized bubble(?) sort.
'Moves data as far as possible with each Middle loop
'Skips data that doesn't need sorted with each new pass on inner loop.
'P = what we divide the array size by to get the gap
'G = the gap
'using nested for loops avoids having to perform a line search that would
'happen with GOTO. The address is simply pulled off of the stack.
'Using STEP 0 keeps FOR NEXT from changing the variable and the endless loop
'exits once the exit condition is achieved
10000 P=1:FORG=2TO1STEP0:P=P*2:G=INT(N/P):NW=N-G:PRINTG;
10010 FORQ=1TO0STEP0:Q=0:FORI=1TONW
10020 IFA$(B(I))>A$(B(I+G))THENT=B(I):B(I)=B(I+G):B(I+G)=T:Q=I
10030 NEXT:IFQ>0THENNW=Q
10040 NEXT:NEXT:RETURN
'1000 MOST POPULAR SIR NAMES FROM MOST TO LEAST POPULAR
100 DATA SMITH,2501922,1.006,1,JOHNSON,2014470,.81,2,WILLIAMS,1738413,.699,3
101 DATA JONES,1544427,.621,4,BROWN,1544427,.621,5,DAVIS,1193760,.48,6
...
1000 DATA "",0,0,0 :REM END OF DATA MARKER
Back in the 90s I was working on a project I inherited from someone else. It involved nightly data dumps from a production system to a local server that made the data accessible to customers via modem, using custom software. The process was rather labor intensive. The operator had to run the data extraction, ftp the data to a PC, which was then imported by a custom VB application that required multiple starts, executing other program, then continuing, etc... It was impossible to automate the way it was.
Upon investigation, the original programmer did not know how to implement a sort, so he was using an external utility. (he also didn't seem to know how to take a shower... but that's another topic)
After a quick search on Yahoo, no VB sorts turned up (I think the search engine was undergoing maintenance), so I threw in a bubble sort and went home. Some 12 hours later, the sort was still going so I killed it, wrote a more optimal version, and on the first try it took about 18 minutes to sort the 80,000+ records, and it didn't require human intervention so it could be launched automatically.
Anyway, a more polished version of that sort is below. This has some optimizations that weren't in the original as it's aimed at the Microsoft BASIC interpreter.
The sort is, at the very least, a really improved version of the bubble sort. It functions a bit like a comb or shell sort, so I'm not sure what you'd call it. It's easy to implement, pretty fast, and it's fairly small. Taking a hint from the comb sort, dividing the gap by two may not be the most efficient, but it works pretty well for something I came up with off the top of my head in my 20s.
The data comes from a list of the 1000 most common surnames, and it is truncated here for space. The data includes a few other numbers with it that I didn't waste time removing. With all the additional data, only 894 names fit in memory, but that provides a really good workout for the interpreter and sort. Sorting takes over 10 minutes on a regular MC-10, but I'm hoping the new string comparison cuts that by at least 20%, which is about what you can expect from unrolling a loop once.
0 I=0:N=1000:C=0:D=0:E=0:NW=0
'initialize the index array, and read in the names. Skip the other data.
'scans through the data to determine the array sizes before dimensioning the arrays.
'The most heavily use variables are initialized on the first like to insure they are
' at the start of the variable table
'
10 I=0:J=0:G=0:N=0:Q=0
15 PRINT"SCANNING FOR END OF DATA"
20 READ K$,C,D,E:IF K$<>"" THEN N=N+1:GOTO 20
30 RESTORE
40 DIM A$(N),B(N)
45 PRINT"INITIALIZING ARRAYS"
50 FORI=1TON:READ A$(I),C,D,E:B(I)=I:NEXT
60 PRINT:PRINT N" MOST POPULAR SIR NAMES FROM MOST TO LEAST POPULAR"
70 GOSUB 2000
80 PRINT:PRINT "SORTING"N"NAMES":GOSUB 10000
90 PRINT:PRINT N" MOST POPULAR SIR NAME IN ALPHABETICAL ORDER"
95 GOSUB 2000
96 END
'print out the names based on the array index
2000 FOR I=1 TO N:PRINT A$(B(I))" ";:NEXT:RETURN
'optimized bubble(?) sort.
'Moves data as far as possible with each Middle loop
'Skips data that doesn't need sorted with each new pass on inner loop.
'P = what we divide the array size by to get the gap
'G = the gap
'using nested for loops avoids having to perform a line search that would
'happen with GOTO. The address is simply pulled off of the stack.
'Using STEP 0 keeps FOR NEXT from changing the variable and the endless loop
'exits once the exit condition is achieved
10000 P=1:FORG=2TO1STEP0:P=P*2:G=INT(N/P):NW=N-G:PRINTG;
10010 FORQ=1TO0STEP0:Q=0:FORI=1TONW
10020 IFA$(B(I))>A$(B(I+G))THENT=B(I):B(I)=B(I+G):B(I+G)=T:Q=I
10030 NEXT:IFQ>0THENNW=Q
10040 NEXT:NEXT:RETURN
'1000 MOST POPULAR SIR NAMES FROM MOST TO LEAST POPULAR
100 DATA SMITH,2501922,1.006,1,JOHNSON,2014470,.81,2,WILLIAMS,1738413,.699,3
101 DATA JONES,1544427,.621,4,BROWN,1544427,.621,5,DAVIS,1193760,.48,6
...
1000 DATA "",0,0,0 :REM END OF DATA MARKER
The data came from this page
ReplyDeletehttps://names.mongabay.com/most_common_surnames.htm
FWIW, this is also a good example of how to implement a DO loop using FOR NEXT
ReplyDeleteThis code shows a mod to the sort that attempts to eliminate final passes at each gap level where no swaps will take place. The code is untested but I've posted it in case someone wants to experiment with it.
ReplyDeleteNote that this relies on the ELSE statement, and machines that do not support that will need an addition IF added.
10000 P=1:FORG=2TO1STEP0:P=P*2:G=INT(N/P):NW=N-G:PRINTG;
10010 FORQ=1TO0STEP0:Q=0:FORI=1TONW
'10010 FORQ=G-1TO0STEP-1:R=0:FORI=1TONW
10020 IFA$(B(I))>A$(B(I+G))THENT=B(I):B(I)=B(I+G):B(I+G)=T:Q=I
'10020 IFA$(B(I))>A$(B(I+G))THENT=B(I):B(I)=B(I+G):B(I+G)=T:R=I
10030 NEXT:IFQ>0THENNW=Q
'10030 NEXT:IFR>0THENNW=RELSEQ=0
10040 NEXT:NEXT:RETURN
That change doesn't work and I tried using a square of the value and that didn't even work, but multiplying P by 1.7 instead of 2 like with the comb sort definitely makes it faster.
DeleteAfter some tests, there isn't much point in optimizing this sort any further. It's okay for a bubble sort, but over 30% of all passes through the data were where no swaps were made, and calculating the maximum number of passes does not appear useful. Just setting the number to 3 or 4 might yield the best results, though it would not eliminate all the wasted passes through the data.
ReplyDeleteThis version using 1.5 instead of 2 in the gap calculation yielded the best results on my data:
10000 P=1:FORG=2TO1STEP0:P=P*1.5:G=INT(N/P):NW=N-G
10010 FORQ=1TO0STEP0:Q=0:FORI=1TONW
10020 IFA$(B(I))>A$(B(I+G))THENT=B(I):B(I)=B(I+G):B(I+G)=T:Q=I
10030 NEXT:IFQ>0THENNW=Q
10040 NEXT:NEXT:RETURN
After ditching the repeated passes at each gap level, I remember why I originally thought I had accidentally created a comb sort.
ReplyDeleteDividing the gap by 2 doesn't fully sort the data, so I used a bubble sort to finish sorting the data.
Once I tried to eliminate the redundant passes I remember the 2nd sort. I'm guessing I went through the same process back then and didn't realize I spent that much time on it.
Changing this code so the gap calculation uses 1.3 seems to finish the sort without the 2nd sort. So now I know where they got that value for the comb sort.
A little experiment in varying the value used to calculate the gap sped up the sort by reducing the number of passes.
It starts by dividing by 2 and works it's way to 1.3 a little at a time.
More swaps take place per pass, but that also means there are fewer wasted tests.
It will need further testing to see if it always works, and I need to figure out the ideal rate to adjust the gap divisor, but it could be promising... or a wast of time. :D
This seems to do the trick, but I can't be sure the value of H or this modification to the sort will work with all data. The gap is reduced towards 1.3 over the first 5 passes using this value for H.
ReplyDelete10000 P=1:F=2:H=.91
10001 P=P*F:G=INT(N/P):NW=N-G:PRINTG;:F=F*H:IFF<1.3THENF=1.3
10010 R=0:FORI=1TONW
10020 IFA$(B(I))>A$(B(I+G))THENT=B(I):B(I)=B(I+G):B(I+G)=T
10030 NEXT
10040 IFG>0THEN10001
10050 RETURN
After testing this and performing benchmarks on it... it saved 10 seconds on an array that fills most of memory and takes several minutes to sort. Yeah, it's faster, but not really worth the effort.
ReplyDeleteThis is the final version of the sort. Using the FOR NEXT loop to test for G is definitely faster than an IF THEN (GOTO)
ReplyDelete10000 P=1:F=1.3
10001 FORG=1TO0STEP0:P=P*F:G=INT(N/P):NW=N-G:PRINTG;
10010 R=0:FORI=1TONW
10020 IFA$(B(I))>A$(B(I+G))THENT=B(I):B(I)=B(I+G):B(I+G)=T
10030 NEXT
10040 NEXT
10050 RETURN