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

children.push_back(*this);プロファイリングによると、私のコードは、次のように関数を呼び出している行だけで約 40% の時間を費やしています。

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 内で一度にすべての状態が本当に必要かということです。それらをデフォルトの順序で 1 回または 2 回繰り返すだけであれば、ベクターは必要なく、必要に応じて生成するだけです。

本当に必要な場合は、次のステップです。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 に答える