A music library scan tool I've written produces a list of over 4000???
lines, each line shows the path to a particular album. But the filer
does not list in alphabetic order...
There are two sort types I understand; Bubble sort and what I callThanks for Coline :-)
"Best So Far" but I bet there is a different official name.
I've always gone for bubble sort for two reasons, firstly I
understand the principle and it does not require another chunk of ram
to hold the result file. But using this method takes 12.6 seconds.
The "Best So Far" method is to repeatedly pass through the source
file and pick out the best line on each pass and move it out to
another store and mark it as used in the source. I had the idea of
squirting these best lines one at a time to a file on disc rather
than provide temporary ram.
I realised that using OS_BPut, line by line was not going to be as
fast as saving a file in one go but tried it anyway. It took 6
seconds. Faster yes but I don't like it, the sorted file never exists
in the application. True it doesn't matter but it kind of does to me.
Anyone got any suggestions for a better approach? Something I might
even understand?
A slight complication, any sort would need to handle is the Coline
Dion problem. I like treating o as e as regards the sort comparison
stage.
Also, how is StrongEd so lightning fast on sorts? It barely blinks.Yes, but failed with Coline...
Still coded in Basic Assembler, in case you need to know.good luck!
Thanks.--
Bob.
In message <5d336712aebob@sick-of-spam.invalid>
Bob Latham <bob@sick-of-spam.invalid> wrote:
But the filer does not list in alphabetic order...
??? Is the list a text file?
In article <1db391335d.jmb@jmc.bruck.orange.fr>,I did some tests with C/C++ fonctions, result(s) not good with "Coline" problem.
Jean-Michel <jmc.bruck@orange.fr> wrote:
In message <5d336712aebob@sick-of-spam.invalid>
Bob Latham <bob@sick-of-spam.invalid> wrote:
But the filer does not list in alphabetic order...
??? Is the list a text file?
Yes.
Bob.--
A music library scan tool I've written produces a list of over 4000
lines, each line shows the path to a particular album. But the filer
does not list in alphabetic order...
In article <5d336712aebob@sick-of-spam.invalid>,
Bob Latham <bob@sick-of-spam.invalid> wrote:
A music library scan tool I've written produces a list of over 4000
lines, each line shows the path to a particular album. But the filer
does not list in alphabetic order...
My own database program uses SYS "OS_HeapSort". It sorts a block of 4000 strings in less than a fraction of a second, inluding the routine that
takes capitals, diacritics and other signs into account. A perfect job, but... quite some programming is involved.
Paul
Nice,You have implemented your own routine in ASM
In article <91421d345d.jmb@jmc.bruck.orange.fr>,
Jean-Michel <jmc.bruck@orange.fr> wrote:
Nice,You have implemented your own routine in ASM
No, I wrote the entire program in BASIC and then compiled it with
!ABC. But of course, OS_HeapSort does the actual sorting. My
routines just prepare the strings. Remember however that
OS_HeapSort only sorts memory blocks, it won't do anything with
arrays - as far as I remember.
In article <5d34218484Paul@sprie.nl>,
Paul Sprangers <Paul@sprie.nl> wrote:
In article <91421d345d.jmb@jmc.bruck.orange.fr>,
Jean-Michel <jmc.bruck@orange.fr> wrote:
Nice,You have implemented your own routine in ASM
No, I wrote the entire program in BASIC and then compiled it with
!ABC. But of course, OS_HeapSort does the actual sorting. My
routines just prepare the strings. Remember however that
OS_HeapSort only sorts memory blocks, it won't do anything with
arrays - as far as I remember.
The ArmSort module will happily sort one or more BASIC arrays (see www.avisoft.f9.co.uk) ... but it does not cater for the Coline
problem without creating a duplicate array with the accent removed.
I've written a short BASIC program that sorts the lines in a text
file, taking capitals, undercasts and all sorts of diacritics, as
well most other characters into account.
My own example has nearly 6000 lines. The BASIC version took about
23 seconds to sort them, while the compiled version took less than
3 seconds to do the job. (On a 4to2 computer.)
The text file is not included, but you should rename yours to
"Texts" in order to let the program do its work. If your text file
counts more than 6000 lines, you should change the DIM's in the
program. Compile the program with the freely available !ABC
compiler. Remember that the compiled version needs quite a big NEXT
slot.
There are much better or memory friendly ways to do this, but as an
example it may have some use.
As a specific example, it works but does have some limitations.
The most obvious one is that any characters not included in FNcase are omitted from the sort key completely (eg blank or hyphen).
I suspect however that as FNcase tests each character 29 times, it could
be optimised.
I've written a short BASIC program that sorts the lines in a text file, taking capitals, undercasts and all sorts of diacritics, as well most other characters into account.
My own example has nearly 6000 lines.
The BASIC version took about 23 seconds to sort them, while the compiled version took less than 3 seconds to do the job. (On a 4to2 computer.)
The text file is not included, but you should rename yours to "Texts" in order to let the program do its work. If your text file counts more than
6000 lines, you should change the DIM's in the program. Compile the program with the freely available !ABC compiler. Remember that the compiled version needs quite a big NEXT slot.
There are much better or memory friendly ways to do this, but as an example it may have some use.
Paul
REM DIM two string arrays,
REM big enough to store your lines.
REM My example had 5913 lines.
DIM text$(5913), dummy$(5913)
REM Now store every line into both arrays.
REM The dummy array will be adjusted on the fly,
REM by changing undercast into capitals and by
REM removing diacritics, in FNcase (see botom).
f%=OPENIN("Texts")
IF f%>0 THEN
a%=0
REPEAT
a%+=1
text$(a%) = GET$#f%
dummy$(a%) = FNcase(text$(a%))
UNTIL EOF#f%
ENDIF
IF f%>0 THEN CLOSE#f%
REM NOW the actual sorting will start
OK% = TRUE
time = TIME
PROCsort
t = TIME - time : REM The time needed in centiseconds.
REM Finally, print the sorted lines
FOR i% = 1 TO a% : PRINT STR$(i%) +": " + text$(i%) : NEXT
PRINT t
END
DEF PROCsort
FOR i% = 1 TO a%
IF dummy$(i%) < dummy$(i%-1) THEN
SWAP text$(i%),text$(i%-1)
SWAP dummy$(i%),dummy$(i%-1)
OK% = FALSE
ENDIF
NEXT
IF NOT OK% THEN OK% = TRUE : PROCsort
ENDPROC
DEF FNcase(x$)
y$=""
FOR j%= 1 TO LEN x$
c%=ASC(MID$(x$,j%,1))
IF c%>96 AND c%<123 THEN y$ += CHR$(c%-32) : REM undercast -> capital
IF c%>47 AND c%< 58 THEN y$ += CHR$(c%) : REM numbers don't change
IF c%>64 AND c%< 91 THEN y$ += CHR$(c%) : REM capitals don't change
IF c%>223 AND c%<230 THEN y$ += "A" : REM diacritics removed
IF c%>231 AND c%<231 THEN y$ += "E"
IF c%>235 AND c%<240 THEN y$ += "I"
IF c%>241 AND c%<247 THEN y$ += "O"
IF c%>248 AND c%<253 THEN y$ += "U"
IF c%=229 OR c%=197 THEN y$ += "A"
IF c%=230 OR c%=198 THEN y$ += "AE"
IF c%=231 OR c%=199 THEN y$ += "C"
IF c%=241 OR c%=209 THEN y$ += "N"
IF c%=248 OR c%=216 THEN y$ += "O"
IF c%=223 THEN y$ += "SS"
IF c%=255 THEN y$ += "Y"
NEXT
=y$
IF c%>231 AND c%<231 THEN y$ += "E"
=> IF c%>231 AND c%<236 THEN y$ += "E"
I am waiting the same for UTF8...
| Sysop: | Amessyroom |
|---|---|
| Location: | Fayetteville, NC |
| Users: | 76 |
| Nodes: | 6 (0 / 6) |
| Uptime: | 57:40:15 |
| Calls: | 1,265 |
| Calls today: | 1 |
| Files: | 1,362 |
| D/L today: |
4 files (9,632K bytes) |
| Messages: | 285,926 |