배경 : 나는 숙제로 게임을 끝냈다. 우리는 16 진수의 경기를해야했습니다. 노드의 2 차원 벡터를 사용하여 보드를 구현하기로 결정하고 노드의 이웃의 x와 y 좌표를 추적하기 위해 2 개의 벡터를 사용했습니다. 승자를 결정하는 데 사용 된 경로 찾기 알고리즘은 Dijkstra의 알고리즘과 유사합니다.(쌍의 벡터) 대 (벡터 쌍) C++
2 개의 벡터를 사용할 때의 단점은 항상 동기화되어야한다는 것입니다. 그러나 속도에 관해 묻습니다. 또한 보드를 구현하는 더 빠른 방법은 아마 1d 벡터를 사용하는 것임을 깨달았습니다.
질문 : 원시 속도와 관련하여 경로 찾기 알고리즘은 2 벡터로 (x, y)를 추적하는 것이 더 빠르지 않습니까? 아니면 쌍의 벡터를 사용하여 구현하면 알고리즘이 더 빨리 실행됩니까?
중에서 선택하십시오. 소프트웨어 설계 단계에서 성능에 대해 걱정하지 않아도됩니다. 가장 중요한 것은 가장 잘 작업 할 수있는 데이터 구조를 선택하는 것입니다.
이렇게하면 성능상의 이점이 이미 있습니다.
그는 이미 프로젝트를 마쳤으며, 프로젝트가 완료되고 기능적으로 작동하면 약간의 성능 향상 효과를 기대할 수있는 최적의시기라고 생각합니다. 게다가, 그들에게 질문에 대한 대답이 필요 없다고 말하는 것은 대답이 아닙니다. – Luke
프로파일 링은 마이크로 최적화를 최적화하거나 추측하거나 사람들이 마이크로 최적화라고 부르는 가장 좋은 방법입니다. – poitroae
@ user2581799 :이 * answer *에서 분명하지 않은 것은 사용자가 실제로 디자인을 선행했는지 여부입니다. 질문에서 그는 프로젝트의 후반까지 쌍의 벡터의 가능성을 고려조차하지 않은 것으로 보인다. 이제 aoeu는 디자인을 다시 방문하도록 제안합니다. * 어떤 데이터 구조가 가장 잘 작동 할 수 있습니까? * 아니오. 디자인을위한 1 개의 추진력 (그리고 나는 쌍의 벡터가 아마도 더 좋을 것이라고 생각할 것이다). 이 특별한 경우에는 성능을 전혀 고려하지 않아야합니다 (측정 될 때까지) –
내 직감은 쌍의 벡터가 빠르다는 것을 말해 주지만, 아마도 그것을 테스트해야 할 것입니다. 더 빠른 포맷과 시간 모두에 수백만 포인트를 삽입하는 테스트 프로그램을 만듭니다. 그런 다음 저장된 데이터를 추출하는 데 걸리는 시간이 더 빠릅니다.
아우에 맞습니다. 우선 멋진 표현에 대해 걱정하지 마십시오.
둘째, 게임 속도가 느려지는 것에 대해 걱정한다면 둘째. 문제가되는 부분을 찾아 걱정하십시오. 이 순차적 때
메모리 액세스가 가장 빠른 :
속도에 대한 약간, 말했다. 주위를 뛰어 다니는 것이 나쁘다. 값을 하나씩 액세스하는 것이 좋습니다.쌍의 벡터 (더 일반적으로 구조체의 벡터, VoS) 또는 벡터 쌍 (벡터의 구조체 SoV)이 더 빠른지 여부는 전적으로 귀하의 액세스 패턴에 달려 있습니다. 함께 좌표 쌍에 액세스합니까 아니면 먼저 모든 x 값을 처리 한 다음 y 값을 모두 처리합니까? 그 대답은 아마도 가장 빠른 데이터 레이아웃을 보여줄 것입니다.
말하자면, "아마"는 쪼그리고 앉는 것을 의미합니다. 프로필, 프로필, 프로필.
먼저, 아오에 지점입니다. 일반적으로 최적화에 관한
둘째 :
최적화의 첫 번째 단계는, 그렇지 않으면 당신은에 대해 개선을 비교하는 기준이없는, 측정입니다.
다음 단계는 프로파일 러에서주기/메모리/기타를 소비하는 곳을 확인하기 위해 일종의 프로파일 러를 사용하는 것입니다.
두 가지 작업을 모두 마쳤 으면 올바른 방법으로 코드의 올바른 부분을 최적화하는 작업을 시작할 수 있습니다.
내 의견 외에도. 게임이 진행됨에 따라 구현 속도가 느려지면 (AI 부분을 추측합니다), 매번 이동 한 후에 Dijkstra를 실행하고있는 것이 원인 일 수 있습니다.보드에서 더 많은 움직임으로 게임이 커지면 AI의 성능이 저하됩니다.
승자를 결정하려면 Dijkstra 대신 disjoint-set 방법을 사용하는 것이 좋습니다. Dijkstra에 비해 disjoint-set의 장점은 메모리 사용량이 적을뿐 아니라 게임이 진행됨에 따라 느려지지 않으므로 각 플레이어가 이동 한 후에 실행할 수 있다는 것입니다. , Disjoint-set - Wikipedia, Union-find - princeton
나는 프로젝트의 중요한 부분의 하나의 구현을 변경하면 거의 DO IT ALL OVER AGAIN을 가진 필요하기 때문에 어려운 작업임을 인식하지만, 이것은 단지 제안하고 당신은 AI의 속도에 대해 걱정하는 경우 그렇다면 이것은 확실히 조사 할만한 가치가 있습니다. 다른 방법으로는 AI를 구현하는 다른 방법이 있습니다. minMAX tree, Alphabeta pruning (이것은 minmax 트리가 개선되었습니다)
Gl.
이런 종류의 질문은 작은 자체 포함 코드 샘플을 제시 할 때 가장 잘 대답 할 수 있습니다. 그리고 그 때까지는 자신의 벤치 마크를 구축하는 데 90 % 이상 걸릴 것입니다. – DavidO
나는 과거에 이런 식으로 해 봤는데'(x, y)'와 같이 쌍을 걱정하는 대신 단순히 쌍을 정수'(x * Number_Of_rows + y)'로 변환하기 만하면됩니다. 보드상의 개별 위치. 이웃 노드는 유사한 방식으로 저장됩니다. 각 노드는 이웃들의'std :: list'을 저장할 것입니다. –
smac89
아마도 여러분은 http://stackoverflow.com/questions/7274268/which-is-faster-vector-of를 읽고 싶을 것입니다. -structs-or-a-number of of vectors 무겁게 읽었을지라도, 구현의 향상 문서는 Djikstra에 대한 많은 통찰력을 제공 할 수 있습니다. http://www.boost.org/doc/libs/1_55_0/libs /graph/doc/dijkstra_shortest_paths.html –