Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / Need help optimizing search loops

Author
Message
Kensupen
23
Years of Service
User Offline
Joined: 19th Sep 2002
Location: United States
Posted: 12th Aug 2003 13:03
Link
Ok, what I'm trying to do is make an anagrams game.
I have 4 word lists with these amounts of words
3 letters=532
4 letters=1751
5 letters=2457
6 letters=3274

The game picks one six letter word at random then has to find all the words it can make with those six letters from each list.

The way I'm doing it right now takes 54,921 for...next loops to find every single word. I need to see if there is a way that I can streamline the process and get this down to as few loops as possible.

The way I'm doing it right now, is that it sorts each word in the list from a to z as it goes through looking for a match, but since there are many combinations of 3 letters you can try with 6 to choose from, this makes it so that it's 20 combinations times 532 words just to find all the 3 letter ones. Then 15*1751, 6*2457 and finally 3274. (Giving the 54,921 total) Can anyone think of a better way to do this?

-Kensupen
Nerdsoft Creations - Lead Programmer
System Specs: AMD XP 1700+, WinXP Home, 1GB PC133 ram and Radeon 9500 using DX9
Back to top
Profile PM Website
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 12th Aug 2003 16:16
Link
Try taking all the letters from a word, then sort them alphabetically. This becomes your sort key. Repeat for each word, then use these new 'words' to sort the original list, maybe in a 'type' like this:

type WordList
Key as string
Word as string
endtype

Then when you need to search for a word, you can select (sorted) combinations of the letters you are looking for to binary search your array.
Back to top
Profile PM Email Website
BatVink
Moderator
23
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 12th Aug 2003 17:07
Link
I don't see this as a problem. I have a program that has a series of loops that iterate 36,000 times, and it does it in under 2 seconds on a 1Ghz PC.

There are 2 very important factors:
The number of loops are less important than the code in the loop. Make the code as efficient as possible. For example, 100 lines of code evaluates to 5.4 million line executions. Reduce it to 80, you've streamlined the program execution by 1 million lines of code.

Reduce screen updates, this is the biggest factor in slowing down your loop. For example, If you update the screen every loop at a screen refresh of 60Hz, you reduce the number of iterations to 60 / second. I'm getting around 18,000 /second (300 x faster), simply because I have no need to update the screen at this point in the program.

Hope this helps.

Thanks in advance.
All the Best,
StevieVee
Back to top
Profile PM Email
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 12th Aug 2003 20:41
Link
Instead of going through each entire list, you can use a binary search on the list which is quite efficient.

(1) You're saying each list is alphabetically sorted, which is good.
(2) You have the 3 letter word (for example) to check agains the list.

With that you can perform a binary search. What you need to do is start in the middle of the list, so:
(1) Get the number of elements in the list.
(2) Divide this number by 2.
(3) Access the list at this position (so if it was 500 words, then you'll access the list at 250).
(4) Compare the word you want to check with this word.
(5) If its not the same, then do comparison. Is the word in the list bigger than the word you're checking? (ie. does it appear later on in the alphabet?) Or is it smaller (appear before in the alphabet)
(6) Depending on whether its bigger or small, you can eliminate half the list from the search. If you're seaching for "cat" and the word at position 250 is "ditch" then you know the words following ditch (the second half of the list) cannot contain "cat".
(7) Select this half of the list, and return to step 1.

By doing this, instead of searching through 500 words, you search through a miximum of 9 words.

It's just a tad quicker.

Insiiiiiiiiiiiiiiiiiiiiiiiide!
Back to top
Profile PM
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 12th Aug 2003 20:52
Link
Might look something like this, depending on how db handles string comparisons and such.

searchword$="cat"
wordfound = 0
liststart = 1
listend = 500
repeat
`Get position
searchposition = int((listend-liststart)/2)
`Compare strings
if WordList$(searchposition) = searchword$
wordfound = 1
else
if WordList$(searchposition) > searchword$
`Word in list is bigger than search word, so last half of list is crap
listend = searchposition - 1
else
`Word in list is smaller than search word, so second half is shit
liststart = searchposition + 1
endif
endif
`Check to make sure start and end arent the same (i.e. whole list searched)
If liststart = listend or liststart > listend
wordfound = -1
endif
until wordfound <> 0

`At this point, wordfound = 1 is the word was found or -1 if the word was not found


I just wrote that in here, so it's not tested, but it's the shell of it.

Insiiiiiiiiiiiiiiiiiiiiiiiide!
Back to top
Profile PM
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 12th Aug 2003 20:55 Edited at: 12th Aug 2003 20:58
Link
And just to segrigate my post even more, I stuck the same source in the source section here where it may be more clear.

Btw, didn't notice Ian suggested a binary search already.

Insiiiiiiiiiiiiiiiiiiiiiiiide!
Back to top
Profile PM
Kensupen
23
Years of Service
User Offline
Joined: 19th Sep 2002
Location: United States
Posted: 13th Aug 2003 03:59
Link
Well, to clear things up a bit.

I have 4 separate word lists. One is all 3 letter words, 4 letter words, 5 letters and 6 letters. I have each of them stored in their own array.

Now, lets say the PC picks the word "WANTED" It now has to find every word in the 3 letter array it can make with the letters in "WANTED" What I did so far is sort the word into alphabetic order to make less searches. "ADENTW" is the result. Next I had to find out what all possible combinations there are of 3 letters using that. If you think of it in positions, the word is simply 123456.

Here's the combinations I found that doesn't use the same 3 letters:
123,124,125,126,134,135,136,145,146,156
234,235,236,245,246,256
345,346,356
456
This gives a total of 20 combinations possible.

Right now I have a brute force method of finding all possible matches from the 3 letter word array. It does a for...next loop from 0 to 531 (All the words in the array) sorting each word in the array into alphabetic order. Then it checks each one of the 20 combinations against the current word in the list. The reason I sorted the words before the checks is so that I wouldn't have to try EVERY single combination of 3 letters from 6. That would be a whole lot.

The only other thing I can think of trying is to pre-sort all the lists by re-ordering each word alphabetically then sort the entire list alphabetically and use a 2 dimentional array that has the words ordered first then the "real" word next. But, I'd have to find a way to not have to search every word in the list for speed. This is where I'm stuck.

-Kensupen

Nerdsoft Creations - Lead Programmer
System Specs: AMD XP 1700+, WinXP Home, 1GB PC133 ram and Radeon 9500 using DX9
Back to top
Profile PM Website
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 13th Aug 2003 06:50
Link
Whaaa??? I just spent 15 minutes earlier explaining a binary search which'll do the job perfectly.

Work out your different possible letter combinations for the words, like you have.
Sort the word lists alphabetically, like you have.
Then for each possible letter combination, search the appropriate array using the binary search.

Using this method, the max number of search loops for your word "wanted" will be:
Maximum possible searches in a 532 element array = 10
Maximum possible searches in a 1751 element array =11
Maximum possible searches in a 2457 element array =12
Maximum possible searches in a 3274 element array =12
3 letter array - 9 searches x 10 3 letter words = 90
4 letter array - 11 searches x 6 4 letter words = 66
5 letter array - 12 searches x 3 5 letter words = 36
6 letter array - 12 searches x 1 6 letter word = 12

Minimum possible search loops = 20
Maximum possible search loops = 204

You can't complain at getting 54,921 loops down to 204 search loops.

Insiiiiiiiiiiiiiiiiiiiiiiiide!
Back to top
Profile PM
Kensupen
23
Years of Service
User Offline
Joined: 19th Sep 2002
Location: United States
Posted: 13th Aug 2003 07:43
Link
Maybe I'm just slow, but I don't get the code you posted. I'll have to play around with it and try to see how it works. I understand that it's trying 1/2 the total list, but that doesn't explain how you figure getting 54k loops down to 200. I'll see if I can figure out your code.

-Kensupen

Nerdsoft Creations - Lead Programmer
System Specs: AMD XP 1700+, WinXP Home, 1GB PC133 ram and Radeon 9500 using DX9
Back to top
Profile PM Website
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 13th Aug 2003 10:26 Edited at: 13th Aug 2003 10:30
Link
The basic idea is that you keep splitting the list of words in half until you either get a match, or don't find what you're looking for.

Look at the middle element.

Is what you are looking for less than this (in the first half of the list)?

In this case this is your new 'top' position, otherwise, it's you're new 'bottom' position.

Repeat until your 'top' <= 'bottom'

In your case, you'll need to add a few steps, because there can be many matches for the same combination of letters. As soon as you find a match, move back through the list until you don't find a match. Move forward 1 again, and this is the start of your list. Then repeat in the forward direction.

To explain fallouts numbers, imagine that you have a list of 100 words. You check the middle one (1) find that what you're looking for is in the first half ... you've already eliminated the top half of the list, leaving 50.

It goes like this:
1, eliminate 50, leaving 50
2, eliminate 25, leaving 25
3, eliminate 12, leaving 13
4, eliminate 6, leaving 7
5, eliminate 3, leaving 4
6, eliminate 2, leaving 2
7, check against the first. If it's a not a match, it's the other one.

Maximum worse case is 7 matches for 100 entries.
Back to top
Profile PM Email Website
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 13th Aug 2003 15:05
Link
Yeah, IanM's having a bash too, but sometimes it's tricky to get the concept across with just words. Maybe a search on Google or something for "Binary search algorithm" might through up a lot more detail? Either way, it does seem like the solution you want.

I'll try and explain the concept in another way.
-You have the alphabet stores in an array, and you want to find if the letter "R" exists in that list (we all know it does, but assume we dont). The array is obviously 26 elements long.
-You could do a for loop 1 to 26 and check each element (this is what you're doing, correct?) But we'll use a binary search instead.

Step 1 - Select the middle of the list. If it's 26 items long, the middle is 13, which is the letter "M".
Step 2 - Is this the letter we're looking for? Nope. Is it bigger than the letter we're looking for? Nope. Is it smaller than the letter we're looking for? Yep ... M is smaller than R.
We now know that if R is within the array, it must be in a position greater than 13, so we can ignore all the array positions before 13.
Step 3 - Our new lower search boundary is 14. Our upper search boundary is still 26.
Step 4 - The middle of 26 and 14 is 20. The letter at position 20 is "T"
Step 5 - Is this the letter we're looking for? Nope. Is it bigger than the letter we're looking for? Yes - T is bigger than R. So we know if R exists in the array, it must be between 14 and 19, as all positions bigger than 20 (holding T) are larger than the value R.
Step 6 - Lower search boundary is still 14. Upper search boundary is now 19.
Step 7 - The middle is 16 (rounded down because the exact middle is a .5 number). Which is "P". Repeating all the processes above we then get.
Step 8 - Numbers 17 - 19
Step 9 - Middle = 18 (rounded down) This is "R" .. so it's been found.

If we'd got down to where the upper and lower boundary equalled the same number, with no match, then we end the search knowing the is no match in the array.

If you look at all the "middle number is" parts, that's how many times you've actually accessed the array. In this example it's 4 times. If you search from A->R using a 4 loop, it'd take 18 times. Binary searches come into their own in large searches though.

If you have 1000,000 elements, you might have to for loop through 1000,000 times, but using a binary search, the maximum you'd have to for loop through is 20 times. So it's the daddy of searches.

Hope that makes it more clear, otherwise I'm stumped.

Insiiiiiiiiiiiiiiiiiiiiiiiide!
Back to top
Profile PM
Kensupen
23
Years of Service
User Offline
Joined: 19th Sep 2002
Location: United States
Posted: 13th Aug 2003 23:56
Link
Ok, I figured it out and went from 10,000+ loops to 260 on my 3 letter word list. After plaing around with your code, I modified it to work the way I needed it to. It's the same basic idea, I just wrote it a bit different.

The reason I was getting confused is because I was only re-ordering each word alphabetically, not the entire list. So, in order for this to work, I had to make a 2 dimensional array and re-order each word, then the entire list. I kept the "real" word in the first part and the re-ordered words in the second part.

My problem is I'm trying to make this game for DB and eVB. When I ported my code to eVB, it just gets stuck in the while loop. I think it's the way I re-wrote the code.

-Kensupen

Nerdsoft Creations - Lead Programmer
System Specs: AMD XP 1700+, WinXP Home, 1GB PC133 ram and Radeon 9500 using DX9
Back to top
Profile PM Website
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 14th Aug 2003 01:00
Link
Ahh, I see the confusion. Yeah, your word arrays need to be sorted alphabetically. Sounds like it's a touch faster now though. Glad I could help.

Insiiiiiiiiiiiiiiiiiiiiiiiide!
Back to top
Profile PM
Kensupen
23
Years of Service
User Offline
Joined: 19th Sep 2002
Location: United States
Posted: 14th Aug 2003 14:00
Link
I also found the problem in the eVB code. when you delcare a variable, it's any type. the first thing I assigned to it was a float value so it became a float. After I converted it to an INT, it worked. Load times went from 23 secongs to just under 2 so it's now playable. Yeah! Thanks for all the help and patience.

-Kensupen

P.S. I'm going to add bigger arrays of words and see how much slower it is. I'm guessing not much slower at all.

Nerdsoft Creations - Lead Programmer
System Specs: AMD XP 1700+, WinXP Home, 1GB PC133 ram and Radeon 9500 using DX9
Back to top
Profile PM Website
Fallout
23
Years of Service
User Offline
Joined: 1st Sep 2002
Location: Basingstoke, England
Posted: 14th Aug 2003 14:32
Link
"Option Explicit" is the key. I wish they had that command in DB to force you to declare all variables. Would save 50% of all programming errors, I think.

Insiiiiiiiiiiiiiiiiiiiiiiiide!
Back to top
Profile PM
Back to top

Login to post a reply

Server time is: 2026-07-23 02:30:02
Your offset time is: 2026-07-23 02:30:02