faster search protocol with large list? hello and thanks for reading my post. I'm making some simple autocomplete software that compares the word being entered to every word that matches that word's sequence of letters in the English dictionary. The dictionary contains 400,000 elements so as you could expect it makes for a very long wait time for simple searches.

                for (int j = 0; j < list.size(); j  )
                {
                    if (list[j].length() >= input[input.size()-1].length() && input[input.size() - 1] == list[j].substr(0, input[input.size() - 1].length()))
                    {
                        suggestions.push_back(list[j]);
                    }
                }

The code above is probably the least efficient for runtime optimization, but I tried some other things like creating a displacement variable for all 27 letters and then adding that to i. and reducing the maximum to the next letter start (if the index of the first letter, say r, is 400, and the index of the first letter beginning with s is 800, then I would set the range between 400 and 800 instead of 0- 1,500 but it still was slow). Any help would be appreciated

CodePudding user response：

Sort your dictionary. Then you can binary search for the word, since you're matching prefixes only (i.e. you aren't trying to find "hello" by typing "ell").

Also this is very inefficient:

input[input.size() - 1] == list[j].substr(0, input[input.size() - 1].length())

That innocent-looking std::string::substr() allocates memory every time! You can use std::string::compare() to do the same comparison without memory allocation, which will make this part ~10x faster.