c++ - 如何对矩形打包算法进行单元测试

Question

我最近为我正在进行的项目实现了一些矩形装箱算法。我一直在通过生成大量矩形并查看结果来稍微天真地测试它，但我想更有条理地进行测试。

公开的界面如下所示:

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 都会将该容器的一 block 分配给一个矩形，直到它已满并且不能再容纳(在这种情况下，该方法将返回 false)。

那么，鉴于系统接口(interface)很小，算法非常复杂，我无法检查内部状态，我将如何为此编写单元测试？

我的直觉告诉我，我可以用大量随机生成的矩形敲击它。我会保留一份退回配件的 list ，并检查它们是否都在垃圾箱的范围内并且相互不相交。然而，这并没有测试某些退化的情况(比如将所有矩形堆叠在一侧并留出 >80% 的空间)。当然，我可以尝试定义最大允许浪费百分比，并在算法开始拒绝配件时检查它。

对此有几个不满意的方面:

• 如何设置允许的浪费百分比？对我来说，这似乎非常武断和空泛。将它设置得太低，你会得到太多误报，将它设置得太高，你会错过算法中的问题。
• 我希望我的单元测试具有确定性和可重现性。随机数据感觉不对。但是，如果我每次都使用同一组矩形，我就有丢失东西的风险。
• 通过跟踪返回的配件并对其进行分析，测试本身变得非常复杂，以至于它们很容易出错。单元测试应该非常简单。
• 某些不当行为只有在用一双人眼查看数据时才会变得明显。不确定如何检查算法是否“表现良好”。例如，它可能会留下很大的间隙，或者它可能无法旋转矩形以获得最大效率，或者它可能会以错误的方式旋转它们(符号错误)并以这种方式浪费空间...

我知道如何手动测试它，但如何为此编写测试套件？我是否让这件事比实际情况更困难？

Answer 1

需要注意的是，当涉及到测试时，我永远都不太确定我在说什么，下面是我考虑这个问题的方式:

为什么要编写单元测试？据我了解，单元测试是关于确保代码做正确的事情。用一定面积的长方形装一个箱子。尝试打包一个面积大于差值的矩形。合身吗？它不应该。打包一个矩形。是不是在边缘。这是您寻找应该始终保持的简单约束的地方，因此如果您搞砸了重构或忽略了某些事情，您可以捕获它。该算法如何违反您所在宇宙的物理学，您检查它的最简单方法是什么？

您的算法的表现如何好是一个不同的问题。这是基准测试，而不是单元测试。你做得比随机好吗？它与其他装箱算法相比如何？

测试和基准测试有两个不同的目的，我会分开对待它们。

解决具体问题:

But if I use the same set of rectangles every time I risk missing stuff.

您无法测试所有内容。处理所有你能想到的情况。如果出现新情况，就会吸取教训。

how do I set the allowed waste percentage?

查看可用的文献和问题的背景。你需要有多好？其他人有多好？

Not sure how to check that the algorithm is "well behaved".

您可以为特定行为构建最少的示例。对于正确的旋转问题，将“宽”盒子放入“高”箱中，因此唯一的解决方案是旋转。或者构建类似的东西

|    |
|    |
|    |
|x   |
------

并尝试插入

xxxx