如何测试算法的实现?
问题描述:
我想测试的一些算法如何测试算法的实现?
如果你想想一个TDD/BDD重点实施...一个考验将是
Scenario: doubling search
Given an ordered array "[2,3,4,5,6,7]"
When I look for "4" with "doubling search" in it
Then the result must be "2"
我想确保我的算法是做得很好...那么,你将如何测试算法实现?
答
你测试的算法的每个执行同样的方式:采取输入,通过手工计算你的预期产出,并比较其算法为您提供的输出。
如果你在使用接口的语言,这样做,你可以有一个通用的测试采取类型接口的参数,并将它通过传递你实现你的实际测试中被调用。这确保所有算法都基于其接口进行相同的测试。
// double search implemented by using the search and multiplying by 2
algorithm multDoubleSearch
define input array
define input search
for each i in array
if i = search * 2
return index of i
end
return -1
end.
// double search implemented by dividing the values by 2
algorithm divDoubleSearch
define input array
define input search
for each i in array
if i/2 = search
return index of i
end
return -1
end.
test mytest
define array {2 3 4 5 6 7}
define search 2
define resultMult = multDoubleSearch(array,search)
assert resultMult == 2 // 4 is index 2, assuming 0 indexed
define resultDiv = divDoubleSearch(array,search)
assert resultDiv == 2 // 4 is index 2, assuming 0 indexed
end.
答
那么这取决于你手头有什么。
除了手动提供输入和输出以测试角落案例和少量其他输入的常见测试(请参阅JUnit或任何流行语言中的类似框架)之外,您还可以编写低效但简单的版本你的算法(或者是产生相同的结果,通常是不完全一样的算法精确的任何东西)和测试针对的版本,无论是对所有可能的输入或者如果使用Fuzztester和一些随机化是不可能的。为后来
一个例子是测试一个复杂的排序算法(假设堆排序)对选择排序。如果你优化了代码,并且手边已经有一个经过验证和测试的版本(这本身就是一个递归问题),那也可以。
你的具体情况,你可以只是比较您的版本对一个简单的二进制搜索 - 其标准库肯定已经有 - 随机输入产生随机大小的数组不应该是问题。