Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.sys.apple2.programmer > #2471 > unrolled thread
| Started by | wssimms@gmail.com |
|---|---|
| First post | 2016-03-10 07:34 -0800 |
| Last post | 2016-03-21 01:40 -0500 |
| Articles | 20 on this page of 55 — 9 participants |
Back to article view | Back to comp.sys.apple2.programmer
qsort for 65c02 wssimms@gmail.com - 2016-03-10 07:34 -0800
Re: qsort for 65c02 qkumba <peter.ferrie@gmail.com> - 2016-03-10 09:10 -0800
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-10 17:23 -0800
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-10 19:13 -0800
Re: qsort for 65c02 "Michael J. Mahon" <mjmahon@aol.com> - 2016-03-10 19:37 -0800
Re: qsort for 65c02 wssimms@gmail.com - 2016-03-10 21:37 -0800
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 12:43 -0800
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-11 15:48 -0600
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 20:59 -0800
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 21:13 -0800
Re: qsort for 65c02 wssimms@gmail.com - 2016-03-11 21:19 -0800
Re: qsort for 65c02 wssimms@gmail.com - 2016-03-12 07:15 -0800
Re: qsort for 65c02 wssimms@gmail.com - 2016-03-12 07:25 -0800
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-12 11:22 -0600
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-12 10:00 -0800
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-12 14:09 -0600
Re: qsort for 65c02 wssimms@gmail.com - 2016-03-12 22:17 -0800
Re: qsort for 65c02 Scott Hemphill <hemphill@hemphills.net> - 2016-03-13 09:03 -0400
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-13 09:22 -0700
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-13 13:45 -0500
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-13 19:01 -0700
Re: qsort for 65c02 wssimms@gmail.com - 2016-03-13 21:28 -0700
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-13 22:15 -0700
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-13 13:45 -0500
Re: qsort for 65c02 wssimms@gmail.com - 2016-03-13 15:46 -0700
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-11 03:30 -0800
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 13:25 -0800
Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-14 16:24 -0700
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 23:35 -0500
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-15 10:20 -0700
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-15 17:30 -0500
Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-15 13:35 -0700
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-15 20:15 -0700
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-15 20:23 -0700
Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-16 10:33 -0700
Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 08:50 -0700
Re: qsort for 65c02 David Schmidt <schmidtd@my-deja.com> - 2016-03-18 12:37 -0400
Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 10:04 -0700
Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-18 10:12 -0700
Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 10:33 -0700
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-18 13:01 -0500
Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 11:33 -0700
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-18 17:37 -0500
Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-20 10:52 -0700
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-20 13:42 -0500
Re: qsort for 65c02 D Finnigan <dog_cow@macgui.com> - 2016-03-20 19:05 +0000
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-20 15:37 -0500
Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-20 13:33 -0700
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-20 15:53 -0500
Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-20 18:40 -0700
Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-21 01:40 -0500
Page 1 of 3 [1] 2 3 Next page →
| From | wssimms@gmail.com |
|---|---|
| Date | 2016-03-10 07:34 -0800 |
| Subject | qsort for 65c02 |
| Message-ID | <21cdc87f-461c-4351-82d3-241a0c3689d4@googlegroups.com> |
Here is a version of qsort for 65c02. It isn't wholly mine, but rather
it is a translation of a PDP-11 assembler qsort with some modifications.
I put this together because I was interested in sorting speed after
thinking about sorting strings while considering the garbage collection
routines recently posted. This code almost certainly could be improved.
It is quite general and therefore gives up optimization opportunities
that a more task-specific sorting routine would permit. The interface
is quite similar to the C library function qsort().
I measured some sort times using Virtual ][ 7.5.2 at the 1Mhz speed
setting. The following are average elapsed time from beginning of
sort, to the beginning of printing of the results. In all cases, the total
array size was 8190 bytes, initialized with values obtained from the
Xorshift PRNG I posted a week or two ago:
1170 7-byte records, sorted on the first 2 bytes = 11s
1638 5-byte records, sorted on the first 2 bytes = 15s
2730 3-byte records, sorted on the first 2 bytes = 26s
4095 2-byte integers, sorted by value = 37s
By these numbers, the sort requires approximately 9 ms per element.
The qsort code follows. After that is the code for the test program:
xc
rel
dsk qsort.l
use /hd/merlin/himath
umul ext
udiv ext
spopw ext
spushw ext
ptr1 = $E2
ptr2 = $E4
*
* quicker sort
*
* ldx #<base
* ldy #>base
* jsr spushw
* ldx #<nelems
* ldy #>nelems
* jsr spushw
* ldx #<compare
* ldy #>compare
* lda #elem.width
* jsr qsort
*
* setup for qsort
qsort ent
sta width ;remember width
stx cmp1+1
stx cmp2+1 ;insert compare routine
sty cmp1+2
sty cmp2+2
jsr spopw
stx mplcand ;retrieve # elements
sty mplcand+1
jsr spopw
stx ptr1
sty ptr1+1
lda width
cmp #1 ;element width is 1?
bne :1a
:2a
clc
lda mplcand ;add nelems to the base ptr
adc ptr1 ;to build a ptr to the end
sta ptr2 ;of the array
lda mplcand+1
adc ptr1+1
sta ptr2+1
bra qs1
:1a
cmp #2 ;element width is 2?
bne :2b
asl mplcand ;multiply nelems by 2
rol mplcand+1
bra :2a
:2b
sta mplier ;multiply nelems by width to
stz mplier+1 ;get the total length of the array
jsr umul
clc
lda prod
adc ptr1 ;build a pointer to the end of the
sta ptr2 ;array in ptr2
lda prod+1
adc ptr1+1
sta ptr2+1
* sort the array between ptr1 and ptr2
qs1
sec
lda ptr2
sbc ptr1 ;find the length of the array in bytes
sta dvdnd0 ;if end ptr > base ptr then
lda ptr2+1 ;sort the array, otherwise return
sbc ptr1+1
sta dvdnd1
ora dvdnd0 ;ptr1 == ptr2 ?
bne :1a
rts
:1a
lda width
cmp #1
bne :1b
lsr dvdnd1 ;divide by two to get middle byte
ror dvdnd0
:2
lda dvdnd0
sta prod
lda dvdnd1
sta prod+1
bra :3a ;jump to build the pivot ptr
:1b
cmp #2
bne :1c
lsr dvdnd1
ror dvdnd0 ;divide by width to get nelems
lsr dvdnd1
ror dvdnd0 ;divide by two for middle elem index
asl dvdnd0
rol dvdnd1 ;multiply by two for middle elem offset
bra :2
:1c
sta dvsor0
stz dvsor1 ;for other widths, divide by the width
stz dvdnd2 ;to get the number of elements
stz dvdnd3
jsr udiv
lsr dvquo1 ;divide nelems by two to find the
ror dvquo0 ;index of the middle of the array
lda width
sta mplier
stz mplier+1 ;multiply the middle index by the
lda dvquo0 ;element width to get the offset of
sta mplcand ;the pivot element from the base ptr
lda dvquo1
sta mplcand+1
jsr umul
:3a
clc
lda prod
adc ptr1 ;build the pivot ptr
sta pivot
lda prod+1
adc ptr1+1
sta pivot+1
ldx ptr1
ldy ptr1+1 ;remember the base ptr
jsr spushw
ldx ptr2
ldy ptr2+1 ;remember the end ptr
jsr spushw
* scan up through the lower half of the array looking for an
* element that is greater than the pivot element
loop
lda ptr1+1
cmp pivot+1
bne :1a ;if ptr1 has reached pivot
lda ptr1 ;go scan backwards with ptr2
cmp pivot
beq loop1
:1a
ldx ptr1
ldy ptr1+1
jsr spushw
ldx pivot
ldy pivot+1 ;compare the element pointed to
jsr spushw ;by ptr1 to the element pointed to
cmp1 jsr $FFFF ;by pivot
beq :1a ;if *ptr1 > *pivot, *ptr1 should be
bcs loop1 ;swapped, go scan backwards with ptr2
:1a
clc
lda width
adc ptr1
sta ptr1
bcc loop ;otherwise advance ptr1 to the next element
inc ptr1+1
bra loop
* scan down through the upper half of the array looking for an
* element that is less than the pivot element
loop1
lda ptr2+1
cmp pivot+1 ;if ptr2 has reached pivot
bne :2a ;go see if ptr1 is also at pivot
lda ptr2
cmp pivot
beq ckptr1
:2a
sec
lda ptr2
sbc width ;decrement ptr2 to previous element
sta ptr2
tax
lda ptr2+1
sbc #0 ;compare the element pointed to
sta ptr2+1 ;by ptr2 to the element pointed to
tay ;by pivot
jsr spushw
ldx pivot
ldy pivot+1
jsr spushw
cmp2 jsr $FFFF
bcs loop1 ;continue loop if *ptr2 >= *pivot
* here both *ptr1 >= *pivot and *ptr2 <= *pivot
* exchange *ptr1 with *ptr2
jsr exchange
lda ptr1+1
cmp pivot+1
beq :2a
jmp loop ;if ptr1 has not yet advanced all
:2a ;the way to pivot, then scan
lda ptr1 ;some more
cmp pivot
beq :2b
jmp loop
:2b
lda ptr2
sta pivot ;if ptr1 is at pivot, then make
lda ptr2+1 ;ptr2 the pivot and scan some more
sta pivot+1
jmp loop
* here ptr2 has backed up so that ptr2 == pivot
ckptr1
lda ptr1+1
cmp pivot+1 ;see if ptr1 == pivot also
bne :2a
lda ptr1
cmp pivot
beq :1a
:2a
jsr exchange ;if not, exchange *ptr1 and *ptr2
lda ptr1
sta pivot ;copy ptr1 to pivot
lda ptr1+1
sta pivot+1
jmp loop1 ;and scan backwards some more with ptr2
* here all elements in the array have been swapped
* around the pivot
:1a
jsr spopw
stx ptr2 ;restore original ptr2 (end ptr)
sty ptr2+1
clc
lda width
adc pivot ;build new ptr1 which is the element
sta ptr1 ;after the pivot element
lda #0
adc pivot+1
sta ptr1+1
* now the array has been split in two: from original
* ptr1 to pivot and from new ptr1 (pivot+1) to ptr2
sec
lda ptr2
sbc ptr1
sta :h0+1 ;find length of the top half of array
lda ptr2+1
sbc ptr1+1
sta :h1+1
jsr spopw
stx :p0+1
sty :p1+1
jsr spushw ;retrieve and put back original ptr1
ldx pivot
ldy pivot+1 ;push the pivot so the stack contains
jsr spushw ;pointers to the bottom half of the array
sec
lda pivot
:p0 sbc #0
sta pivot
lda pivot+1 ;find the length of the bottom half of the array
:p1 sbc #0
sta pivot+1
:h1 lda #0
cmp pivot+1
bcc :1b ;if the length of the top half is
bne :2b ;less than the length of the bottom
:h0 lda #0 ;half, goto :1b to sort the top
cmp pivot ;half and then the bottom half
bcc :1b
* length of bottom half is less than length of top half, so
* swap the stacked pointers with ptr1 & ptr2 so as to first
* sort the bottom half and then the top half
:2b
jsr spopw ;retrieve end ptr of bottom half
stx :bp0+1
sty :bp1+1
jsr spopw ;retrieve base ptr of bottom half
lda ptr1 ;swap with base ptr to top half
stx ptr1 ;so that base ptr of bottom half
tax ;is now in ptr1
lda ptr1+1
sty ptr1+1
tay
jsr spushw ;push base ptr of top half
ldx ptr2
ldy ptr2+1
jsr spushw ;push end ptr of top half
:bp0 lda #0
sta ptr2
:bp1 lda #0 ;get end ptr of bottom half
sta ptr2+1 ;in ptr2
:1b
jsr qs1 ;sort the subarray between ptr1 and ptr2
jsr spopw
stx ptr2
sty ptr2+1
jsr spopw ;retrieve the ptrs to the other half
stx ptr1
sty ptr1+1
jmp qs1 ;sort the other half
* exchange two elements of the array
exchange
ldy width
dey
:1
lda (ptr1),y
tax
lda (ptr2),y
sta (ptr1),y
txa
sta (ptr2),y
dey
bpl :1
rts
pivot dw 0
width db 0
*
*
*
Now the code for the test program:
*
*
*
lst off
xc
rel
dsk qst.l
spopw ext
spushw ext
qsort ext
rand ext
rndnum ext
rndseed ext
printf ext
esiz = 2
vsiz = 4095*esiz
nelem = vsiz/esiz
try
jsr spopw
cpx #1
beq :1
jsr spopw
jsr spopw
stx :0+1
sty :0+2
ldx #0
:0
lda $FFFF,x
beq :1
sta rndseed,x
inx
cpx #8
bcc :0
:1
jsr mkrn
ldx #<gos
ldy #>gos
jsr spushw
jsr printf
jsr sortb
jsr showb
rts
gos asc 'GO!',0A00
cmpb
jsr spopw
stx :p2+1
sty :p2+2
jsr spopw
stx :p1+1
sty :p1+2
:p1 lda $FFFF
:p2 cmp $FFFF
rts
cmpw
jsr spopw
stx :p2+1
stx :p4+1
sty :p2+2
sty :p4+2
jsr spopw
stx :p1+1
stx :p3+1
sty :p1+2
sty :p3+2
ldx #1
:p1 lda $FFFF,x
:p2 cmp $FFFF,x
beq :p3
rts
:p3 lda $FFFF
:p4 cmp $FFFF
rts
sortb
ldx #<vec
ldy #>vec
jsr spushw
ldx #<nelem
ldy #>nelem
jsr spushw
ldx #<cmpw
ldy #>cmpw
lda #esiz
jsr qsort
rts
showb
stz idx
stz idx+1
:1
lda idx+1
cmp #>vsiz
bne :2
lda idx
cmp #<vsiz
bne :2
rts
:2
clc
lda idx
adc #<vec
sta :A+1
sta :B+1
lda idx+1
adc #>vec
sta :A+2
sta :B+2
ldx #1
:A lda $FFFF,x
tay
:B lda $FFFF
tax
jsr spushw
ldx #<bstrs
ldy #>bstrs
jsr spushw
jsr printf
clc
lda idx
adc #esiz
sta idx
bcc :1
inc idx+1
bra :1
bstrs asc '%l',0A00
idx dw 0
mkrn
lda #16
sta idx
:1
jsr rand
dec idx
bne :1
stz idx
stz idx+1
:2
lda idx+1
cmp #>vsiz
bne :3
lda idx
cmp #<vsiz
bne :3
rts
:3
clc
lda idx
adc #<vec
sta :0+1
lda idx+1
adc #>vec
sta :0+2
jsr rand
lda rndnum+6
:0 sta $FFFF
inc idx
bne :2
inc idx+1
bra :2
vec ds vsiz+esiz
[toc] | [next] | [standalone]
| From | qkumba <peter.ferrie@gmail.com> |
|---|---|
| Date | 2016-03-10 09:10 -0800 |
| Message-ID | <efd85e5f-5f60-41e1-9526-bc5b5a93d6ca@googlegroups.com> |
| In reply to | #2471 |
> This code almost certainly could be improved. > It is quite general and therefore gives up optimization opportunities > that a more task-specific sorting routine would permit. The interface > is quite similar to the C library function qsort(). There are places where it could be improved without resulting in specialization. For example, the "LDA width / CMP ..." could be "LDY width / DEY" instead to save a few bytes; the LSR/ROL of dvdnd could be combined in width 1 and 2. There are probably other things. I might take a closer look tomorrow, if no-one beats me to it.
[toc] | [prev] | [next] | [standalone]
| From | gids.rs@sasktel.net |
|---|---|
| Date | 2016-03-10 17:23 -0800 |
| Message-ID | <09f553ea-ec51-4742-a372-2ceb0bce4b8e@googlegroups.com> |
| In reply to | #2471 |
On Thursday, March 10, 2016 at 9:34:12 AM UTC-6, wss...@gmail.com wrote:
> Here is a version of qsort for 65c02. It isn't wholly mine, but rather
> it is a translation of a PDP-11 assembler qsort with some modifications.
>
> I put this together because I was interested in sorting speed after
> thinking about sorting strings while considering the garbage collection
> routines recently posted. This code almost certainly could be improved.
> It is quite general and therefore gives up optimization opportunities
> that a more task-specific sorting routine would permit. The interface
> is quite similar to the C library function qsort().
>
> I measured some sort times using Virtual ][ 7.5.2 at the 1Mhz speed
> setting. The following are average elapsed time from beginning of
> sort, to the beginning of printing of the results. In all cases, the total
> array size was 8190 bytes, initialized with values obtained from the
> Xorshift PRNG I posted a week or two ago:
>
> 1170 7-byte records, sorted on the first 2 bytes = 11s
> 1638 5-byte records, sorted on the first 2 bytes = 15s
> 2730 3-byte records, sorted on the first 2 bytes = 26s
> 4095 2-byte integers, sorted by value = 37s
>
> By these numbers, the sort requires approximately 9 ms per element.
> The qsort code follows. After that is the code for the test program:
>
For awhile, I thought the quicksort method was the fastest sort out there, compared the other known sorts around. I don't know where I got it from, but I had this scrap paper out of magazine that I had ripped out one time, that had an applesoft sorting routine on it.
I never thought about it much for years (how on earth I kept a scrap piece of paper around for years without garbaging or losing it is beyond me).
I finally entered it in and was pretty impressed with the speed, until I realized it only sorted on the first character of each name. Hardly a complete and working algorithm.
To complete it all I did was set up a linear search (a binary search would even speed this up even more, but a little more difficult to implement due to the way the sort works) and now it sorts on whole words.
The speed is still impressive. It can sort a random list of 500 words in 35 secs in applesoft. An applesoft version of quicksort using the same list of 500 words takes 1 min 30 secs.
That is about 65% faster than quicksort. I can't say for sure if one would get the same sort speed in ML over quicksort, but I think it would be worth it to get it converted to ML.
So here is a listing of my sort for you to play with. And a listing of applesoft quick-sort for comparison.
One last note, the smallest sort routine I was able to make was using bubble sort and only takes 144 bytes, fully usable, no external routines.
* UNKNOWN ROUTINE, SO I GAVE IT A NAME, I CALL IT ROBS-SORT :)
* FOR ALL UPPERCASE MAKE AM=65 : BM = 38
* TO INCLUDE ALL SYMBOLS, MAKE AM=96 : BM = 0
* FOR UPPER AND LOWER CASE MAKE, AM = 65 : BM = 6
* FOR ALL NUMBERS MAKE AM=48 : BM = 70
10 AM = 65:BM=38: GOSUB 200
20 FOR C = 1 TO N:A = ASC (A$(C)) - AM:P(C) = T(A):T(A) = C
30 IF NOT P(C) THEN NEXT : GOTO 80
40 P = P(C):L = P
50 IF A$(C) > A$(P) THEN T = P:P = P(P):FL = 1: ON P > 0 GOTO 50
60 IF FL THEN FL = NOT FL:P(C) = P:P(T) = C:T(A) = L
70 NEXT
80 FOR C = 0 TO 95: IF T(C) = 0 THEN 110
90 P = T(C)
100 FOR I = 1 TO N: IF P(P) THEN P = P(P): NEXT : GOTO 120
105 I = N: NEXT
110 P(P) = T(C + 1): NEXT
115 PRINT CHR$ (7)
120 X = 1:P = T(0): FOR I = 1 TO N: PRINT X" "A$(P),:P = P(P):X = X + 1:NEXT
199 END
200 N = 500: DIM A$(N),T(129-AM-BM+1),P(N): HOME
210 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I) + CHR$ ( INT ( RND (1) * (128-AM-BM)) + AM): NEXT : VTAB 1: PRINT I" ": NEXT
215 ?:?"GET OUT A STOPWATCH AND PRESS ANY KEY WHEN READY":?:GETA$
220 HOME : INVERSE : PRINT " SORTED LIST " CHR$ (7): NORMAL
230 RETURN
* QUICKSORT ROUTINE
5 GOSUB 1000: GOSUB 10: PRINT CHR$ (7): FOR I = 1 TO N: PRINT A$(I),: NEXT
: END
10 S = 0:F = 1:L = N
20 M$ = A$( INT ((L + F) / 2)):I = F:J = L
40 IF A$(I) < M$ THEN I = I + 1: GOTO 40
70 IF A$(J) > M$ THEN J = J - 1: GOTO 70
100 ON I > J GOTO 180: ON I = J GOTO 160
120 T$ = A$(I):A$(I) = A$(J):A$(J) = T$
160 I = I + 1:J = J - 1
170 ON I < = J GOTO 40
180 ON I > = L GOTO 250
190 F(S) = I:L(S) = L:S = S + 1
250 L = J: ON F < L GOTO 20: IF NOT S THEN RETURN
260 S = S - 1:F = F(S):L = L(S): GOTO 20
999 END
1000 N = 500: DIM A$(N),L(200),F(200),T(27),P(N): HOME
1010 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I)
+ CHR$ ( INT ( RND (1) * 26) + 65): NEXT : VTAB 1: PRINT I" ": NEXT
1015 ?:?"PRESS ANY KEY TO START":?:GETA$
1020 HOME : INVERSE : PRINT " SORTED LIST " CHR$ (7): NORMAL
1030 RETURN
[toc] | [prev] | [next] | [standalone]
| From | gids.rs@sasktel.net |
|---|---|
| Date | 2016-03-10 19:13 -0800 |
| Message-ID | <e39f8639-8401-440e-815c-cd8748aba505@googlegroups.com> |
| In reply to | #2475 |
> * QUICKSORT ROUTINE > > > 5 GOSUB 1000: GOSUB 10: PRINT CHR$ (7): FOR I = 1 TO N: PRINT A$(I),: NEXT > : END > 10 S = 0:F = 1:L = N > 20 M$ = A$( INT ((L + F) / 2)):I = F:J = L > 40 IF A$(I) < M$ THEN I = I + 1: GOTO 40 > 70 IF A$(J) > M$ THEN J = J - 1: GOTO 70 > 100 ON I > J GOTO 180: ON I = J GOTO 160 > 120 T$ = A$(I):A$(I) = A$(J):A$(J) = T$ > 160 I = I + 1:J = J - 1 > 170 ON I < = J GOTO 40 > 180 ON I > = L GOTO 250 > 190 F(S) = I:L(S) = L:S = S + 1 > 250 L = J: ON F < L GOTO 20: IF NOT S THEN RETURN > 260 S = S - 1:F = F(S):L = L(S): GOTO 20 > 999 END > 1000 N = 500: DIM A$(N),L(200),F(200),T(27),P(N): HOME > 1010 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I) > + CHR$ ( INT ( RND (1) * 26) + 65): NEXT : VTAB 1: PRINT I" ": NEXT > 1015 ?:?"PRESS ANY KEY TO START":?:GETA$ > 1020 HOME : INVERSE : PRINT " SORTED LIST " CHR$ (7): NORMAL > 1030 RETURN Some may think this quicksort routine is not very optimized due to all the GOTO's in it. I just want to mention that I have another quicksort routine with 3x FOR-NEXT loops and only 2x GOTO's, for 500 random words it takes 1 min and 45 secs. I believe this kind of proves that when GOTO's are used and the line numbers are close to the beginning of the program that, GOTO's are faster than FOR-NEXT loops.
[toc] | [prev] | [next] | [standalone]
| From | "Michael J. Mahon" <mjmahon@aol.com> |
|---|---|
| Date | 2016-03-10 19:37 -0800 |
| Message-ID | <L-mdnVR6VID0oH_LnZ2dnUU7-bvNnZ2d@giganews.com> |
| In reply to | #2475 |
On 3/10/2016 5:23 PM, gids.rs@sasktel.net wrote: > On Thursday, March 10, 2016 at 9:34:12 AM UTC-6, wss...@gmail.com wrote: >> Here is a version of qsort for 65c02. It isn't wholly mine, but rather >> it is a translation of a PDP-11 assembler qsort with some modifications. >> >> I put this together because I was interested in sorting speed after >> thinking about sorting strings while considering the garbage collection >> routines recently posted. This code almost certainly could be improved. >> It is quite general and therefore gives up optimization opportunities >> that a more task-specific sorting routine would permit. The interface >> is quite similar to the C library function qsort(). >> >> I measured some sort times using Virtual ][ 7.5.2 at the 1Mhz speed >> setting. The following are average elapsed time from beginning of >> sort, to the beginning of printing of the results. In all cases, the total >> array size was 8190 bytes, initialized with values obtained from the >> Xorshift PRNG I posted a week or two ago: >> >> 1170 7-byte records, sorted on the first 2 bytes = 11s >> 1638 5-byte records, sorted on the first 2 bytes = 15s >> 2730 3-byte records, sorted on the first 2 bytes = 26s >> 4095 2-byte integers, sorted by value = 37s >> >> By these numbers, the sort requires approximately 9 ms per element. >> The qsort code follows. After that is the code for the test program: >> > > > For awhile, I thought the quicksort method was the fastest sort out there, compared the other known sorts around. I don't know where I got it from, but I had this scrap paper out of magazine that I had ripped out one time, that had an applesoft sorting routine on it. > > I never thought about it much for years (how on earth I kept a scrap piece of paper around for years without garbaging or losing it is beyond me). > > I finally entered it in and was pretty impressed with the speed, until I realized it only sorted on the first character of each name. Hardly a complete and working algorithm. > > To complete it all I did was set up a linear search (a binary search would even speed this up even more, but a little more difficult to implement due to the way the sort works) and now it sorts on whole words. > > The speed is still impressive. It can sort a random list of 500 words in 35 secs in applesoft. An applesoft version of quicksort using the same list of 500 words takes 1 min 30 secs. > > That is about 65% faster than quicksort. I can't say for sure if one would get the same sort speed in ML over quicksort, but I think it would be worth it to get it converted to ML. > > So here is a listing of my sort for you to play with. And a listing of applesoft quick-sort for comparison. > > One last note, the smallest sort routine I was able to make was using bubble sort and only takes 144 bytes, fully usable, no external routines. > > > * UNKNOWN ROUTINE, SO I GAVE IT A NAME, I CALL IT ROBS-SORT :) > * FOR ALL UPPERCASE MAKE AM=65 : BM = 38 > * TO INCLUDE ALL SYMBOLS, MAKE AM=96 : BM = 0 > * FOR UPPER AND LOWER CASE MAKE, AM = 65 : BM = 6 > * FOR ALL NUMBERS MAKE AM=48 : BM = 70 > > 10 AM = 65:BM=38: GOSUB 200 > 20 FOR C = 1 TO N:A = ASC (A$(C)) - AM:P(C) = T(A):T(A) = C > 30 IF NOT P(C) THEN NEXT : GOTO 80 > 40 P = P(C):L = P > 50 IF A$(C) > A$(P) THEN T = P:P = P(P):FL = 1: ON P > 0 GOTO 50 > 60 IF FL THEN FL = NOT FL:P(C) = P:P(T) = C:T(A) = L > 70 NEXT > 80 FOR C = 0 TO 95: IF T(C) = 0 THEN 110 > 90 P = T(C) > 100 FOR I = 1 TO N: IF P(P) THEN P = P(P): NEXT : GOTO 120 > 105 I = N: NEXT > 110 P(P) = T(C + 1): NEXT > 115 PRINT CHR$ (7) > 120 X = 1:P = T(0): FOR I = 1 TO N: PRINT X" "A$(P),:P = P(P):X = X + 1:NEXT > 199 END > > 200 N = 500: DIM A$(N),T(129-AM-BM+1),P(N): HOME > 210 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I) + CHR$ ( INT ( RND (1) * (128-AM-BM)) + AM): NEXT : VTAB 1: PRINT I" ": NEXT > 215 ?:?"GET OUT A STOPWATCH AND PRESS ANY KEY WHEN READY":?:GETA$ > 220 HOME : INVERSE : PRINT " SORTED LIST " CHR$ (7): NORMAL > 230 RETURN This algorithm is a radix (or "bucket") sort, doing only one pass on the most significant character of the A$() strings, and therefore incompletely sorting them. Normally a radix sort would do as many passes over the key array as there are characters in the array. Successive iterations of the radix sort operate in least significant to most significant order, with the "buckets" stacked (as in 100-110) between passes. This is the algorithm used in the punched card era to sort decks of punched cards using a card sorter. The algorithm performs K passes (where K = number of "key" characters), each N iterations long (where N = number of records). For a given key length, the execution time is essentially linear in N, and although each character of each key is "examined", no key characters are ever "compared". Instead, the numeric equivalence of each character is used to distribute the records into K "buckets" which are then "stacked in order" between passes. The linked radix sort is quite useful, since it has almost unity storage ratio (it doesn't require additional storage proportional to N) and its execution time is independent of the distribution of key values. Since it is desirable to keep K << N (to conserve storage and minimize the occurrence of empty buckets), in Applesoft it is most useful for strings. In machine language, bytes are a natural radix for either alphabetic or numeric data. -- -michael NadaNet 3.1 for Apple II parallel computing! Home page: http://michaeljmahon.com "The wastebasket is our most important design tool--and it's seriously underused."
[toc] | [prev] | [next] | [standalone]
| From | wssimms@gmail.com |
|---|---|
| Date | 2016-03-10 21:37 -0800 |
| Message-ID | <56b96c23-bb76-4018-a32f-a86ee8b5691f@googlegroups.com> |
| In reply to | #2477 |
On Friday, March 11, 2016 at 12:37:14 PM UTC+9, mjm...@aol.com wrote: > On 3/10/2016 5:23 PM, gids.rs@sasktel.net wrote: > > > > * UNKNOWN ROUTINE, SO I GAVE IT A NAME, I CALL IT ROBS-SORT :) > > * FOR ALL UPPERCASE MAKE AM=65 : BM = 38 > > * TO INCLUDE ALL SYMBOLS, MAKE AM=96 : BM = 0 > > * FOR UPPER AND LOWER CASE MAKE, AM = 65 : BM = 6 > > * FOR ALL NUMBERS MAKE AM=48 : BM = 70 > > > > 10 AM = 65:BM=38: GOSUB 200 > > 20 FOR C = 1 TO N:A = ASC (A$(C)) - AM:P(C) = T(A):T(A) = C > > 30 IF NOT P(C) THEN NEXT : GOTO 80 > > 40 P = P(C):L = P > > 50 IF A$(C) > A$(P) THEN T = P:P = P(P):FL = 1: ON P > 0 GOTO 50 > > 60 IF FL THEN FL = NOT FL:P(C) = P:P(T) = C:T(A) = L > > 70 NEXT > > 80 FOR C = 0 TO 95: IF T(C) = 0 THEN 110 > > 90 P = T(C) > > 100 FOR I = 1 TO N: IF P(P) THEN P = P(P): NEXT : GOTO 120 > > 105 I = N: NEXT > > 110 P(P) = T(C + 1): NEXT > > 115 PRINT CHR$ (7) > > 120 X = 1:P = T(0): FOR I = 1 TO N: PRINT X" "A$(P),:P = P(P):X = X + 1:NEXT > > 199 END > > > > 200 N = 500: DIM A$(N),T(129-AM-BM+1),P(N): HOME > > 210 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I) + CHR$ ( INT ( RND (1) * (128-AM-BM)) + AM): NEXT : VTAB 1: PRINT I" ": NEXT > > 215 ?:?"GET OUT A STOPWATCH AND PRESS ANY KEY WHEN READY":?:GETA$ > > 220 HOME : INVERSE : PRINT " SORTED LIST " CHR$ (7): NORMAL > > 230 RETURN > > This algorithm is a radix (or "bucket") sort, doing only one pass on the > most significant character of the A$() strings, and therefore > incompletely sorting them. > It has been a long time since I have done much AppleSoft BASIC and so reading this kind of makes my head hurt but it looks like this code is building linked lists of strings that have the same initial character. Then, each time a new string is added to a list, lines 40-70 search through the list and move the newest string to the correct place using AppleSoft string compare to compare the new string to the other strings in the list.
[toc] | [prev] | [next] | [standalone]
| From | gids.rs@sasktel.net |
|---|---|
| Date | 2016-03-11 12:43 -0800 |
| Message-ID | <1a698500-b4e6-4ef5-b545-9ed4730486c6@googlegroups.com> |
| In reply to | #2478 |
On Thursday, March 10, 2016 at 11:37:14 PM UTC-6, wes wrote: > On Friday, March 11, 2016 at 12:37:14 PM UTC+9, micahel wrote: > > On 3/10/2016 5:23 PM, Rob wrote: > > > > > > * UNKNOWN ROUTINE, SO I GAVE IT A NAME, I CALL IT ROBS-SORT :) > > > * FOR ALL UPPERCASE MAKE AM=65 : BM = 38 > > > * TO INCLUDE ALL SYMBOLS, MAKE AM=96 : BM = 0 > > > * FOR UPPER AND LOWER CASE MAKE, AM = 65 : BM = 6 > > > * FOR ALL NUMBERS MAKE AM=48 : BM = 70 > > > > > > 10 AM = 65:BM=38: GOSUB 200 > > > 20 FOR C = 1 TO N:A = ASC (A$(C)) - AM:P(C) = T(A):T(A) = C > > > 30 IF NOT P(C) THEN NEXT : GOTO 80 > > > 40 P = P(C):L = P > > > 50 IF A$(C) > A$(P) THEN T = P:P = P(P):FL = 1: ON P > 0 GOTO 50 > > > 60 IF FL THEN FL = NOT FL:P(C) = P:P(T) = C:T(A) = L > > > 70 NEXT > > > 80 FOR C = 0 TO 95: IF T(C) = 0 THEN 110 > > > 90 P = T(C) > > > 100 FOR I = 1 TO N: IF P(P) THEN P = P(P): NEXT : GOTO 120 > > > 105 I = N: NEXT > > > 110 P(P) = T(C + 1): NEXT > > > 115 PRINT CHR$ (7) > > > 120 X = 1:P = T(0): FOR I = 1 TO N: PRINT X" "A$(P),:P = P(P):X = X + 1:NEXT > > > 199 END > > > > > > 200 N = 500: DIM A$(N),T(129-AM-BM+1),P(N): HOME > > > 210 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I) + CHR$ ( INT ( RND (1) * (128-AM-BM)) + AM): NEXT : VTAB 1: PRINT I" ": NEXT > > > 215 ?:?"GET OUT A STOPWATCH AND PRESS ANY KEY WHEN READY":?:GETA$ > > > 220 HOME : INVERSE : PRINT " SORTED LIST " CHR$ (7): NORMAL > > > 230 RETURN > > > > This algorithm is a radix (or "bucket") sort, doing only one pass on the > > most significant character of the A$() strings, and therefore > > incompletely sorting them. > > > > It has been a long time since I have done much AppleSoft BASIC and so reading this kind of makes my head hurt but it looks like this code is building linked lists of strings that have the same initial character. Then, each time a new string is added to a list, lines 40-70 search through the list and move the newest string to the correct place using AppleSoft string compare to compare the new string to the other strings in the list. Lines 40-60 is the linear search that I added so that it would sort by the whole word. What makes even the linear search so fast is, that it does not have to move the entire list up to make room for that one word. It only has to move the list that is in that category. So basically, 1/26 (if only using uppercase) of the whole list. This is where I believe this routine offers the significant speed increase over quick-sort.
[toc] | [prev] | [next] | [standalone]
| From | Michael J. Mahon <mjmahon@aol.com> |
|---|---|
| Date | 2016-03-11 15:48 -0600 |
| Message-ID | <WsSdnQ15NeS8oH7LnZ2dnUU7-dXNnZ2d@giganews.com> |
| In reply to | #2483 |
<gids.rs@sasktel.net> wrote: > On Thursday, March 10, 2016 at 11:37:14 PM UTC-6, wes wrote: >> On Friday, March 11, 2016 at 12:37:14 PM UTC+9, micahel wrote: >>> On 3/10/2016 5:23 PM, Rob wrote: >>>> >>>> * UNKNOWN ROUTINE, SO I GAVE IT A NAME, I CALL IT ROBS-SORT :) >>>> * FOR ALL UPPERCASE MAKE AMe : BM = 38 >>>> * TO INCLUDE ALL SYMBOLS, MAKE AM : BM = 0 >>>> * FOR UPPER AND LOWER CASE MAKE, AM = 65 : BM = 6 >>>> * FOR ALL NUMBERS MAKE AMH : BM = 70 >>>> >>>> 10 AM = 65:BM8: GOSUB 200 >>>> 20 FOR C = 1 TO N:A = ASC (A$(C)) - AM:P(C) = T(A):T(A) = C >>>> 30 IF NOT P(C) THEN NEXT : GOTO 80 >>>> 40 P = P(C):L = P >>>> 50 IF A$(C) > A$(P) THEN T = P:P = P(P):FL = 1: ON P > 0 GOTO 50 >>>> 60 IF FL THEN FL = NOT FL:P(C) = P:P(T) = C:T(A) = L >>>> 70 NEXT >>>> 80 FOR C = 0 TO 95: IF T(C) = 0 THEN 110 >>>> 90 P = T(C) >>>> 100 FOR I = 1 TO N: IF P(P) THEN P = P(P): NEXT : GOTO 120 >>>> 105 I = N: NEXT >>>> 110 P(P) = T(C + 1): NEXT >>>> 115 PRINT CHR$ (7) >>>> 120 X = 1:P = T(0): FOR I = 1 TO N: PRINT X" "A$(P),:P = P(P):X = X + 1:NEXT >>>> 199 END >>>> >>>> 200 N = 500: DIM A$(N),T(129-AM-BM+1),P(N): HOME >>>> 210 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = >>>> A$(I) + CHR$ ( INT ( RND (1) * (128-AM-BM)) + AM): NEXT : VTAB 1: PRINT I" ": NEXT >>>> 215 ?:?"GET OUT A STOPWATCH AND PRESS ANY KEY WHEN READY":?:GETA$ >>>> 220 HOME : INVERSE : PRINT " SORTED LIST " CHR$ (7): NORMAL >>>> 230 RETURN >>> >>> This algorithm is a radix (or "bucket") sort, doing only one pass on the >>> most significant character of the A$() strings, and therefore >>> incompletely sorting them. >>> >> >> It has been a long time since I have done much AppleSoft BASIC and so >> reading this kind of makes my head hurt but it looks like this code is >> building linked lists of strings that have the same initial character. >> Then, each time a new string is added to a list, lines 40-70 search >> through the list and move the newest string to the correct place using >> AppleSoft string compare to compare the new string to the other strings in the list. > > > > Lines 40-60 is the linear search that I added so that it would sort by > the whole word. What makes even the linear search so fast is, that it > does not have to move the entire list up to make room for that one word. > It only has to move the list that is in that category. So basically, > 1/26 (if only using uppercase) of the whole list. This is where I > believe this routine offers the significant speed increase over quick-sort. > > So, a radix sort on the first character followed by an insertion sort on the remainder of the key. As you point out, even a linear search for the insertion sort, an N squared sort, is pretty reasonable since the initial radix distribution phase limits the size of each bucket to N/Radix if the keys are uniformly distributed. Unfortunately, if the key values are clumped, it degenerates into a linear insertion sort. For example, if 500 keys are uniformly distributed, the time will be proportional to N (for the main radix distribution) times 1/2 (N/R)^2 (for the linear insertion phase. If the 500 keys all begin with, say, "B", then the time is proportional to N^2, since all keys are in the same bucket. The advantage of a pure radix sort is that it requires time proportional to N for all distributions of key values. Just for context, any sequential sort will require time between O(N) and O(N^2). All the "simple" sorts, like linear insertion and bubble sort, are O(N^2), while most "treelike" sorts, like quicksort or heap sort, are O(NlogN). It is remarkable for a sort to execute in O(N) time. To do so with essentially unity storage ratio is a bonus. -- -michael - NadaNet 3.1 and AppleCrate II: http://michaeljmahon.com
[toc] | [prev] | [next] | [standalone]
| From | gids.rs@sasktel.net |
|---|---|
| Date | 2016-03-11 20:59 -0800 |
| Message-ID | <d71bead2-2706-4dd7-a876-5df2bd8a7035@googlegroups.com> |
| In reply to | #2486 |
On Friday, March 11, 2016 at 3:48:18 PM UTC-6, Michael wrote: > <Rob> wrote: > > On Thursday, March 10, 2016 at 11:37:14 PM UTC-6, wes wrote: > >> On Friday, March 11, 2016 at 12:37:14 PM UTC+9, micahel wrote: > >>> On 3/10/2016 5:23 PM, Rob wrote: > >>>> > >>>> * UNKNOWN ROUTINE, SO I GAVE IT A NAME, I CALL IT ROBS-SORT :) > >>>> * FOR ALL UPPERCASE MAKE AMe : BM = 38 > >>>> * TO INCLUDE ALL SYMBOLS, MAKE AM- : BM = 0 > >>>> * FOR UPPER AND LOWER CASE MAKE, AM = 65 : BM = 6 > >>>> * FOR ALL NUMBERS MAKE AMH : BM = 70 > >>>> > >>>> 10 AM = 65:BM8: GOSUB 200 > >>>> 20 FOR C = 1 TO N:A = ASC (A$(C)) - AM:P(C) = T(A):T(A) = C > >>>> 30 IF NOT P(C) THEN NEXT : GOTO 80 > >>>> 40 P = P(C):L = P > >>>> 50 IF A$(C) > A$(P) THEN T = P:P = P(P):FL = 1: ON P > 0 GOTO 50 > >>>> 60 IF FL THEN FL = NOT FL:P(C) = P:P(T) = C:T(A) = L > >>>> 70 NEXT > >>>> 80 FOR C = 0 TO 95: IF T(C) = 0 THEN 110 > >>>> 90 P = T(C) > >>>> 100 FOR I = 1 TO N: IF P(P) THEN P = P(P): NEXT : GOTO 120 > >>>> 105 I = N: NEXT > >>>> 110 P(P) = T(C + 1): NEXT > >>>> 115 PRINT CHR$ (7) > >>>> 120 X = 1:P = T(0): FOR I = 1 TO N: PRINT X" "A$(P),:P = P(P):X = X + 1:NEXT > >>>> 199 END > >>>> > >>>> 200 N = 500: DIM A$(N),T(129-AM-BM+1),P(N): HOME > >>>> 210 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = > >>>> A$(I) + CHR$ ( INT ( RND (1) * (128-AM-BM)) + AM): NEXT : VTAB 1: PRINT I" ": NEXT > >>>> 215 ?:?"GET OUT A STOPWATCH AND PRESS ANY KEY WHEN READY":?:GETA$ > >>>> 220 HOME : INVERSE : PRINT " SORTED LIST " CHR$ (7): NORMAL > >>>> 230 RETURN > >>> > >>> This algorithm is a radix (or "bucket") sort, doing only one pass on the > >>> most significant character of the A$() strings, and therefore > >>> incompletely sorting them. > >>> > >> > >> It has been a long time since I have done much AppleSoft BASIC and so > >> reading this kind of makes my head hurt but it looks like this code is > >> building linked lists of strings that have the same initial character. > >> Then, each time a new string is added to a list, lines 40-70 search > >> through the list and move the newest string to the correct place using > >> AppleSoft string compare to compare the new string to the other strings in the list. > > > > > > > > Lines 40-60 is the linear search that I added so that it would sort by > > the whole word. What makes even the linear search so fast is, that it > > does not have to move the entire list up to make room for that one word. > > It only has to move the list that is in that category. So basically, > > 1/26 (if only using uppercase) of the whole list. This is where I > > believe this routine offers the significant speed increase over quick-sort. > > > > > > So, a radix sort on the first character followed by an insertion sort on > the remainder of the key. > > As you point out, even a linear search for the insertion sort, an N squared > sort, is pretty reasonable since the initial radix distribution phase > limits the size of each bucket to N/Radix if the keys are uniformly > distributed. Unfortunately, if the key values are clumped, it degenerates > into a linear insertion sort. > > For example, if 500 keys are uniformly distributed, the time will be > proportional to N (for the main radix distribution) times 1/2 (N/R)^2 (for > the linear insertion phase. > > If the 500 keys all begin with, say, "B", then the time is proportional to > N^2, since all keys are in the same bucket. > > The advantage of a pure radix sort is that it requires time proportional to > N for all distributions of key values. > > Just for context, any sequential sort will require time between O(N) and > O(N^2). All the "simple" sorts, like linear insertion and bubble sort, are > O(N^2), while most "treelike" sorts, like quicksort or heap sort, are > O(NlogN). It is remarkable for a sort to execute in O(N) time. To do so > with essentially unity storage ratio is a bonus. > -- . I think I may have described that wrong. It is not a true insertion sort as per se, as an insertion requires the words at the end of the list to be moved up to make room for the one word. Instead, it is just a linear search to find the point of insertion and it just uses the same hashing algorithm that the radix sort uses which is a lot faster than the actual insertion sort.
[toc] | [prev] | [next] | [standalone]
| From | gids.rs@sasktel.net |
|---|---|
| Date | 2016-03-11 21:13 -0800 |
| Message-ID | <aa5cb096-162d-4117-8e97-26998076b5ed@googlegroups.com> |
| In reply to | #2489 |
> > I think I may have described that wrong. It is not a true insertion sort as per se, as an insertion requires the words at the end of the list to be moved up to make room for the one word. > > Instead, it is just a linear search to find the point of insertion and it just uses the same hashing algorithm that the radix sort uses which is a lot faster than the actual insertion sort. Once the linear search finds the point of insertion, only two pointers (or variables) are manipulated. The previous word's pointer to this new word, and this new word's pointer to the next word in line. The nice thing about this sort as well, is that the original list is untouched.
[toc] | [prev] | [next] | [standalone]
| From | wssimms@gmail.com |
|---|---|
| Date | 2016-03-11 21:19 -0800 |
| Message-ID | <abd5e73a-1ed5-4bd1-b81e-8da865eb97f1@googlegroups.com> |
| In reply to | #2490 |
It's an insertion sort where the to-be-sorted collection is a linked list. I'm still not 100% comfortable that I understand the code, but it looks like it goes through and connects all of the linked lists into one giant linked list before it prints the results. If I have understood that correctly it is of course unnecessary to do so.
[toc] | [prev] | [next] | [standalone]
| From | wssimms@gmail.com |
|---|---|
| Date | 2016-03-12 07:15 -0800 |
| Message-ID | <59ac624e-a9ba-4d4a-8939-cbefd6ec37bf@googlegroups.com> |
| In reply to | #2483 |
On Saturday, March 12, 2016 at 5:43:14 AM UTC+9, gid...@sasktel.net wrote:
> >
> >
> > It has been a long time since I have done much AppleSoft BASIC and so reading this kind of makes my head hurt but it looks like this code is building linked lists of strings that have the same initial character. Then, each time a new string is added to a list, lines 40-70 search through the list and move the newest string to the correct place using AppleSoft string compare to compare the new string to the other strings in the list.
>
> Lines 40-60 is the linear search that I added so that it would sort by the whole word. What makes even the linear search so fast is, that it does not have to move the entire list up to make room for that one word. It only has to move the list that is in that category. So basically, 1/26 (if only using uppercase) of the whole list. This is where I believe this routine offers the significant speed increase over quick-sort.
I've been able to spend a little bit of time on this today.
First I modified your sort routine to keep, in addition to the array T(), an array E(), that stores the indices of the last elements in each of the linked lists, so that the lists could be easily joined without digging through each of them to find the last element. This turned out to save only about 3-5 seconds when sorting 500 strings, so it may not be worth it to you.
Second, I was not able to get any 35 second sorting times using your code. Running on Virtual II at the 1Mhz setting, the sort time for 500 random strings was consistently over 1 minute. More on that below.
Third, I did not try the quicksort code you posted. Instead I wrote my own code using the same algorithm as the assembly code I posted. Here is it (more commentary below):
10 FM = 65:LM = 90: GOSUB 2000
20 GOSUB 100
30 GOTO 1000
100 B = 1:E = N + 1
105 IF E = B THEN RETURN
110 I = B:J = E:P = INT ((B + E) / 2)
120 IF I = P THEN 200
130 IF A$(I) > A$(P) THEN 200
140 I = I + 1: GOTO 120
200 IF J = P THEN 300
210 J = J - 1: IF A$(J) > = A$(P) THEN 200
220 T$ = A$(J):A$(J) = A$(I):A$(I) = T$: IF I < P THEN 130
240 P = J: GOTO 130
300 IF I = P THEN 400
310 T$ = A$(J):A$(J) = A$(I):A$(I) = T$:P = I: GOTO 210
400 SL = P - B:SH = E - P - 1: IF SL < SH THEN H(Q) = P + 1:E(Q) = E:E =
P: GOTO 500
420 H(Q) = B:E(Q) = P:B = P + 1
500 Q = Q + 1: GOSUB 105
510 Q = Q - 1:B = H(Q):E = E(Q): GOTO 105
1000 FOR X = 1 TO N: PRINT X" "A$(X),: NEXT X
1990 END
2000 N = 500
2005 DIM A$(N),H(LM - FM + 1),E(LM - FM + 1),P(N): HOME
2010 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I)
+ CHR$ ( INT ( RND (1) * (LM - FM + 1)) + FM): NEXT : VTAB 1: PRINT
I" ": NEXT
2020 PRINT : PRINT "Get out a stopwatch and press any key when ready": PRINT
: GET A$
2030 HOME : INVERSE : PRINT " Sorted List " CHR$ (7): NORMAL
2040 RETURN
Lastly I did some comparisons between your radix-insertion sort and this quicker sort code. I suspected that as the number of items to be sorted increased, qsort would compare better. That turned out to be the case. Here are the numbers:
N=500
Robs-Sort average time: 1:11
qsort average time: 2:15
ratio rs/qs: 0.526
N=1000
Robs-Sort average time: 3:40
qsort average time: 4:55
ratio rs/qs: 0.746
N=2000
Robs-Sort average time: 13:16
qsort average time: 11:42
ration rs/qs: 1.137
[toc] | [prev] | [next] | [standalone]
| From | wssimms@gmail.com |
|---|---|
| Date | 2016-03-12 07:25 -0800 |
| Message-ID | <9458af3c-1392-4264-81c9-36611eaac181@googlegroups.com> |
| In reply to | #2492 |
On Sunday, March 13, 2016 at 12:15:16 AM UTC+9, wss...@gmail.com wrote: > > 2005 DIM A$(N),H(LM - FM + 1),E(LM - FM + 1),P(N): HOME > Maybe I should point out that these DIMs are mostly nonsensical for the qsort code. The A$() array is necessary as it is the array of strings to be sorted. The H() and E() arrays are used as the stack for qsort so they are necessary, but their sizes are left over from the radix-insertion sort. they actually only need to be about log2 of N in length, so maybe 16-element (to be safe) T() and E() array are about right. P() is simply an unused leftover of the radix-insertion sort.
[toc] | [prev] | [next] | [standalone]
| From | Michael J. Mahon <mjmahon@aol.com> |
|---|---|
| Date | 2016-03-12 11:22 -0600 |
| Message-ID | <OqKdnX6W9qrQzXnLnZ2dnUU7-I3NnZ2d@giganews.com> |
| In reply to | #2492 |
<wssimms@gmail.com> wrote: > On Saturday, March 12, 2016 at 5:43:14 AM UTC+9, gid...@sasktel.net wrote: >>> >>> >>> It has been a long time since I have done much AppleSoft BASIC and so >>> reading this kind of makes my head hurt but it looks like this code is >>> building linked lists of strings that have the same initial character. >>> Then, each time a new string is added to a list, lines 40-70 search >>> through the list and move the newest string to the correct place using >>> AppleSoft string compare to compare the new string to the other strings in the list. >> >> Lines 40-60 is the linear search that I added so that it would sort by >> the whole word. What makes even the linear search so fast is, that it >> does not have to move the entire list up to make room for that one word. >> It only has to move the list that is in that category. So basically, >> 1/26 (if only using uppercase) of the whole list. This is where I >> believe this routine offers the significant speed increase over quick-sort. > > I've been able to spend a little bit of time on this today. > > First I modified your sort routine to keep, in addition to the array T(), > an array E(), that stores the indices of the last elements in each of the > linked lists, so that the lists could be easily joined without digging > through each of them to find the last element. This turned out to save > only about 3-5 seconds when sorting 500 strings, so it may not be worth it to you. > > Second, I was not able to get any 35 second sorting times using your > code. Running on Virtual II at the 1Mhz setting, the sort time for 500 > random strings was consistently over 1 minute. More on that below. > > Third, I did not try the quicksort code you posted. Instead I wrote my > own code using the same algorithm as the assembly code I posted. Here is > it (more commentary below): > > 10 FM = 65:LM = 90: GOSUB 2000 > 20 GOSUB 100 > 30 GOTO 1000 > 100 B = 1:E = N + 1 > 105 IF E = B THEN RETURN > 110 I = B:J = E:P = INT ((B + E) / 2) > 120 IF I = P THEN 200 > 130 IF A$(I) > A$(P) THEN 200 > 140 I = I + 1: GOTO 120 > 200 IF J = P THEN 300 > 210 J = J - 1: IF A$(J) > = A$(P) THEN 200 > 220 T$ = A$(J):A$(J) = A$(I):A$(I) = T$: IF I < P THEN 130 > 240 P = J: GOTO 130 > 300 IF I = P THEN 400 > 310 T$ = A$(J):A$(J) = A$(I):A$(I) = T$:P = I: GOTO 210 > 400 SL = P - B:SH = E - P - 1: IF SL < SH THEN H(Q) = P + 1:E(Q) = E:E P: GOTO 500 > 420 H(Q) = B:E(Q) = P:B = P + 1 > 500 Q = Q + 1: GOSUB 105 > 510 Q = Q - 1:B = H(Q):E = E(Q): GOTO 105 > 1000 FOR X = 1 TO N: PRINT X" "A$(X),: NEXT X > 1990 END > 2000 N = 500 > 2005 DIM A$(N),H(LM - FM + 1),E(LM - FM + 1),P(N): HOME > 2010 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I) > + CHR$ ( INT ( RND (1) * (LM - FM + 1)) + FM): NEXT : VTAB 1: PRINT > I" ": NEXT > 2020 PRINT : PRINT "Get out a stopwatch and press any key when ready": PRINT > : GET A$ > 2030 HOME : INVERSE : PRINT " Sorted List " CHR$ (7): NORMAL > 2040 RETURN > > Lastly I did some comparisons between your radix-insertion sort and this > quicker sort code. I suspected that as the number of items to be sorted > increased, qsort would compare better. That turned out to be the case. > Here are the numbers: > > NP0 > Robs-Sort average time: 1:11 > qsort average time: 2:15 > ratio rs/qs: 0.526 > > N00 > Robs-Sort average time: 3:40 > qsort average time: 4:55 > ratio rs/qs: 0.746 > > N 00 > Robs-Sort average time: 13:16 > qsort average time: 11:42 > ration rs/qs: 1.137 > This is the behavior I would expect. The radix sort on the first character takes time proportional to N, while the linear insertion sort of the rest of the key takes time proportional to (N/R)^2, so since R is fixed, as N increases, the sum is dominated by the term proportional to N^2. The quickersort takes time proportional to NlogN for all N, so it is ultimately faster. BTW, no one sort algorithm is "best" for everything. Knuth himself said (lightheartedly) that each of the couple dozen different sorting methods was "best in some situation, except bubble sort, which is never optimal--but is best for teaching about sorting!" (It's the first algorithm that most programmers come up with on their own.) My favorite for small size, suitable for sorting less than a dozen keys (like sorting a hand of cards), is "pick and zot": linearly search the list for the smallest key and output it, set the key to "infinity", and repeat until the smallest key found is infinity! Pure N^2 behavior, but fine for small N, and when space is more important than speed. -- -michael - NadaNet 3.1 and AppleCrate II: http://michaeljmahon.com
[toc] | [prev] | [next] | [standalone]
| From | gids.rs@sasktel.net |
|---|---|
| Date | 2016-03-12 10:00 -0800 |
| Message-ID | <83649064-082a-4f0e-be6a-ce626c0d9c27@googlegroups.com> |
| In reply to | #2492 |
> I've been able to spend a little bit of time on this today. > > First I modified your sort routine to keep, in addition to the array T(), an array E(), that stores the indices of the last elements in each of the linked lists, so that the lists could be easily joined without digging through each of them to find the last element. This turned out to save only about 3-5 seconds when sorting 500 strings, so it may not be worth it to you. > > Second, I was not able to get any 35 second sorting times using your code. Running on Virtual II at the 1Mhz setting, the sort time for 500 random strings was consistently over 1 minute. More on that below. > > Third, I did not try the quicksort code you posted. Instead I wrote my own code using the same algorithm as the assembly code I posted. Here is it (more commentary below): > > 10 FM = 65:LM = 90: GOSUB 2000 > 20 GOSUB 100 > 30 GOTO 1000 > 100 B = 1:E = N + 1 > 105 IF E = B THEN RETURN > 110 I = B:J = E:P = INT ((B + E) / 2) > 120 IF I = P THEN 200 > 130 IF A$(I) > A$(P) THEN 200 > 140 I = I + 1: GOTO 120 > 200 IF J = P THEN 300 > 210 J = J - 1: IF A$(J) > = A$(P) THEN 200 > 220 T$ = A$(J):A$(J) = A$(I):A$(I) = T$: IF I < P THEN 130 > 240 P = J: GOTO 130 > 300 IF I = P THEN 400 > 310 T$ = A$(J):A$(J) = A$(I):A$(I) = T$:P = I: GOTO 210 > 400 SL = P - B:SH = E - P - 1: IF SL < SH THEN H(Q) = P + 1:E(Q) = E:E = > P: GOTO 500 > 420 H(Q) = B:E(Q) = P:B = P + 1 > 500 Q = Q + 1: GOSUB 105 > 510 Q = Q - 1:B = H(Q):E = E(Q): GOTO 105 > 1000 FOR X = 1 TO N: PRINT X" "A$(X),: NEXT X > 1990 END > 2000 N = 500 > 2005 DIM A$(N),H(LM - FM + 1),E(LM - FM + 1),P(N): HOME > 2010 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I) > + CHR$ ( INT ( RND (1) * (LM - FM + 1)) + FM): NEXT : VTAB 1: PRINT > I" ": NEXT > 2020 PRINT : PRINT "Get out a stopwatch and press any key when ready": PRINT > : GET A$ > 2030 HOME : INVERSE : PRINT " Sorted List " CHR$ (7): NORMAL > 2040 RETURN > > Lastly I did some comparisons between your radix-insertion sort and this quicker sort code. I suspected that as the number of items to be sorted increased, qsort would compare better. That turned out to be the case. Here are the numbers: > > N=500 > Robs-Sort average time: 1:11 > qsort average time: 2:15 > ratio rs/qs: 0.526 > > N=1000 > Robs-Sort average time: 3:40 > qsort average time: 4:55 > ratio rs/qs: 0.746 > > N=2000 > Robs-Sort average time: 13:16 > qsort average time: 11:42 > ration rs/qs: 1.137 As far as the time comparisons are concerned, it was already mentioned that the linear search is the slowest part of this sort, and that it could be changed into a binary search with a little extra code. The binary search would then allow this sort to be consistently twice as fast as quicksort no matter how large the number of items were increased to. I also found where the time differences were, and now that I understand the program a little more, it makes sense now. A bug fix. I had confused myself with the use of the AM/BM variables and how I wanted to implement them. Now they are implemented as AM being the character to start on, and BM being the number of characters that follow AM to be sorted. i.e. if AM=65 (letter A) and BM=26 (26 characters that follow the letter A), allows for a sort on uppercase letters. This is the reason for my speed increase. In my test program, I had AM being 32 which allowed for 96 categories, so the linear search did not have as much to search through in each category. When I changed to AM=65:BM=26 then I got your 1:11 for 500 items. The number of first character sorts greatly influenced the speed of this routine. Changing over to a binary search would give a more consistent speed across the board and allow the sorting algorithm on a whole to be consistently twice as fast no matter how large the array got. Once could even combine the two sorts use the radix sort for the initial sort and use quicksort on the categories. * BUGS ELIMINATED * RADIX SORT WITH LINEAR SEARCH * CHANGE THE LINEAR SEARCH TO A BINARY SEARCH TO MAKE THIS SORT * CONSISTENTLY TWICE AS FAST AS QUICK SORT * FOR ALL UPPERCASE MAKE AM=65 : BM = 26 * TO INCLUDE ALL SYMBOLS, MAKE AM=96 : BM = 0 * FOR UPPER AND LOWER CASE MAKE, AM = 65 : BM = 58 * FOR ALL NUMBERS MAKE AM=48 : BM = 10 10 AM = 65:BM=26: GOSUB 200 20 FOR C = 1 TO N:A = ASC (A$(C)) - AM:P(C) = T(A):T(A) = C 30 IF NOT P(C) THEN NEXT : GOTO 80 40 P = P(C):L = P 50 IF A$(C) > A$(P) THEN T = P:P = P(P):FL = 1: ON P > 0 GOTO 50 60 IF FL THEN FL = NOT FL:P(C) = P:P(T) = C:T(A) = L 70 NEXT 80 FOR C = 0 TO BM:IF T(C) = 0 THEN 110 90 P = T(C) 100 FOR I = 1 TO N: IF P(P) THEN P = P(P): NEXT : GOTO 120 105 I = N: NEXT 110 P(P) = T(C + 1): NEXT 115 PRINT CHR$ (7) 120 X = 1:P = T(0): FOR I = 1 TO N: PRINT X" "A$(P),:P = P(P):X = X + 1:NEXT 199 END 200 N = 500: DIM A$(N),T(BM+1),P(N): HOME 210 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I) + CHR$ ( INT ( RND (1) * (BM)) + AM): NEXT : VTAB 1: PRINT I" ": NEXT 215 ?:?"GET OUT A STOPWATCH AND PRESS ANY KEY WHEN READY":?:GETA$ 220 HOME : INVERSE : PRINT " SORTED LIST " CHR$ (7): NORMAL 230 RETURN
[toc] | [prev] | [next] | [standalone]
| From | Michael J. Mahon <mjmahon@aol.com> |
|---|---|
| Date | 2016-03-12 14:09 -0600 |
| Message-ID | <rYmdnQiCY7EJ6nnLnZ2dnUU7-KvNnZ2d@giganews.com> |
| In reply to | #2496 |
<gids.rs@sasktel.net> wrote: >> I've been able to spend a little bit of time on this today. >> >> First I modified your sort routine to keep, in addition to the array >> T(), an array E(), that stores the indices of the last elements in each >> of the linked lists, so that the lists could be easily joined without >> digging through each of them to find the last element. This turned out >> to save only about 3-5 seconds when sorting 500 strings, so it may not be worth it to you. >> >> Second, I was not able to get any 35 second sorting times using your >> code. Running on Virtual II at the 1Mhz setting, the sort time for 500 >> random strings was consistently over 1 minute. More on that below. >> >> Third, I did not try the quicksort code you posted. Instead I wrote my >> own code using the same algorithm as the assembly code I posted. Here is >> it (more commentary below): >> >> 10 FM = 65:LM = 90: GOSUB 2000 >> 20 GOSUB 100 >> 30 GOTO 1000 >> 100 B = 1:E = N + 1 >> 105 IF E = B THEN RETURN >> 110 I = B:J = E:P = INT ((B + E) / 2) >> 120 IF I = P THEN 200 >> 130 IF A$(I) > A$(P) THEN 200 >> 140 I = I + 1: GOTO 120 >> 200 IF J = P THEN 300 >> 210 J = J - 1: IF A$(J) > = A$(P) THEN 200 >> 220 T$ = A$(J):A$(J) = A$(I):A$(I) = T$: IF I < P THEN 130 >> 240 P = J: GOTO 130 >> 300 IF I = P THEN 400 >> 310 T$ = A$(J):A$(J) = A$(I):A$(I) = T$:P = I: GOTO 210 >> 400 SL = P - B:SH = E - P - 1: IF SL < SH THEN H(Q) = P + 1:E(Q) = E:E > P: GOTO 500 >> 420 H(Q) = B:E(Q) = P:B = P + 1 >> 500 Q = Q + 1: GOSUB 105 >> 510 Q = Q - 1:B = H(Q):E = E(Q): GOTO 105 >> 1000 FOR X = 1 TO N: PRINT X" "A$(X),: NEXT X >> 1990 END >> 2000 N = 500 >> 2005 DIM A$(N),H(LM - FM + 1),E(LM - FM + 1),P(N): HOME >> 2010 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I) >> + CHR$ ( INT ( RND (1) * (LM - FM + 1)) + FM): NEXT : VTAB 1: PRINT >> I" ": NEXT >> 2020 PRINT : PRINT "Get out a stopwatch and press any key when ready": PRINT >>> GET A$ >> 2030 HOME : INVERSE : PRINT " Sorted List " CHR$ (7): NORMAL >> 2040 RETURN >> >> Lastly I did some comparisons between your radix-insertion sort and this >> quicker sort code. I suspected that as the number of items to be sorted >> increased, qsort would compare better. That turned out to be the case. >> Here are the numbers: >> >> NP0 >> Robs-Sort average time: 1:11 >> qsort average time: 2:15 >> ratio rs/qs: 0.526 >> >> N00 >> Robs-Sort average time: 3:40 >> qsort average time: 4:55 >> ratio rs/qs: 0.746 >> >> N 00 >> Robs-Sort average time: 13:16 >> qsort average time: 11:42 >> ration rs/qs: 1.137 > > > As far as the time comparisons are concerned, it was already mentioned > that the linear search is the slowest part of this sort, and that it > could be changed into a binary search with a little extra code. The > binary search would then allow this sort to be consistently twice as fast > as quicksort no matter how large the number of items were increased to. > > > > I also found where the time differences were, and now that I understand > the program a little more, it makes sense now. > > A bug fix. I had confused myself with the use of the AM/BM variables and > how I wanted to implement them. > Now they are implemented as AM being the character to start on, and BM > being the number of characters that follow AM to be sorted. i.e. if AMe > (letter A) and BM& (26 characters that follow the letter A), allows for a > sort on uppercase letters. > > This is the reason for my speed increase. In my test program, I had AM > being 32 which allowed for 96 categories, so the linear search did not > have as much to search through in each category. > > When I changed to AMe:BM& then I got your 1:11 for 500 items. The number > of first character sorts greatly influenced the speed of this routine. > Changing over to a binary search would give a more consistent speed > across the board and allow the sorting algorithm on a whole to be > consistently twice as fast no matter how large the array got. > > Once could even combine the two sorts use the radix sort for the initial > sort and use quicksort on the categories. > > > > > * BUGS ELIMINATED > * RADIX SORT WITH LINEAR SEARCH > * CHANGE THE LINEAR SEARCH TO A BINARY SEARCH TO MAKE THIS SORT > * CONSISTENTLY TWICE AS FAST AS QUICK SORT > > * FOR ALL UPPERCASE MAKE AMe : BM = 26 > * TO INCLUDE ALL SYMBOLS, MAKE AM : BM = 0 > * FOR UPPER AND LOWER CASE MAKE, AM = 65 : BM = 58 > * FOR ALL NUMBERS MAKE AMH : BM = 10 > > 10 AM = 65:BM&: GOSUB 200 > 20 FOR C = 1 TO N:A = ASC (A$(C)) - AM:P(C) = T(A):T(A) = C > 30 IF NOT P(C) THEN NEXT : GOTO 80 > 40 P = P(C):L = P > 50 IF A$(C) > A$(P) THEN T = P:P = P(P):FL = 1: ON P > 0 GOTO 50 > 60 IF FL THEN FL = NOT FL:P(C) = P:P(T) = C:T(A) = L > 70 NEXT > 80 FOR C = 0 TO BM:IF T(C) = 0 THEN 110 > 90 P = T(C) > 100 FOR I = 1 TO N: IF P(P) THEN P = P(P): NEXT : GOTO 120 > 105 I = N: NEXT > 110 P(P) = T(C + 1): NEXT > 115 PRINT CHR$ (7) > 120 X = 1:P = T(0): FOR I = 1 TO N: PRINT X" "A$(P),:P = P(P):X = X + 1:NEXT > 199 END > > 200 N = 500: DIM A$(N),T(BM+1),P(N): HOME > 210 FOR I = 1 TO N: FOR J = 1 TO 5 + INT ( RND (1) * 5):A$(I) = A$(I) > + CHR$ ( INT ( RND (1) * (BM)) + AM): NEXT : VTAB 1: PRINT I" ": NEXT > 215 ?:?"GET OUT A STOPWATCH AND PRESS ANY KEY WHEN READY":?:GETA$ > 220 HOME : INVERSE : PRINT " SORTED LIST " CHR$ (7): NORMAL > 230 RETURN > Linear search is natural for a linked list. Binary search of a linear linked list is problematic. The natural linked data structure corresponding to a binary search is a binary tree. This tree could be either a linked structure with two links per item or, if data movement is allowable, no links but a "heap-structured" array, in which the two "descendants" of item J are items 2J and 2J+1. Either of these approaches will have poorer performance than linear insertion when the bucket size is small, but their NlogN performance will eventually win as bucket size increases. -- -michael - NadaNet 3.1 and AppleCrate II: http://michaeljmahon.com
[toc] | [prev] | [next] | [standalone]
| From | wssimms@gmail.com |
|---|---|
| Date | 2016-03-12 22:17 -0800 |
| Message-ID | <a257fb9d-01bd-42d4-866a-1e99ca6d00d2@googlegroups.com> |
| In reply to | #2496 |
I couldn't quite figure out AM and BM myself, so I changed them to FM (first character) and LM (last character). You are right about the increased number of buckets playing a large role in the sort time. Of course that means an increased extra memory requirement but as long as your got the variable space to spare that's fine. As for the switch to binary search or qsort on the buckets, that's a prinlet because it's really tough to binary search a linked list. Instead you would just replace the linked list with a balanced binary tree. That would speed things up a bit for larger N. But actually the idea of implementing balanced binary trees in AppleSoft to speed up a string sort seems pretty comical to me. You've got to draw a line somewhere on what's just not a great use of AppleSoft and that's past the line for me :-)
[toc] | [prev] | [next] | [standalone]
| From | Scott Hemphill <hemphill@hemphills.net> |
|---|---|
| Date | 2016-03-13 09:03 -0400 |
| Message-ID | <87io0qlecw.fsf@hemphills.net> |
| In reply to | #2498 |
wssimms@gmail.com writes: > I couldn't quite figure out AM and BM myself, so I changed them to FM > (first character) and LM (last character). > > You are right about the increased number of buckets playing a large > role in the sort time. Of course that means an increased extra memory > requirement but as long as your got the variable space to spare that's > fine. > > As for the switch to binary search or qsort on the buckets, that's a > prinlet because it's really tough to binary search a linked > list. Instead you would just replace the linked list with a balanced > binary tree. That would speed things up a bit for larger N. > > But actually the idea of implementing balanced binary trees in > AppleSoft to speed up a string sort seems pretty comical to me. You've > got to draw a line somewhere on what's just not a great use of > AppleSoft and that's past the line for me :-) Unbalanced trees would be simpler to implement, and might be better for the relatively small number of records you would want to sort on a 6502. Both have poor behavior if the records are already in order, so you could shuffle the array first. :-) Scott -- Scott Hemphill hemphill@alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear
[toc] | [prev] | [next] | [standalone]
| From | gids.rs@sasktel.net |
|---|---|
| Date | 2016-03-13 09:22 -0700 |
| Message-ID | <08136179-746a-4991-b236-86f54fa2ec8b@googlegroups.com> |
| In reply to | #2498 |
On Sunday, March 13, 2016 at 12:17:21 AM UTC-6, wss wrote: > I couldn't quite figure out AM and BM myself, so I changed them to FM (first character) and LM (last character). > > You are right about the increased number of buckets playing a large role in the sort time. Of course that means an increased extra memory requirement but as long as your got the variable space to spare that's fine. > > As for the switch to binary search or qsort on the buckets, that's a prinlet because it's really tough to binary search a linked list. Instead you would just replace the linked list with a balanced binary tree. That would speed things up a bit for larger N. > > But actually the idea of implementing balanced binary trees in AppleSoft to speed up a string sort seems pretty comical to me. You've got to draw a line somewhere on what's just not a great use of AppleSoft and that's past the line for me :-) I don't use applesoft much myself. I only brought this up because the listing was in applesoft, and I wanted to be able to understand it and get it perfected before I convert to assembly language. My first idea was to use the radix sort on the second and subsequent characters as well. But couldn't see how I could get that to work. I already have a very good binary search program in assembly, but I was struggling to see how I could use it due to the linked lists. You gave me an idea using the E() array. I use sorts on a regular basis in my programming. So, like all things I do on the computer, I am on a quest to find the fastest and most compact programming ideas available. There seems to be no shortage of applesoft programs, and some of the ideas implemented in them have no assembly language counterpart.
[toc] | [prev] | [next] | [standalone]
| From | Michael J. Mahon <mjmahon@aol.com> |
|---|---|
| Date | 2016-03-13 13:45 -0500 |
| Message-ID | <JfSdne9ivfOoKHjLnZ2dnUU7-WHNnZ2d@giganews.com> |
| In reply to | #2500 |
<gids.rs@sasktel.net> wrote: > On Sunday, March 13, 2016 at 12:17:21 AM UTC-6, wss wrote: >> I couldn't quite figure out AM and BM myself, so I changed them to FM >> (first character) and LM (last character). >> >> You are right about the increased number of buckets playing a large role >> in the sort time. Of course that means an increased extra memory >> requirement but as long as your got the variable space to spare that's fine. >> >> As for the switch to binary search or qsort on the buckets, that's a >> prinlet because it's really tough to binary search a linked list. >> Instead you would just replace the linked list with a balanced binary >> tree. That would speed things up a bit for larger N. >> >> But actually the idea of implementing balanced binary trees in AppleSoft >> to speed up a string sort seems pretty comical to me. You've got to draw >> a line somewhere on what's just not a great use of AppleSoft and that's >> past the line for me :-) > > > I don't use applesoft much myself. I only brought this up because the > listing was in applesoft, and I wanted to be able to understand it and > get it perfected before I convert to assembly language. My first idea > was to use the radix sort on the second and subsequent characters as > well. But couldn't see how I could get that to work. I already have a > very good binary search program in assembly, but I was struggling to see > how I could use it due to the linked lists. You gave me an idea using the E() array. What's required is running the radix passes from the least significant key character to the most significant, and "restacking" or splicing the buckets into a linear list between passes by putting the highest value buckets in front of the lower value ones. This "complete" radix sort will run in constant time per item, dependent only upon the length of the keys (the number of passes). > I use sorts on a regular basis in my programming. So, like all things I > do on the computer, I am on a quest to find the fastest and most compact > programming ideas available. Each application will have characteristics which will lead to a different order of "desirability" for the various sorting algorithms. Important characteristics are: the relative scarcity of time or space, the number of items, the length and distribution(s) of the key(s), and, perhaps most significant, which subroutines you have already at your disposal. ;-) > There seems to be no shortage of applesoft programs, and some of the > ideas implemented in them have no assembly language counterpart. > Whaaaat? Certainly there is an assembly language equivalent to *every* Applesoft program, so I'm not sure what you mean. Perhaps you mean that Applesoft's built-in support for floating-point and varying-length strings leads to small Applesoft programs that would be fairly large (and improbable) assembly language programs? -- -michael - NadaNet 3.1 and AppleCrate II: http://michaeljmahon.com
[toc] | [prev] | [next] | [standalone]
Page 1 of 3 [1] 2 3 Next page →
Back to top | Article view | comp.sys.apple2.programmer
csiph-web