快速选择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）），也可以确定折衷。