具有大列表的更快搜索协议 (c++)

Question

大列表的更快搜索协议？你好，感谢阅读我的 post。我正在制作一些简单的自动完成软件，将输入的单词与英语词典中与该单词的字母序列相匹配的每个单词进行比较。该词典包含 400,000 个元素，因此如您所料，简单搜索需要等待很长时间。

                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]);
                    }
                }

上面的代码可能是运行时优化效率最低的，但我尝试了一些其他的东西，比如为所有 27 个字母创建一个位移变量，然后将其添加到 i。并将最大值减少到下一个字母开头（如果第一个字母的索引，比如 r，是 400，并且以 s 开头的第一个字母的索引是 800，那么我会将范围设置在 400 到 800 之间而不是 0 - 1,500 但它仍然很慢）。任何帮助将不胜感激

Answer 1

整理你的字典。然后你可以二进制搜索这个词，因为你只匹配前缀（即你不是试图通过键入“ell”来查找“hello”）。

这也是非常低效的：

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

那个一脸无辜的std::string::substr()每次都分配内存！您可以使用 std::string::compare() 在不分配内存的情况下进行相同的比较，这将使这部分速度提高约 10 倍。

具有大列表的更快搜索协议 (c++)

faster search protocol with large list (c++)

c++

arrays

string

search

vector