我最近为我正在做的一个项目实现了一些矩形装箱算法。我一直在通过生成许多矩形并查看结果来进行一些天真的测试,但我想更系统地进行测试。
公开的接口是这样的:
class RectPacker
{
public:
RectPacker(int width, int height);
virtual ~RectPacker();
//////
/// brief fit a rectangle into the available space
///
/// param[in] width, height size of the rectangle to be fitted
/// param[out] x, y position where the rectangle was fitted (disregard if function returns false)
/// param[out] rotated whether or not the rectangle was rotated during the fitting
/// return true if position for the rectangle could be found, false if rectangle could not be fitted.
///
virtual bool findBestPosition(int width, int height, int& x, int& y, bool& rotated) = 0;
//////
/// brief clear the rectangle packer
///
/// Resets the packer to an empty state. This is usefull when you want to free up space.
/// Since just freeing space will the space fragmented and degrade packing performance
/// it is usually better to just clear the entire packer and repack all the remaining
/// rectangles.
///
virtual void clear() = 0;
};
基本上你初始化包装与一个bin大小。每次调用findBestPosition都会将该bin中的一个块分配给一个矩形,直到它已满并且无法再容纳更多(在这种情况下,该方法将返回false)。
那么,考虑到系统接口是如此之小,算法是相当复杂的,我不能检查内部状态,我该如何为它编写单元测试?
我的直觉告诉我,我可以用大量随机生成的矩形锤击它。我会保留一份退回配件的清单,并检查它们是否都在垃圾箱的范围内并且互不连接。然而,这并不能测试某些退化情况(如将所有矩形堆叠在一侧并留下>80%的空白空间)。当然,我可以尝试定义一个最大允许的浪费百分比,并在算法开始拒绝配件时检查它。
有几个令人不满意的方面:
- 如何设置允许的浪费百分比?对我来说,这似乎是非常武断和空洞的。设得太低,你会得到太多误报,设得太高,你会错过算法中的问题。
- 我喜欢我的单元测试是确定的和可重复的。随机数据感觉不太对。但是如果我每次都使用相同的矩形集合,我就有可能丢失一些东西。
- 通过跟踪返回的配件并对其进行分析,测试本身变得非常复杂,容易出错。单元测试应该非常简单。
- 某些不当行为只有用一双人类的眼睛看数据才会变得明显。不知道如何检查算法是否"表现良好"。例如,它可能会留下很大的间隙,或者它可能无法旋转矩形以获得最大的效率,或者它可能以错误的方式旋转它们(符号错误)并浪费空间。
我知道如何手动测试它,但是如何为它编写测试套件?我是不是把事情弄得更复杂了?
需要说明的是,当涉及到测试时,我从来都不太确定我在说什么,下面是我如何思考这个问题的:
你为什么要写单元测试?根据我的理解,单元测试是关于确保代码做正确的事情。用一定面积的矩形包装一个箱子。试着用一个面积大于差的矩形来包装。合身吗?这是不应该的。打包成一个矩形。它在边缘吗?这是您寻找应该始终保持的简单约束的地方,因此,如果您搞砸了重构或忽略了某些内容,您可以捕获它。这个算法怎么能违背宇宙的物理规律,最简单的检验方法是什么?
如何好你的算法执行是一个不同的问题。这是基准测试,而不是单元测试。你做得比随机更好吗?它与其他装箱算法相比如何?
测试和基准测试服务于两个不同的目的,我将把它们分开对待。
处理特定点:
但是如果我每次都使用相同的矩形集合,我就有可能丢失一些东西。
你不能测试所有的东西。处理所有你能想到的案子。如果有新的东西出现,那就吸取教训。
如何设置允许的浪费百分比?
看看现有的文献和问题的背景。你需要做得多好?其他人有多好?
不确定如何检查算法是否"表现良好"。
你可以为特定的行为构造最小的例子。对于正确的旋转问题,将"宽"的盒子放入"高"的箱子中,因此唯一的解决方案就是旋转。或者创建像
这样的东西| |
| |
| |
|x |
------
并尝试插入
xxxx