快速选择 DOM 中的元素
背景：我的大学课程之一是制作国际象棋。 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++ 进行开发，并且可能会使用 Xerces 库XML，尽管我主要是在寻找想法，而不是实际代码（尽管这会很有帮助）。
Background: For one of my university courses, I am making Chess. The GUI is already finished with hooks into a controller, all I have to do is implement the objects. Traditionally, I would just use native structures suited to each type of object, a stack for a move history (undo supported, but not redo), 2d array/vector for the board, etc. Part of the specification is that I have to load and save the game in a specialized XML format, so I am tempted to simply use a DOMDocument to store the game in its entirety. This would make loading and saving extremely easy if I have a library that implements the DOM load/save actions, because I no longer have to translate between the XML and my structures.
Problem: Speed. In all of the algorithms in chess, I have to do a lot of selecting by location.
XML Format (unchangeable):
<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>
Now I have to get all piece elements and filter out the attributes, an O(n) operation. In an array/vector implementation, I can easily achieve an O(1) time, because it's simple indexing. The price of O(n) is just too high to pay, especially when detecting stalemate.
How would you improve the speed? I'm basically looking for ways index the DOM. I've had some ideas, but how would you solve this problem?
For reference, I'm developing in C++ and will probably use the Xerces library for XML, though I'm mainly looking for ideas, not actual code (though that would be helpful).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
由于国际象棋棋盘具有固定尺寸，因此我选择使用 DOMNode 指针的 2D 数组。它非常快，虽然它确实增加了一些代码复杂性，但它工作得很好。
我确实希望我知道另一种做事的方法。
Because the board for chess has fixed dimensions, I opted to go with a 2D array of
DOMNodepointers. It's very quick, and while it does add some code complexity, it works just fine.I do wish I knew of another way to do things.
您强迫自己使用 XML 结构，从而给自己造成了速度障碍。所有这些为您提供的是快速保存/加载，这是在游戏过程中比实际玩游戏要少得多的事情。因此，我建议您使用本机结构来获得所需的速度，并编写序列化代码将本机结构映射到 XML。
不过，我对你的速度问题很好奇：O(n) 与 O(1) 仅当 n 很大时才是问题。是否真的会有大量的 O(n) 搜索成为问题？时间复杂度只是执行速度的理论指导。您需要记住，这将被实现，并且在您的实现中，即使它们不是理论上的最佳选择（即选择 O(n) 而不是 O(1)），权衡也可以是好的
You've created the speed impediment yourself by forcing yourself to use the XML structure. All this is giving you is a quick save/load, which is something which is done far less often during the game than actually playing the game. Therefore, I suggest you use your native structures to obtain the speed you want, and write serialization code to map the native structures to the XML.
I am curious about your speed issues though: O(n) vs O(1) is only a problem when n is large. Are there really going to be a large number of pieces that the O(n) searching is a problem? Time complexity is just a theoretical guide to the speed of execution. You need to keep in mind that this will be implemented, and in your implementation, tradeoffs can be OK even if they are not the theoretical best choices (i.e. chosing O(n) over O(1))