2

我们正在开发一个解决 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（是 Boggle 的 NxN 板的维度）并且 aux 是一个向量，其中来自标准输入的所有数据都被转储。我们强加了 len >= 3 的条件，因为我们只想要包含 3 个或更多字母的单词。

有什么想法可以提高这些功能的速度吗？

4

1 回答 1

2

提高这些函数速度的最佳方法是在它们上运行分析器。在您针对它运行分析器之前，我不会考虑优化这样的代码。

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

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

于 2016-11-01T21:21:56.943 回答