C++ Trie 搜索性能

Question

所以我创建了一个包含大量数据的 trie，我的搜索算法非常快，但我想看看是否有人知道我如何才能让它更快。

    bool search (string word)
{
    int wordLength = word.length();
    node *current = head;
    for (unsigned int i=0; i<wordLength; ++i)
    {
            if (current->child[((int)word[i]+(int)'a')] == NULL)
                    return false;
            else
                    current = current->child[((int)word[i]+(int)'a')];
    }
    return current->is_end;
}

Answer 1

在性能方面看起来不错，除了这些花絮:

• 将函数参数声明为 const string&(而不仅仅是 string)，以避免不必要的复制。
• 您可以提取 if 前面的公共(public)子表达式 current->child[((int)word[i]+(int)'a')] ，以避免重复并使代码稍微变小，但任何称职的编译器无论如何都会为您进行优化。

---

“风格”建议:

• 如果 word 包含“a”下方的字符(例如大写字母、数字、标点符号、换行符等...)怎么办？您需要验证 输入以避免访问错误的内存位置和崩溃。这也不应该是 -(int)'a' 而不是 + (我假设你只想支持一组有限的字符:'a' 和以上)？
• 将 wordLength 声明为 size_t(或更好的 auto)，但这对于任何实际长度的字符串都不重要(甚至可能会伤害如果 size_t 大于 int，性能略有下降)。 i 也是如此。