速度（成對的矢量）vs（成對的矢量）C++

-3

背景：我已經完成了作爲一項家庭作業的寫作遊戲。我們必須做一個十六進制遊戲。我決定使用2d節點向量來實現該板，並使用2個向量來跟蹤節點鄰居的x和y座標。我用來確定獲勝者的路徑尋找算法與Dijkstra的相似。速度（成對的矢量）vs（成對的矢量）C++

我意識到使用2個向量的缺點是它們必須始終保持同步，但我在問速度。我也意識到，實現該板的更快方法可能是使用1d矢量（我在完成該程序時意識到了這一點）。

問題：就原始速度而言，如果使用雙向量向量來實現，路徑搜索算法會以2個向量運行得更快以跟蹤（x，y）還是算法運行得更快？

來源

2014-02-18 paeynivek

當提供一個小型的自包含代碼示例時，可以最好地回答這類問題，當你完成這些時，你有90％的方法可以構建自己的基準測試。 – DavidO

我在過去做過這樣的事情，而不是擔心'（x，y）'中的對，我只是將這些對轉換爲整數（（* x Number_Of_rows + y）），這就是我用來存儲每個對在板上的個人位置。鄰居以類似的方式存儲，其中每個節點將存儲鄰居的「std :: list 」 – smac89

也許你想閱讀http://stackoverflow.com/questions/7274268/which-is-faster-vector-of - 結構或向量編號儘管它是一個繁重的閱讀，但它們的實現的增強文檔可以對Djikstra具體有更多的瞭解：http://www.boost.org/doc/libs/1_55_0/libs /graph/doc/dijkstra_shortest_paths.html –

選擇其中更適合您需要的產品。在軟件設計的這個階段，你不應該關心性能。更重要的是選擇最適合的數據結構。

在這樣做時，性能優勢可能已經在您身邊。

來源

2014-02-18 17:01:59 poitroae

他說他已經完成了它，並且在一個項目完成之後，功能似乎成爲了獲得一些性能優勢的最佳時機。此外，告訴他們他們不需要回答他們的問題並不是一個答案。 – Luke

分析是優化，猜測或人們稱之爲微優化的最佳方式。 – poitroae

@ user2581799：從這個*答案*中可能不明顯的是用戶是否實際想到了設計。從這個問題來看，他似乎甚至沒有考慮在項目的晚些時候纔開始配對的可能性。現在，aoeu建議重新考慮設計：*您最適合使用哪種數據結構？*應該是否定的。 1的設計驅動力（我想可能會有更好的配對向量）。你甚至可以說，對於這種特殊情況，你甚至不應該考慮性能（直到測量） –

我的直覺告訴我，對的向量會更快，但您可能需要測試它。創建一個測試程序，將數百萬個點插入到格式和時間更快的地方。然後，時間格式更快以提取存儲的數據。

來源

2014-02-18 17:06:47 Luke

aoeu有權利：首先擔心好的代表性。第二，如果你擔心遊戲速度緩慢，配置文件。發現問題領域並擔心這些問題。

這就是說，一些關於速度：

內存訪問是最快的，當它是連續的。跳來跳去是不好的。一個接一個地訪問值是很好的。

對（更一般地說，結構向量，VoS）或一對向量（向量結構，SoV）的向量是否更快的問題完全取決於您的訪問模式。你是否一起訪問座標對，或者你是先處理所有的x，然後處理所有的y值？答案很可能會顯示更快的數據佈局。

這就是說，「最可能」是指下蹲。簡介，簡介，簡介。

來源

2014-02-18 17:07:18

首先，aoeu是關鍵。

其次，對於一般的優化：

優化的第一步就是測量，否則你不會有一個基準來比較的改善。

下一步是使用某種類型的分析器來查看代碼花費週期/內存/其他的位置，它可能不是您的想法。

當你完成了這兩項工作之後，你就可以開始以正確的方式優化代碼的正確部分了。

來源

2014-02-18 17:09:20 dutt

除了我的評論。如果你的實現在遊戲進行時運行得更慢（我猜測它的AI部分），那麼可能是因爲你在每次移動後都在運行Dijkstra。隨着遊戲規模越來越大，AI的性能越來越差。

建議使用disjoint-set方法而不是Dijkstra來確定獲勝者。與Dijkstra相比，disjoint-set的優勢在於它不僅使用更少的內存，而且隨着遊戲進行速度不會變慢，所以您可以在每個玩家移動後運行它。 Disjoint-set - Wikipedia，Union-find - princeton

我認識到，改變項目的重要組成部分之一的實施是一項艱鉅的任務，因爲它要求幾乎不必DO IT ALL OVER AGAIN，但是這僅僅是一個建議，如果你是擔心AI的速度，那麼這絕對值得研究。還有其他的方法可以實現AI，例如minMAX tree,Alphabeta pruning（這是對minmax樹的改進）

G1。

來源

2014-02-18 17:26:43 smac89

速度（成對的矢量）vs（成對的矢量）C++

回答

相關問題