Scrabble Dictionary

[bplus]

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.

[SMcNeill]

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 Function

[bplus]

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 Function

[PhilOfPerth]

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.

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".

[bplus]

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

But I am sure I encounter my worst case more often.