logo标签列表

测试复杂算法的单元测试

algorithmunit-testing
24

如果要测试一个类似于N皇后问题这样比较复杂的算法，你会怎么写测试？我的意思是，对于这种算法，应该采用什么样的正确方法来进行测试：

  1. 有许多解决方案（你不知道/不关心有多少个解决方案），

  2. 你只能得到所有可能解决方案的一个小子集，和

  3. 验证一个解决方案是否正确可能有点棘手（与算法本身的复杂性相当）。

我知道这些条件在N皇后问题本身中并不存在，但我提到它只是为了提供一个例子。

8个回答
9
在您的示例中，我认为您是想对验证提议解决方案的算法进行单元测试。
您需要涵盖以下情况：
- 快乐路径测试以验证算法接受各种正确解决方案 - 快乐路径测试以验证算法拒绝各种不正确的解决方案 - 悲伤路径测试以确保算法正确处理非候选人（例如具有8个皇后而非8个皇后的“解决方案”等）
这里，“各种”意味着您希望解决方案覆盖可能性空间。但是，覆盖该空间的含义因问题而异。我不熟悉N皇后问题，不知道正确解决方案之间存在哪些差异，但如果我要实现测试，则会很有用。关于错误解决方案，您需要涉及相同的排名，相同的文件，相同的对角线和混合的一些解决方案。一些涉及到在边缘上暴露和涉及到离开边缘的暴露。等。
此外，如果您了解解决方案的分布情况，则可以优先考虑更可能的解决方案，尽管最终您将要覆盖那些不太可能的解决方案，因为它们往往是在现实生活中容易出问题的解决方案。
此外，如果算法很复杂，则将其分解为部分并以类似的方式测试这些部分的正确性是有意义的（区分快乐路径和悲伤路径，并测试两种类型的输入）。
7
我认为这是一个非常好的问题，但没有银弹。 我只能告诉你我的经验。
我编写了一个算法，在3D空间中找到两个圆柱体之间最近的点集。 这是一个非常复杂的问题，输入空间很大。
为了测试我的代码，起初我只生成了一些规范情况，这些情况相当轴对齐，因此“正确”的结果是显而易见的。 但那太弱了。
然后，我能够通过应用随机变换来加强规范案例。 这有点帮助。
然后我想过写另一个重复的算法和实现，但那太难了，并且不可能知道两个算法是否可能展现相同的错误。 但是，对于另一个问题，这可能是可行的，例如：蛮力法：不高效，但非常简单易懂且易验证。
然后我考虑解决方案集的属性。例如，分离向量必须是局部极小值，因此我应该能够“围绕”每个解的端点查看（对于小的epsilon），并确定解是否为局部极小值。
然后我开始思考将输入映射到输出的函数的拓扑学特性。 在这种情况下，我知道分离距离应该平稳变化。 因此，我选择了一个随机输入和小的delta，然后将具有和不具有应用delta的输出进行比较。 如果算法正确，则输出中的差异应该很小。
通过结合所有这些技术，我能够对代码产生高度信心。
6

在测试复杂算法时，您需要依靠需要验证的“数据”。假设您已经有了某种形式的问题解决方案（数据），您只需采取数据并让算法运行，并查看答案是否匹配。以使用算法解决n-puzzle为例，它是不确定性的，但您有数据来验证解决方案。

1
这是一个不错的起点，但往往会导致栅栏错误等问题。这绝对不够。 - Paul McMillan
1
但是如果有很多正确答案，而你的算法只是输出了它找到的第一个答案，那么你该怎么办呢？你如何相信它找到的解决方案在你的解决方案集中（你知道这个集合不完整）？ - Sergio
2
Sergio，你需要拥有一个相当全面的解决方案集。或者至少要有一种从基本模板中制定解决方案集的方法。 （看一下算法竞赛如topcoder或codejam如何进行测试，他们只遵循这种方法）。编写另一个算法来验证算法将会出现递归错误的问题。 - Senthil Kumaran
2
如果你知道需要什么样的算法，那么一种选择是使用TDD实现该算法的某些部分。这样，当这些部分被实现后，构建完整的算法将变得轻而易举。
这是一个问题的例子(九个位置的图表)，我不知道它的解决方案，所以从测试驱动开发（TDD）的角度来看，编写一个测试用例将会很困难、甚至是不可能或者不切实际的（因为这需要一个巨大的飞跃）。我认识到它与九皇后问题非常相似，所以我决定使用类似于我用于解决九皇后问题的算法。我使用DiagramTest对Diagram进行测试驱动，之后把所有东西组合在一起放到了九个位置的图表中，只需十几行代码即可完成。运行代码后，我手动检查了最终结果，它确实是该问题的解决方案。
0

算法实际上是最容易进行单元测试的，因为它们没有外部依赖。最好的方法是使用测试驱动开发：确定您想要算法实现的下一个微小需求，为其创建一个测试，然后编写代码以满足该测试（即使这意味着硬编码结果，也不要编写比必要更多的代码）。然后继续进行，根据需要重构代码库，使其更通用并接受更多的用例。当所有用例都被覆盖时，您应该拥有一个坚实的算法实现。

0

你只能测试你知道可以期望的行为。

你是否知道某些测试数据存在解决方案？例如，你可能手动计算出在8x8棋盘上肯定可以放置六个皇后，或者你可能在书中读到至少存在一种方法将八个皇后放置在8x8棋盘上。然后你可以测试你的程序返回至少一个解决方案（也许你不检查它是否是有效的解决方案）。

你是否知道其他一些测试数据不存在解决方案？例如，你可以很容易地自我说服，在3x3上放置三个皇后或在8x8上放置九个皇后是不可能的。然后测试你的程序返回无解决方案，或抛出预期的异常。

你想测试给定的解决方案是否有效吗？那么你必须编写代码来测试其有效性，并运行此代码，无论它有多复杂。如果它足够复杂，请为它编写测试。如果你很幸运，你的程序可以自然地重构，以便你可以重用其中的一些较小部分来测试你的解决方案（重用这些较小部分是可以的，因为你也已经彻底测试了这些部分，不会“引入相同的错误”）。

最后，一旦您发现了错误，您就有了一个示例，说明程序返回了意外结果。编写一个测试来断言下一次不会返回该结果。

任何程序都无法实现100％的测试覆盖率。您能做的只是测试您知道的情况并有时间编写的测试用例。

我喜欢在3x3的棋盘上进行测试的想法。根据我的经验，能够在简单的例子（小N）和显而易见的正确答案的例子上进行测试是一个非常好的想法，这不仅使测试变得更容易，而且还使查找导致测试失败的错误更容易。事实上，面对一个棘手的失败，我经常会尝试看看是否可以获得一个较小N的测试来以同样的方式失败，以便我可以进行调试。 - mcdowella
0

有许多问题，创造一种解决方案比检查任何解决方案是否正确更加困难。

对于像N皇后问题这样的情况，您只需要检查棋盘上每行和对角线上是否只有一个皇后，并且在解决方案中是否有N个皇后，就可以知道该解决方案是否有效。

2：

如果已知该问题具有其他算法可用于某些共同的输入集，则尝试使用其他算法测试原始算法以处理它们都适用的输入集。例如，暴力搜索可能有效，或者可预先计算并保存较小范围的输入的结果以供测试。在某些数学问题中，对于一定范围的输入（如平方数或2的幂等），答案更易验证。您至少应该测试这些情况。

-2
单元测试应该验证算法对各种输入的输出，并且由于这个任务也很复杂，必须由另一个人编写（希望如果代码中有错误，他不会犯同样的错误）。
1
没有一个程序能由单个开发者编写？太可惜了。 - RoundTower
如果问题足够复杂，这是一个非常糟糕的想法。 - Karoly Horvath
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接