在 Trie 中引入数据的最佳方式？ (C++)

Question

我们正在开发一个解决Boggle 游戏的程序，整个程序必须在0.1s 以内执行。我们通过标准输入（持续 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（是 Boggle 的 NxN 板的尺寸）并且 aux 是一个向量，其中转储了来自标准输入的所有数据。我们强加了 len >= 3 的条件，因为我们只想要包含 3 个或更多字母的单词。

有什么提高这些函数速度的想法吗？

Answer 1

提高这些函数速度的最佳方法是运行在它们上面安装分析器。我不会考虑像这样优化代码，除非你运行一个分析器反对它。

话虽如此，我的预测是，如果您运行分析器，您会发现运行的大部分时间（例如 90%）将在 new Node(*word)。与您正在执行的其他操作相比，堆分配速度较慢。有多慢？这取决于您的平台，这就是为什么您必须分析以查找热点的原因。在一个平台上消耗大量时间的东西在其他平台上可能只消耗很少的时间。

运行一个分析器，确定我的说法是否正确。如果它是正确的，那么我建议池分配节点以减少必须发生的分配数量。

在 Trie 中引入数据的最佳方式？ (C++)

Optimal way to introduce data in a Trie? (C++)

c++

boggle