Android Code Snippet Search algorithms (and code) on ordered lists

These days I needed an algorithm to quickly search for it on an archive of 280000 strings (sorted alphabetically).
So I reckoned that at school I had studied Binary Search.

Allows you to find (or ensure that you are not listed) a key with a fixed and minimum access to the archive.
Access Number: Log2 (TotalNumberKey)

I use the "BinarySearch" Sub recursively

Dim Dictionary as List = File.ReadList(File.DirInternal,"MyDict.txt")
Dim MyWord as String = "Hallo"

BinarySearch(MyWord,0,Dictionary.Size-1)


Sub BinarySearch(Word As String, Mn As Int, Mx As Int) As Boolean
    Dim MD As Int = ((Mx+Mn)/2)
    Dim PM As String = Dictionary.get(MD)

    If Mx<Mn Then Return False

    If PM=Word Then
        Return True
    Else if PM.CompareTo(Word)>0 Then
        Return BinarySearch(Word,Mn,MD-1)
    Else
        Return BinarySearch(Word,MD+1,Mx)
    End If

End Sub

Exponential Search. post #4

 

[Star-Dust]

Yes, BinarySearch works only if the key list is sorted alphabetically
To sort a list quickly you can see the implementation of different algorithms on: https://www.b4x.com/android/forum/t...hms-teaching-with-basic4android.8548/#content

Int = ((Mx+Mn)/2) becomes <=1.

I try this:

Sub Dicotomica2(Parola As String, Mn As Int, Mx As Int) As Boolean
    If Mx>Mn Then
        Dim MD As Int = ((Mx+Mn)/2)
        Dim PM As String = Dizionario.get(MD)
     
        If PM=Parola Then
            Return True
        Else if PM.CompareTo(Parola)>0 Then
            Return Dicotomica2(Parola,Mn,MD-1)
        Else
            Return Dicotomica2(Parola,MD+1,Mx)
        End If
    Else If Mx<Mn Then
        Return False
    Else ' Mx=Mn - 1 element
        If Dizionario.get(Mn)=Parola Then Return True Else Return False
    End If
End Sub

But is slower (about +3,5%)

 

[Star-Dust]

I added a variant that is called Exponential Search.
With the power elevation calculation, find the list portion to work on and on that portion apply the Binary Search.
It did not give me higher performance, especially on small archives.
But it is an alternative.

The sub SearchBinary in this code isn't recursive

Sub Exponential_Search (Word As String,Size As Int) As Boolean
    Dim Bound As Int = 1
  
    If Size=0 Then Return False
  
    Do While (Bound < Size) And (Word.CompareTo(Dictionary.Get(Bound-1))>0)
        Bound=Bound*2
    Loop
  
    Return Binary(Word,(Bound/2)-1,Min(Bound-1,Size-1))
End Sub

Sub Binary(SearchWord As String, Mn As Int, Mx As Int) As Boolean
    Dim MD As Int = ((Mx+Mn)/2)
    Dim PM As String = Dictionary.get(MD)
  
    If Mx<Mn Then Return False
  
    If PM=Parola Then
        Return True
    Else if PM.CompareTo(SearchWord)>0 Then
        Return Binary(SearchWord,Mn,MD-1)
    Else
        Return Binary(SearchWord,MD+1,Mx)
    End If
  
End Sub

 

[Star-Dust]

In my specific case I was looking for an algorithm to see if words from a series of anagrams of some letters might be existing words.
A quick algorithm would allow me to discard anagrams that do not avenge meaning and identify existing words.

It's an inspiration to the library that created LordZenzo these days. His library is a fraction of a second having received letters, creates anagrams, and selects the existing palettes in the dictionary.
Obviously none of these algorithms arrive at the performance declared by @LordZenzo about its library.

I have thought that it uses 26 different lists, each list only has the words that start with an alphabet letter. Considering that anagram letters can range from 2 to a maximum of 10, the search will be performed only in the letters lists. So speeding up the search.

But it is my hypothesis I do not know for sure. but you can find his library in these links: https://www.b4x.com/android/forum/threads/gilowordsgamesutils.83394/

Anyway, the result is that I've developed a STANDOUT app that floats on the desktop on other apps or games that helps me find solutions in word games such as RUZZLE.


(I don't always develop for work every now and then for fun too)

Errata Corrige: The library is developed @LordZenzo