(BASIC) string handling advice
(BASIC) string handling advice
I've started writing a new thing and without wanting to give anything away at this stage - don't want to spoil the surprise! - it involves quite a lot of free text input. The program then searches the string that you've entered for the presence of certain terms. I do have a method but it can be horrendously slow, especially if the initial string entered is long. Essentially I suppose what I'm asking is whether there's a fast way to simulate an INSTRING function on the Spectrum in an efficient manner.
e.g. if the input is something like "the quick brown fox jumped over the lazy dog, onto a crocodile then onto a tree stump", what would be fastest way to determine whether the term "dog" or "crocodile" or "stump" (or whatever) is within the original input? The position at which it occurs isn't important, just whether the search string appears. At the moment I'm just going through the input string character by character but there must be a quicker way.
I've searched around a bit but can't find anything on this so any advice would be much appreciated.
e.g. if the input is something like "the quick brown fox jumped over the lazy dog, onto a crocodile then onto a tree stump", what would be fastest way to determine whether the term "dog" or "crocodile" or "stump" (or whatever) is within the original input? The position at which it occurs isn't important, just whether the search string appears. At the moment I'm just going through the input string character by character but there must be a quicker way.
I've searched around a bit but can't find anything on this so any advice would be much appreciated.
www.fahnn.co.uk / Trine Michelson's Hot Parts: www.fahnn.co.uk/trine.txt / Big Deal (demo): http://www.fahnn.co.uk/big_deal.tap / tw@tter: http://www.fahnn.co.uk/[email protected]
- Einar Saukas
- Bugaboo
- Posts: 3094
- Joined: Wed Nov 15, 2017 2:48 pm
Re: (BASIC) string handling advice
Do you need to search for small strings within a (possible large) string? If so, forget complex solutions like the classic Knuth-Morris-Pratt algorithm, and just implement a straightforward Assembly routine to be accessed from BASIC.
Re: (BASIC) string handling advice
I didn't need to forget about that because I'd never heard of it! Interesting stuff though.Einar Saukas wrote: ↑Thu May 23, 2019 7:49 pm forget complex solutions like the classic Knuth-Morris-Pratt algorithm
I can't remember enough assembly to be able to do that, I'm afraid. Maybe that is the answer though and it would give me the impetus to get out of BASIC and into re-learning at least the basics of proper code. Is there genuinely no fast solution in BASIC?Einar Saukas wrote: ↑Thu May 23, 2019 7:49 pmand just implement a straightforward Assembly routine to be accessed from BASIC.
www.fahnn.co.uk / Trine Michelson's Hot Parts: www.fahnn.co.uk/trine.txt / Big Deal (demo): http://www.fahnn.co.uk/big_deal.tap / tw@tter: http://www.fahnn.co.uk/[email protected]
- Einar Saukas
- Bugaboo
- Posts: 3094
- Joined: Wed Nov 15, 2017 2:48 pm
Re: (BASIC) string handling advice
If you post your BASIC implementation here, people will certainly help with suggestions to improve it.
However the fastest solution is to use an Assembly routine you could call from BASIC. There's no need to implement it from scratch, it was already implemented here:
http://programandala.net/en.program.deffnder.html
I can compile it for you if you want, just let me know. Just remember to credit the original authors if you use it, as stated in their code license.
However the fastest solution is to use an Assembly routine you could call from BASIC. There's no need to implement it from scratch, it was already implemented here:
http://programandala.net/en.program.deffnder.html
I can compile it for you if you want, just let me know. Just remember to credit the original authors if you use it, as stated in their code license.
Re: (BASIC) string handling advice
I've only had a quick glance but this has given me a lot to think about, thank-you! I look forward to going through it properly (and probably not understanding much of it) tomorrow. I really need to incorporate some code, I think it's the only way to get some of my more ambitious stuff off the ground. Thanks again, your help is really appreciated.Einar Saukas wrote: ↑Thu May 23, 2019 9:20 pm If you post your BASIC implementation here, people will certainly help with suggestions to improve it.
However the fastest solution is to use an Assembly routine you could call from BASIC. There's no need to implement it from scratch, it was already implemented here:
http://programandala.net/en.program.deffnder.html
I can compile it for you if you want, just let me know. Just remember to credit the original authors if you use it, as stated in their code license.
www.fahnn.co.uk / Trine Michelson's Hot Parts: www.fahnn.co.uk/trine.txt / Big Deal (demo): http://www.fahnn.co.uk/big_deal.tap / tw@tter: http://www.fahnn.co.uk/[email protected]
Re: (BASIC) string handling advice
One idea would be to search as you type and show every word that starts with the first consonant letters, just the first three consonants.
Re: (BASIC) string handling advice
What about this routine I have created -very quickly, sorry-?
https://drive.google.com/file/d/1gWF5-Z ... sp=sharing
The idea is to separate every single word and put it in a array z$(w,l); it is supossed that words are separated by a blank space. The max number of words in the sentence is w, the max lenght of your commands is l.
After that, you have an array with 10 words; you can add more if you want larger sentences to analyse.
Then, for each word in the array, the first letter of the word z$(a,1) is linked to a line according to its CODE. In my example I did GO SUB 1000+CODE Z$(a,1)
If you write the commands in the correspondent line, you can check very fast if each word of the sentence matches with any of your commands.
Sorry, I know it is difficult to explain, let´s see an example:
-In my program, I defined as commands the words "cat","dog" and "lion".
-You can enter a sentence with many words (but the array will work with the first ten words, you can increase it if you want)
-Then, all words will be listed each one in a row.
-If one word is equal to a command, the program will tell you.
(Please note that all commands must start by different letters, in this quick version of the algorithm).
So, if you type "a tiger is sleeping in the jungle", the program will show these words one by one, but no command is detected.
If you type "a tiger is playing with a dog in the jungle", the program will list the words, recognizing "dog" as a command. Try "a lion and a cat are playing with a dog"
An improvement of the program should be:
- the ability to manage upper case and lower case characters, and even numbers.
- the detection of different commands that start with the same letter. Maybe using 1000+10*CODE z$(a,1) will allow space to use consecutive IF to check all commands starting by the same letter.
But for now, I believe this is a fast way to detect the different commands into a sentence.
Hope it is useful for your adventure!
https://drive.google.com/file/d/1gWF5-Z ... sp=sharing
The idea is to separate every single word and put it in a array z$(w,l); it is supossed that words are separated by a blank space. The max number of words in the sentence is w, the max lenght of your commands is l.
After that, you have an array with 10 words; you can add more if you want larger sentences to analyse.
Then, for each word in the array, the first letter of the word z$(a,1) is linked to a line according to its CODE. In my example I did GO SUB 1000+CODE Z$(a,1)
If you write the commands in the correspondent line, you can check very fast if each word of the sentence matches with any of your commands.
Sorry, I know it is difficult to explain, let´s see an example:
-In my program, I defined as commands the words "cat","dog" and "lion".
-You can enter a sentence with many words (but the array will work with the first ten words, you can increase it if you want)
-Then, all words will be listed each one in a row.
-If one word is equal to a command, the program will tell you.
(Please note that all commands must start by different letters, in this quick version of the algorithm).
So, if you type "a tiger is sleeping in the jungle", the program will show these words one by one, but no command is detected.
If you type "a tiger is playing with a dog in the jungle", the program will list the words, recognizing "dog" as a command. Try "a lion and a cat are playing with a dog"
An improvement of the program should be:
- the ability to manage upper case and lower case characters, and even numbers.
- the detection of different commands that start with the same letter. Maybe using 1000+10*CODE z$(a,1) will allow space to use consecutive IF to check all commands starting by the same letter.
But for now, I believe this is a fast way to detect the different commands into a sentence.
Hope it is useful for your adventure!
Re: (BASIC) string handling advice
Yes, I'm definitely going to do something like this, nice idea! It will have the added benefit of the program then being able to (deliberately) confuse similar words (e.g. "plan" and "play" or "woman" and "wombat"), which will be perfect for what I have in mind.
www.fahnn.co.uk / Trine Michelson's Hot Parts: www.fahnn.co.uk/trine.txt / Big Deal (demo): http://www.fahnn.co.uk/big_deal.tap / tw@tter: http://www.fahnn.co.uk/[email protected]
Re: (BASIC) string handling advice
Thanks Ivan, very neat! It's not a million miles away from what I'm already doing (although your version is more compact) but because the input can potentially be quite long with a lot of terms to search, I'm finding it a little bit too slow at the moment. Really appreciate you doing this, though!
Oh, it's not an adventure
www.fahnn.co.uk / Trine Michelson's Hot Parts: www.fahnn.co.uk/trine.txt / Big Deal (demo): http://www.fahnn.co.uk/big_deal.tap / tw@tter: http://www.fahnn.co.uk/[email protected]
Re: (BASIC) string handling advice
I'd always start by splitting the input up into words by scanning along it and anything that's 'whitespace' (space, returns, commas, quotes, colons, end of the string etc.) becomes a point at which you break off a separate word and store it. Then you look up each word. Otherwise you end up with partial matches and think 'Scunthorpe' is a swearword... Which is is, in a way. Just not that way.
Re: (BASIC) string handling advice
I'd not even considered punctuation. Man, I am dense sometimes. However...Joefish wrote: ↑Fri May 24, 2019 1:08 pm I'd always start by splitting the input up into words by scanning along it and anything that's 'whitespace' (space, returns, commas, quotes, colons, end of the string etc.) becomes a point at which you break off a separate word and store it. Then you look up each word.
You've just given me the most amazing idea! My thinking about this has been backwards from the start but now I know exactly what course I'm going to take. Not only will it really speed things up, it's going to contribute massively to the "confused interpretation" thing I want to get going. I honestly can't thank you enough for this!
www.fahnn.co.uk / Trine Michelson's Hot Parts: www.fahnn.co.uk/trine.txt / Big Deal (demo): http://www.fahnn.co.uk/big_deal.tap / tw@tter: http://www.fahnn.co.uk/[email protected]