홍수 채우기 알고리즘을보다 효율적으로 만들려면 어떻게해야합니까?

Question

코드에 채워진 셀의 숫자를 반환하는 플러드 채우기 기능이 있습니다. 하지만 너무 느리게, 내 A * 길 찾기 알고리즘이 지수 적으로 빠릅니다. 스 니펫은 다음과 같습니다.

bool withinBoundaries(_2D::Point p) { 
//cerr << "Checking if x: " << p.x << " y: " << p.y << " is within boundaries" << endl; 
if (p.x <= 29 && p.y <= 19 && p.x >= 0 && p.y >= 0) { 
    return true; 
} 
return false; 
} 


bool canMove(_2D::Point point, _2D::Point offset, map<pair<int, int>, bool> gameGrid) { 
if (!gameGrid[(point + offset).toPair()] && withinBoundaries(point + offset)) return true; 
else return false; 
} 

int floodFillGetArea(_2D::Point point, map<pair<int, int>, bool> gameGrid) { 
    map<pair<int, int>, bool> checked; 
    map<pair<int, int>, bool> gameGridCopy = gameGrid; 
    deque<_2D::Point> openPoints; 
    openPoints.push_back(point); 
    int count = 0; 

    while (!openPoints.empty()) { 
    _2D::Point curPoint = openPoints.back(); 
    openPoints.pop_back(); 
    if(checked[curPoint.toPair()]) break; 
    gameGridCopy[curPoint.toPair()] = true; 
    count++; 
    if (canMove(curPoint, _2D::Point::UP(), gameGridCopy)) { 

     openPoints.push_back(curPoint + _2D::Point::UP()); 
    } 
    if (canMove(curPoint, _2D::Point::RIGHT(), gameGridCopy)) { 
     openPoints.push_back(curPoint + _2D::Point::RIGHT()); 
    } 
    if (canMove(curPoint, _2D::Point::DOWN(), gameGridCopy)) { 
     openPoints.push_back(curPoint + _2D::Point::DOWN()); 
    } 
    if (canMove(curPoint, _2D::Point::LEFT(), gameGridCopy)) { 
     openPoints.push_back(curPoint + _2D::Point::LEFT()); 
    } 
    checked[curPoint.toPair()] = true; 
} 
return count; 
} 

이것은 1 초마다 노드를 검사합니다. 왜 그렇게 느립니다? 그리고 _2D :: Point는 int x와 int y를 가진 객체 일뿐입니다. 또한 이미 확인 된 것으로 레이블이 지정되어있는 경우 열린 노드를 만듭니다. 그 이유는 무엇입니까?

Answer 1

초보자는 std::map 개체를 아무 것도 6 번 복사합니다.

가 CONST 기준으로지도 객체를 전달하기보다는 O 소요 (= 복사) 값

Answer 2

는 (지도 대신 불리언 차원 배열하려고 할로 전달할 시도 (보고 N) 조작 로그 위로) "gameGrid"개체에 대한? 어레이가 옵션이 아니면 해시 테이블로 전환하면 비슷한 성능을 낼 수 있습니까?

지도에 1024 개의 점이있는 경우 벤치 마크 속도에 10-11을 곱해야합니다.

충분하지 않으면 1, 4, 16, 20, 20, 20, 16, 4, 1, 1, 4, 16, 2, 4를 계산하기 위해 여러 스레드와 여러 단계 (동기화)를 수행 할 수 있습니다. ... 한 번에 타일을 바르고 더 빨리 끝내십시오. 배열에이 같은

시도 뭔가 (주사선 기입?) :

while(canMove(right)){enqueue} // Sequential memory access 
    reset horizontal pos, enable reverse prefetching 
    while(canMove(left)){enqueue} // Sequential memory access 

.... 

    then repeat for verticals 

그런 다음 완료 될 때까지 수직 + 수평 계산을 교대로 반복한다. 이 패턴은 x2 메모리 성능 배수를 제공해야하며 그 중 10-11 배 배열 액세스 타이밍 업그레이드는 메모리에서 구조체 (쌍)에 액세스하지 않기 때문에 단지 1 바이트입니다.

또 다른 방법으로 임의의 위치에서 여러 개의 채우기 포인트를 시작하고 그 중 하나가 원래 홍수에 닿을 때까지 반복하고, 원래 점 영역에 점을 추가하고, 모든 작업을 원래의 flood 스레드로 이동하고, 최종 릴리스에서 반복 할 수 있습니다 모든 비 접촉 홍수. 이렇게하면 캐시를 더 자주 사용할 수 있습니까? 그러나 더 많은 코어가 필요합니다. 또한 gpgpu 버전을 사용해도 아프지 않습니다.

참고 : @David Haim이 제안한 또 다른 최적화가 암시 적으로 시행됩니다. 이 모든 최적화를 통해 A * 알고리즘에 대해 언급 한 기하 급수적 인 속도 향상을보아야합니다.