C++ Trie search performance

Question

Итак, я сделал трюк, который содержит довольно большой объем данных, мой алгоритм поиска довольно быстр, но я хотел посмотреть, есть ли у кого-нибудь представление о том, как я мог бы сделать это быстрее.

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), чтобы избежать ненужного копирования.
• Вы можете извлечь общее подвыражение current->child[((int)word[i]+(int)'a')] перед if, чтобы избежать повторения и сделать код немного меньше, но любой компилятор, достойный его соли, сделает эту оптимизацию для вас в любом случае.

---

"Стиль" предложения:

• Что делать, если word содержит символ ниже 'а' (например, буквы, цифры, знак препинания, новой строки и т.д. ...)? Вам необходимо указать , чтобы подтвердить вход, чтобы избежать доступа к неправильному местоположению памяти и сбоям. Также не должно быть -(int)'a' вместо + (Предполагаю, вы просто хотите поддерживать ограниченный набор символов: «а» и выше)?
• Объявить wordLength в size_t (или еще лучше auto), но это не имеет значения для строк любой практической длины (может даже повредить производительность немного, если size_t больше int). То же самое для i.

Answer 2

bool search (string word) 

Вызов этой функции, строка word будет скопировано, тип функции ниже будет быстрее.

bool search (const string &word) 

или

bool search (const char *word)