Basic Speedup Tip

[Mike]

This is a good place to point out, that no fiddling with variable names, or their order of declaration can rescue an otherwise bad algorithm.

A good example are sorting algorithms. Bubble-Sort, while easily implemented (I can write that routine down straight from memory) is a bad algorithm - such that it really should be forbidden to teach it to those new to programming. I just use it here, to state the point, to compare it with Quick-Sort.

Quick-Sort is more complicated to program. I confess I always have to look it up in a book, when I need to implement it myself. Luckily C has a built-in Quick-Sort.

First comes the example. Replace GOSUB 50 in line 13 with GOSUB 20 to test Bubble-Sort instead of Quick-Sort. N is specified in line 11.

Greetings,

Michael


I use the variant of Quick-Sort, that sorts the smallest sub-array first. This minimizes stack usage. DIMS(31) is enough to sort up to 65535 elements.

Quick-Sort also works with String-Arrays (use A$(), A$, and X$ instead). If you want to sort other arrays alongside A(), place the additional swap operation(s) between lines 55 and 56.

Code: Select all

10 DIMS(31):SP=0:REM ** STACK FOR QUICK-SORT
11 N=10:DIMA(N)
12 FORT=0TON:A(T)=RND(1):NEXT
13 T1=TI:L=0:R=N:GOSUB50:T2=TI
14 FORT=0TON:PRINTA(T):NEXT
15 PRINTT2-T1
16 END
18 :
19 REM ** BUBBLE-SORT
20 IFR<=LTHENRETURN
21 F=0:FORT=LTOR-1:IFA(T)>A(T+1)THENA=A(T):A(T)=A(T+1):A(T+1)=A:F=1
22 NEXT:IFFTHEN21
23 RETURN
29 :
49 REM ** QUICK-SORT
50 IFR<=LTHENRETURN
51 I=L:J=R:X=A((L+R)/2)
52 IFA(I)<XTHENI=I+1:GOTO52
53 IFA(J)>XTHENJ=J-1:GOTO53
54 IFI>JTHEN57
55 A=A(I):A(I)=A(J):A(J)=A
56 I=I+1:J=J-1
57 IFI<=JTHEN52
58 IFJ-L<R-ITHENS(SP)=I:S(SP+1)=R:SP=SP+2:R=J:GOSUB50:GOTO60
59 S(SP)=L:S(SP+1)=J:SP=SP+2:L=I:GOSUB50
60 SP=SP-2:L=S(SP):R=S(SP+1):GOTO50

You'll see, for N up to 10, they're roughly on par, Bubble-Sort may even be faster, but look, what happens for greater N:

These are the run times in clock ticks:

Code: Select all

Quick-Sort

   N  Run 1  Run 2  Run 3  Run 4  Run 5

  10     56     65     60     61     59
  30    230    221    231    211    207
 100    837    881    867    849    858
 300   3029   3169   3054   2969   2960
1000  12032  11954  11941  12553  12266


Bubble-Sort

   N  Run 1  Run 2  Run 3  Run 4  Run 5

  10     66     47     93     82     64
  30    563    501    684    633    627
 100   6268   6918   6837   7474   6622
 300  62476  57756  ... you get the idea
1000  not tried, expected time ~600000..700000 clock ticks.

[wimoos]

The list of (float, int, string) variables is also interspersed with hooks to the DEF FNxx( ) functions.

More specifically, the bits 7s of the variablename are a flag for the datatype.
For a float, they both are 0. For a string, only the second is 1. For int, they both are 1. For FN, only the first is 1.

The value that is kept for the FN is a pointer to the function in the BASIC program.

So when you're defining a lot of those in the beginning of your program and hardly using them, be sure to DIM variables first.