Оптимальный способ введения данных в Trie? (C++)

Question

Мы работаем над программой для решения игры Boggle, и вся программа должна быть выполнена менее чем за 0,1 с. Мы вставляем словарь в наш код стандартным вводом (который длится 0,05 с, половина нашего максимального времени). Мы используем следующие функции для добавления слов в словарь, которые длятся 0,1 секунд каждые:

void Node::addWord(const char* word){ 
    const char idx = *word - 'a'; 
    if(!mChildren[idx]) mChildren[idx] = new Node(*word); 
    if(strlen(word) > 1) mChildren[idx]->addWord(word + 1); 
    else mChildren[idx]->setMarker(true); 
} 

void Trie::addDictionary(const vector<string>* aux){ 
    auto length = aux->size(); 
    Node* current = root; 
    for (size_t i = 0; i < length; i++) { 
    int len = aux->at(i).length(); 
    if (len >= 3 && len <= DIM*DIM + 1) { 
     current->addWord(aux->at(i).c_str()); 
    } 
    } 
} 

В этом случае, DIM = 4 (размерность платы NxN из Boggle) и всп вектора где все данные со стандартного ввода сбрасываются. Мы накладываем условие len> = 3, потому что нам нужны только слова с 3 буквами и более.

Любые идеи для повышения скорости этих функций?

Answer 1

Лучший способ повысить скорость этой функции - запустить на них профилировщик. Я бы не стал оптимизировать такой код, пока вы не запустили профайлер против него.

Это, как говорится, будет моим прогнозом, что если вы запустите профилировщик, вы обнаружите, что большая часть вашего времени выполнения (например, 90%) будет находиться в new Node(*word). Распределение кучи медленнее по сравнению с другими операциями, которые вы делаете. Как медленно? Это зависит от вашей платформы, поэтому вам нужно профилировать, чтобы найти горячие точки. То, что потребляет большое количество времени на одной платформе, может потреблять очень мало времени на других.

Запустите профилировщик, определите, верно ли мое требование. Если это правильно, я рекомендую пул распределять узлы, чтобы уменьшить количество распределений, которые должны произойти.