3

在我目前的项目中，我尽最大努力坚持过早优化是万恶之源的原则。但是，现在代码已经过测试，是时候进行优化了。我做了一些分析，结果发现我的代码将近 20% 的时间都花在了一个函数中，在这个函数中它找到了所有可能的孩子，把它们放在一个向量中，然后返回它们。请注意，我正在优化速度，内存限制不是一个因素。

现在函数看起来像这样：

void Board::GetBoardChildren(std::vector<Board> &children)
{
    children.reserve(open_columns_.size()); // only reserve max number of children

    UpdateOpenColumns();

    for (auto i : open_columns_)
    {
        short position_adding_to = ColumnToPosition(i);
        MakeMove(position_adding_to); // make the possible move
        children.push_back(*this); // add to vector of children
        ReverseMove(); // undo move
    }
}

根据分析，我的代码花费了大约 40% 的时间就在children.push_back(*this);我这样调用函数的行上：

std::vector<Board> current_children;
current_state.GetBoardChildren(current_children);

我在想，由于可能的孩子的最大数量很小（7），只使用一个数组会更好吗？还是我不能做很多事情来优化这个功能？

4

2 回答 2

2

从您对我的评论的回复来看，似乎大部分时间都花在了抄板

children.push_back(*this);

您需要找到一种方法来避免制作所有这些副本，或者找到一种使它们更便宜的方法。

简单地将向量更改为数组或列表可能不会对性能产生任何影响。

于 2012-11-25T22:44:36.077 回答
1

最重要的问题是：你真的需要同时在 current_state 中的所有状态吗？如果您只是按默认顺序对它们进行一次或两次迭代，则不需要向量，只需按需生成它们即可。

如果你真的需要它，这是下一步。由于Board复制成本很高，DifferenceBoard因此只跟踪差异可能会更好。伪代码：

struct DifferenceBoard { // or maybe inherit from Board that a DifferenceBoard
                         // can be built from another DifferenceBoard
  Board *original;
  int fromposition, toposition;
  State state_at_position;

  State get(int y, int x) const {
    if ((x,y) == fromposition) return Empty;
    if ((x,y) == toposition  ) return state_at_position;
    return original->get();
  }
};
于 2012-11-25T23:02:24.113 回答