C ++ Trie Search производительность - PullRequest
Новая
       17

C ++ Trie Search производительность

0 голосов
/ 01 марта 2012

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

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

Ответы [ 2 ]

2 голосов
/ 01 марта 2012

Выглядит неплохо с точки зрения производительности, за исключением следующих моментов:

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

Рекомендации по «стилю»:

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

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

bool search (const string &word)

или 

bool search (const char *word)
...