검색을위한 C++ 벡터 최적화

Question

현재 프로젝트에서 조숙 한 최적화가 모든 악의 근원이라는 원칙을 고수하기 위해 최선을 다했습니다. 그러나 이제 코드가 테스트되었으며 최적화 할 시간입니다. 프로파일 링을했는데 코드가 가능한 모든 자식을 찾아 벡터에 넣은 다음 반환하는 함수에서 시간의 거의 20 %를 소비합니다. 메모로서, 나는 속도를 위해 최적화하고있다, 메모리 제한은 요인이 아니다.

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

:

이

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 %를 지출 :

오른쪽 이제 기능은 다음과 같습니다

가능한 최대 어린이 수가 적기 때문에 (7) 배열을 사용하는 것이 좋을까요? 아니면이 기능을 최적화하기 위해 할 수있는 톤이 없습니까? 내 의견에 대한 응답에서

Answer 1

, 당신이 모든 사본을 피하는 방법 또는 방식을 찾아야 대부분의 시간

children.push_back(*this); 

에서 보드를 복사 소요되는 가능성이 높다 보인다 그것들을 더 싸게 만드십시오.

단순히 벡터를 배열 또는 목록으로 변경하면 성능에 아무런 영향을 미치지 않을 것입니다.

Answer 2

가장 중요한 질문은 다음과 같습니다. 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(); 
    } 
};