0

背景：对于我的一门大学课程，我正在下国际象棋。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库，尽管我主要是在寻找想法，而不是实际代码（尽管这会有所帮助）。

4

2 回答 2

1

因为国际象棋棋盘的尺寸是固定的，所以我选择使用 2DDOMNode指针数组。它非常快，虽然它确实增加了一些代码复杂性，但它工作得很好。

我真希望我知道另一种做事的方法。

于 2011-11-15T17:07:38.660 回答
0

通过强迫自己使用 XML 结构，您自己造成了速度障碍。所有这一切都给你一个快速的保存/加载，这是在游戏中比实际玩游戏少得多的事情。因此，我建议您使用您的本机结构来获得您想要的速度，并编写序列化代码将本机结构映射到 XML。

不过，我对您的速度问题很好奇：O(n) 与 O(1) 仅在 n 很大时才是问题。真的会有大量的 O(n) 搜索有问题吗？时间复杂度只是执行速度的理论指导。您需要记住这将被实现，并且在您的实现中，即使它们不是理论上的最佳选择（即选择 O(n) 而不是 O(1)），也可以进行权衡

于 2011-11-09T05:55:12.980 回答