快速選擇DOM中的元素

Question

背景：對於我的大學課程之一，我正在製作國際象棋。 GUI已經完成了鉤入控制器，我所要做的就是實現這些對象。傳統上，我只是使用適合每種類型對象的本機結構，移動歷史（撤消支持，但不重做）的堆棧，二維數組/板載矢量等。規範的一部分是我必須加載並以專門的XML格式保存遊戲，所以我很想簡單地使用DOMDocument來存儲整個遊戲。如果我有一個實現DOM加載/保存操作的庫，這將使加載和保存變得非常容易，因爲我不再需要在XML和我的結構之間進行轉換。

問題：速度。在國際象棋的所有算法中，我必須按位置進行大量選擇。

XML格式（不變）：

<board> 
     <piece type="rook" color="white" column="0" row="7"/> 
     <piece type="knight" color="white" column="1" row="7"/> 
     <piece type="bishop" color="white" column="2" row="7"/> 
     <piece type="queen" color="white" column="3" row="7"/> 
     <piece type="king" color="white" column="4" row="7"/> 
     <piece type="bishop" color="white" column="5" row="7"/> 
     <piece type="knight" color="white" column="6" row="7"/> 
     <piece type="rook" color="white" column="7" row="7"/> 
     <piece color="white" column="3" row="6" type="pawn"/> 
     <piece row="6" type="pawn" color="white" column="4" /> 
</board> 

現在，我必須得到所有片元素，並篩選出的屬性，爲O（n）操作。在一個數組/矢量實現中，我可以輕鬆實現O（1）次，因爲它是簡單的索引。 O（n）的價格太高，特別是在發現僵局時。

你會如何提高速度？我基本上在尋找索引DOM的方法。我有一些想法，但你會如何解決這個問題？

作爲參考，我用C++開發，可能會使用XML的Xerces庫，儘管我主要是在尋找想法，而不是實際的代碼（儘管這會有所幫助）。

Answer 1

因爲板對於國際象棋有固定的尺寸，我選擇使用二維數組DOMNode指針。它非常快速，雖然它增加了一些代碼複雜度，但它工作得很好。

我希望我知道另一種做事的方式。

Answer 2

您已經通過強制自己使用XML結構自己創建了速度障礙。所有這些都給你提供了一個快速的保存/加載，這在遊戲過程中比實際玩遊戲要少得多。因此，我建議你使用你的本地結構來獲得你想要的速度，並編寫序列化代碼來將本地結構映射到XML。

雖然我很好奇你的速度問題：當n很大時，O（n）對O（1）只是一個問題。 O（n）搜索是否是一個問題，是否真的會有大量的片斷？時間複雜度只是執行速度的理論指南。您需要記住，這將實施，並且在您的實施中，即使它們不是理論上的最佳選擇（即，在O（1）上選擇O（n）），也可以確定折衷。