Sorting And Searching
Sorting And Searching
I am looking for basic extensions for sorting and searching string arrays.
And (just to push my luck) wildcard string searches using * and ? or equivalent.
David
And (just to push my luck) wildcard string searches using * and ? or equivalent.
David
David
Re: Sorting And Searching
David,
have a look at the DIY toolkit (from Dilwyn's site).
Section z has INARRAY and MINMAX as examples of fast searching, including "close" and "phonem" searches within S*Basic arrays.
Section X has a fast SEARCH_MEMORY function
Tobias
have a look at the DIY toolkit (from Dilwyn's site).
Section z has INARRAY and MINMAX as examples of fast searching, including "close" and "phonem" searches within S*Basic arrays.
Section X has a fast SEARCH_MEMORY function
Tobias
ʎɐqǝ ɯoɹɟ ǝq oʇ ƃuᴉoƃ ʇou sᴉ pɹɐoqʎǝʞ ʇxǝu ʎɯ 'ɹɐǝp ɥO
- Giorgio Garabello
- Gold Card
- Posts: 277
- Joined: Tue Jun 30, 2015 8:39 am
- Location: Turin, Italy
- Contact:
Re: Sorting And Searching
there's also something done by W. Lenerz..but i don't remember the name.. :-/
Quantum Technology
http://www.hunggartorino.it/ql/language/en/
http://www.hunggartorino.it/ql/language/en/
Re: Sorting And Searching
Hi,
Just an idea, rather then sort disorder, insert into array orderly, if that is possible.
Tomas
Just an idea, rather then sort disorder, insert into array orderly, if that is possible.
Tomas
Re: Sorting And Searching
ARRAY by Wolfgang is on Toolkits page on my website.Giorgio Garabello wrote:there's also something done by W. Lenerz..but i don't remember the name.. :-/
http://www.dilwyn.me.uk/tk/index.html
I don't know of any machine coded wildcard search, sorry.
--
All things QL - https://dilwyn.qlforum.co.uk/index.html
All things QL - https://dilwyn.qlforum.co.uk/index.html
Re: Sorting And Searching
Hi,
I usually fancy coding something simple myself. Depending on the size of an array, if the number of elements is fixed or variable, also if you keep the array sorted.
Fast algorithms may work with `halving' the search range, while you always get the middle index first, and then you look for the element in upper or bottom half, then you halve the range again. If `bottom'>`top' then element not found.
Can you post here a sample array you plan to work with?
There were also some list routines (LIBLIST) for objects coded in plain `C' by Dave Walker, doing also binary trees.
Tomas
I usually fancy coding something simple myself. Depending on the size of an array, if the number of elements is fixed or variable, also if you keep the array sorted.
Fast algorithms may work with `halving' the search range, while you always get the middle index first, and then you look for the element in upper or bottom half, then you halve the range again. If `bottom'>`top' then element not found.
Can you post here a sample array you plan to work with?
There were also some list routines (LIBLIST) for objects coded in plain `C' by Dave Walker, doing also binary trees.
Tomas
Re: Sorting And Searching
I am not able to do any programing in C, I'm afraid.tcat wrote:Hi,
I usually fancy coding something simple myself. Depending on the size of an array, if the number of elements is fixed or variable, also if you keep the array sorted.
Fast algorithms may work with `halving' the search range, while you always get the middle index first, and then you look for the element in upper or bottom half, then you halve the range again. If `bottom'>`top' then element not found.
Can you post here a sample array you plan to work with?
There were also some list routines (LIBLIST) for objects coded in plain `C' by Dave Walker, doing also binary trees.
Tomas
I have read articles such as http://quanta.org.uk/wp-content/uploads ... INE-20.pdf (binary chop) and http://www.dilwyn.me.uk/docs/articles/sorting.zip (general sorting routines in BASIC).
At the moment, I don't know exactly how the data will look - probably a normal 2 or 3 dimensional string array. This will be for general use in a variety of programs. I think that Wolfgang's ARRAY that was mentioned here should be suitable, though I have not tried it yet.
I've written to Dilwyn as well, as his Sort/Column Print program has quite a fast string sort routine despite being written in compiled basic, faster than i have been able to achieve. He said he'll extract the code from that for me when he gets time, or send me the sources.
The Wildcard is for a word game I hope to write in the future, after my current project.
It will be similar to a Scrabble board, where you have to add words to the board using a combination of what is already on the board and tiles you hold, so for example you might have up to about 8 or 10 tiles in your hand, playing against computer - the routine will be for the computer player to look up in a word list, so for example if the computer has to try to place a word around tiles on the board which have something B something T something L, the wildcard search might need to be *B?T?L* with matches from the word list compared to the tiles held in the computer's hand.
The word list is just an ascii ordered list
WORD1
WORD2
WORD3 and so on.
The binary search would be used for adding new words to an already sorted dictionary.
Hope that helps.
David
David
Re: Sorting And Searching
Hi,
I was able to code a simple quick search and insert, it works with integer arithmetics, that may be faster only to interpreted basic once compiled. To this end `'res' and 'i' variables may need to be also declared as integers.
I do not see a simple way to pattern matching and wildcards.
EDIT
That brings up a question, why reals are faster than integers in interpreted basic?
Also interpreter does not allow integers as loop and select variables.
Tom
I was able to code a simple quick search and insert, it works with integer arithmetics, that may be faster only to interpreted basic once compiled. To this end `'res' and 'i' variables may need to be also declared as integers.
I do not see a simple way to pattern matching and wildcards.
Code: Select all
100 REMark String Quick Search & Insert
110 REMark (c)tcat, 2017 Tomas Kral
120 :
130 REMark Globals
140 size%=0 : max%=100
150 DIM words$(max%,16)
160 :
170 :
180 DEFine FuNction Find% (str$,id%)
190 REMark Quick search returns:
200 REMark 0=not found, 1=found, id%=position
210 LOCal top%,bot%,mid%
220 top%=0 : bot%=size%
230 :
240 REPeat find_loop
250 mid%=(bot%+top%) DIV 2
260 :
270 IF top%>bot% THEN
280 id%=mid%+1 : RETurn 0
290 ELSE IF str$ = words$(mid%) THEN
300 id%=mid% : RETurn 1
310 ELSE IF str$ > words$(mid%) THEN
320 top%=mid%+1
330 ELSE IF str$ < words$(mid%) THEN
340 bot%=mid%-1
350 END IF : END IF : END IF : END IF
360 END REPeat find_loop
370 END DEFine Find%
380 :
390 :
400 DEFine FuNction Insert% (str$,id%)
410 REMark Inserts String at position id%
420 REMark Returns 2=ok, -1=array full
430 LOCal i
440 :
450 IF size% >= max% THEN RETurn -1
460 FOR i=size% TO id% STEP -1
470 words$(i+1)=words$(i)
480 END FOR i
490 words$(id%)=str$
500 size%=size%+1
510 :
520 RETurn 2
530 END DEFine Insert%
540 :
550 :
560 DEFine PROCedure Main
570 REMark Main user loop
580 LOCal word$(16),id%,res
590 CLS: CLS#2
600 :
610 PRINT#2,\\"Insert game word"
620 PRINT#2," - enter blank to quit"
630 PRINT ,\\"Words sorted list"
640 :
650 REPeat main_loop
660 INPUT#2,"> ";word$
670 IF word$='' THEN EXIT main_loop
680 :
690 res=Find%(word$,id%)
700 IF res=0 THEN res=Insert%(word$,id%)
710 SELect ON res
720 = 1: PRINT#2,"found at"!;id%
730 = 2: PRINT#2,"inserted at"!;id%
740 =-1: PRINT#2,"array full"
750 END SELect
760 :
770 CLS
780 PRINT,\\"Words sorted list"
790 PRINT words$(1 TO size%)
800 END REPeat main_loop
810 END DEFine Main
820 :
830 Main
840 :
850 REMark END
That brings up a question, why reals are faster than integers in interpreted basic?
Also interpreter does not allow integers as loop and select variables.
Tom
Re: Sorting And Searching
tcat wrote:That brings up a question, why reals are faster than integers in interpreted basic?
Also interpreter does not allow integers as loop and select variables.
Tom
There's a simple answer to that: SuperBASIC never does integer arithmetic. Integers are always converted to floating point first, the actual calculation is done in FP, if the result needs to go into an integer variable, it is then converted back into integer. What you obviously see here is the time needed for conversion from integer to FP and back is the overhead.
Once you compile the program, though, things are entirely different. Compiled integer code runs way faster than FP code, because compilers generate code for integer arithmetic, if they can.
Some of the newer (MG) ROM version actually supported (in a more or less buggy way) integer (and even character) SELect and loop variables. Compiled code will also highly benefit from integer loops and SELects.
Tobias
ʎɐqǝ ɯoɹɟ ǝq oʇ ƃuᴉoƃ ʇou sᴉ pɹɐoqʎǝʞ ʇxǝu ʎɯ 'ɹɐǝp ɥO
Re: Sorting And Searching
Hi Tobias,
Ah, that explains that nicely. So what QL does is actually clever, keeping select & loop variables in FP, that way is faster in the interpreter.
Real benefit of integers is perhaps smaller space allocated on stack or heap, as TG says, integers take words, floats take exponent(word)+mantisa(long), i.e. 2bytes versus 6bytes.
Right?
Tomas
Ah, that explains that nicely. So what QL does is actually clever, keeping select & loop variables in FP, that way is faster in the interpreter.
Real benefit of integers is perhaps smaller space allocated on stack or heap, as TG says, integers take words, floats take exponent(word)+mantisa(long), i.e. 2bytes versus 6bytes.
Right?
Tomas