C++ Trie搜索性能

所以我做了一個擁有相當大量數據的trie，我的搜索算法相當快，但我想看看是否有人對我如何更快地實現它有所瞭解。C++ 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; 
}

來源

2012-03-01 that_guy

看起來良好的性能的角度來看，除了這些花絮：

聲明函數參數作爲const string&（而不是僅僅string），以避免不必要的複製。
您可以提取if前面的常見子表達式current->child[((int)word[i]+(int)'a')]，以避免重複，並使代碼略小，但任何值得其鹽值的編譯器都會爲您進行優化。

「風格」的建議：

如果什麼word包含以下字符 'a'（如大寫字母，數字，標點符號，新的生產線等）？您需要驗證輸入以避免訪問錯誤的內存位置和崩潰。也不應該這是-(int)'a'而不是+（我假設你只是想支持一個有限的字符集：'a'和以上）？
聲明wordLength爲size_t（或更好，但auto），但是這不是任何實際長度的字符串重要（甚至可能會影響性能略微如果size_t大於int）。同上i。

來源

2012-03-01 03:00:19

我使用+（int）a，因爲有值低於 – 2012-03-01 03:34:13

的字符@that_guy：在這種情況下，您不應該向「word [i]」添加任何內容。決定有效範圍，並（可選）將範圍從「word [i]」減去範圍中的最小值，從0開始。 – tom 2012-03-01 04:22:30

bool search (string word)

調用這個函數，串word將被複制，下面類型的功能會更快。

bool search (const string &word)

或

bool search (const char *word)

來源

2012-03-01 02:57:35 kamae

C++ Trie搜索性能

回答

相關問題