Sorting And Searching

Anything QL Software or Programming Related.
User avatar
dden
ROM Dongle
Posts: 43
Joined: Thu Jan 19, 2017 8:56 am

Sorting And Searching

Post by dden »

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


David
User avatar
tofro
Font of All Knowledge
Posts: 2685
Joined: Sun Feb 13, 2011 10:53 pm
Location: SW Germany

Re: Sorting And Searching

Post by tofro »

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


ʎɐqǝ ɯoɹɟ ǝq oʇ ƃuᴉoƃ ʇou sᴉ pɹɐoqʎǝʞ ʇxǝu ʎɯ 'ɹɐǝp ɥO
User avatar
Giorgio Garabello
Gold Card
Posts: 277
Joined: Tue Jun 30, 2015 8:39 am
Location: Turin, Italy
Contact:

Re: Sorting And Searching

Post by Giorgio Garabello »

there's also something done by W. Lenerz..but i don't remember the name.. :-/


tcat
Super Gold Card
Posts: 633
Joined: Fri Jan 18, 2013 5:27 pm
Location: Prague, Czech Republic

Re: Sorting And Searching

Post by tcat »

Hi,

Just an idea, rather then sort disorder, insert into array orderly, if that is possible.

Tomas


User avatar
dilwyn
Mr QL
Posts: 2753
Joined: Wed Dec 01, 2010 10:39 pm

Re: Sorting And Searching

Post by dilwyn »

Giorgio Garabello wrote:there's also something done by W. Lenerz..but i don't remember the name.. :-/
ARRAY by Wolfgang is on Toolkits page on my website.
http://www.dilwyn.me.uk/tk/index.html
I don't know of any machine coded wildcard search, sorry.


tcat
Super Gold Card
Posts: 633
Joined: Fri Jan 18, 2013 5:27 pm
Location: Prague, Czech Republic

Re: Sorting And Searching

Post by tcat »

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


User avatar
dden
ROM Dongle
Posts: 43
Joined: Thu Jan 19, 2017 8:56 am

Re: Sorting And Searching

Post by dden »

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 am not able to do any programing in C, I'm afraid.
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
tcat
Super Gold Card
Posts: 633
Joined: Fri Jan 18, 2013 5:27 pm
Location: Prague, Czech Republic

Re: Sorting And Searching

Post by tcat »

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.

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
Keeping sorted string array
Keeping sorted string array
Quick Search & Insert.png (8.71 KiB) Viewed 3687 times
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


User avatar
tofro
Font of All Knowledge
Posts: 2685
Joined: Sun Feb 13, 2011 10:53 pm
Location: SW Germany

Re: Sorting And Searching

Post by tofro »

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
tcat
Super Gold Card
Posts: 633
Joined: Fri Jan 18, 2013 5:27 pm
Location: Prague, Czech Republic

Re: Sorting And Searching

Post by tcat »

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


Post Reply