+- QB64 Phoenix Edition (https://qb64phoenix.com/forum)
+-- Forum: QB64 Rising (https://qb64phoenix.com/forum/forumdisplay.php?fid=1)
+--- Forum: Code and Stuff (https://qb64phoenix.com/forum/forumdisplay.php?fid=3)
+---- Forum: Programs (https://qb64phoenix.com/forum/forumdisplay.php?fid=7)
+---- Thread: Scrabble Dictionary (/showthread.php?tid=1170)
Pages:
1
2
RE: Scrabble Dictionary - bplus - 11-24-2022
(11-24-2022, 04:12 AM)PhilOfPerth Wrote: I don't really see the point of Random Access for the words; probably I'm missing something again.
Maybe a quicksort routine would help speed things up though.
Anyway, I'm half-way through creating matching Meanings files, so I'll stay with that for now.
With Random Access I can use Binary Search instead of running through every word in file to find a word. Every time I test a word I reduce the number of words to search by one half.
You split up the words into letter files to reduce search times.
RE: Scrabble Dictionary - SMcNeill - 11-24-2022
From my opening post, it uses a binary search for our word array:
Code: (Select All)
Function BinaryStringSearch (search$, Array() As String)
'These routines work with actual indexes, so we can search from Array(-10 to 10), if we want to.
'When the search string is found, it'll return a value = to the index proper.
'When it's not found, it'll return a value LESS THAN the LBOUND limit of the array,
'And the point where the string WOULD'VE appeared, if it existed, is after the shared variable LastIndex
BinaryStringSearch = BinaryStringSearchSome(search$, Array(), LBound(Array), UBound(Array))
End Function
Function BinaryStringSearchSome (search$, Array() As String, StartIndex As Long, EndIndex As Long)
'These routines work with actual indexes, so we can search from Array(-10 to 10), if we want to.
'When the search string is found, it'll return a value = to the index proper.
'When it's not found, it'll return a value LESS THAN the LBOUND limit of the array,
'And the point where the string WOULD'VE appeared, if it existed, is after the shared variable LastIndex
min = StartIndex
max = EndIndex
Do
gap = (max + min) \ 2
compare = _StrCmp(search$, Array(gap))
If compare > 0 Then
min = gap + 1
ElseIf compare < 0 Then
max = gap - 1
Else
BinaryStringSearchSome = gap
Exit Function
End If
If max - min < 1 Then
If search$ = Array(min) Then
BinaryStringSearchSome = min
Else
BinaryStringSearchSome = LBound(Array) - 1
If search$ < Array(min) Then
LastIndex = min - 1
Else
LastIndex = min
End If
End If
found = -1
End If
Loop Until found
End FunctionRE: Scrabble Dictionary - bplus - 11-24-2022
Here's mine for an opened RA file of which I already know Word count, 32 is maximum word length (guessed):
Code: (Select All)
Function findW& (wd$)
Dim As Long lo, hi, m
Dim wrd As String * 32
lo = 1: hi = 279422
While lo <= hi
m = (hi + lo) / 2
Get #1, m, wrd
w$ = _Trim$(wrd)
If w$ = wd$ Then
findW& = m: Exit Function
ElseIf w$ < wd$ Then
lo = m + 1
ElseIf w$ > wd$ Then
hi = m - 1
End If
Wend
End FunctionRE: Scrabble Dictionary - PhilOfPerth - 11-24-2022
(11-24-2022, 04:29 AM)bplus Wrote:I just ran a test for worst-case read and compare for the largest wordlists file (S, with 31947 items) and it took 1.04 seconds for the test, so I don't think I'll worry about changing to RA. I will look at RA though, for my own "education".(11-24-2022, 04:12 AM)PhilOfPerth Wrote: I don't really see the point of Random Access for the words; probably I'm missing something again.
Maybe a quicksort routine would help speed things up though.
Anyway, I'm half-way through creating matching Meanings files, so I'll stay with that for now.
With Random Access I can use Binary Search instead of running through every word in file to find a word. Every time I test a word I reduce the number of words to search by one half.
You split up the words into letter files to reduce search times.
RE: Scrabble Dictionary - bplus - 11-24-2022
Worst case for me with RA, I have to test 19 words!
Code: (Select All)
words = 279422
While words > 1
words = words / 2
count = count + 1
Wend
Print count