0
私は最近、私が取り組んでいるプロジェクトのためのいくつかの長方形ビンパッキングアルゴリズムを実装しました。私は多少の矩形を生成して結果を見ることでやや素朴にテストしてきましたが、もっと体系的に検討したいと思います。ユニットテストの長方形パッキングアルゴリズムの方法
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;
};
基本的には、ビンサイズでパッカーを初期化：
公開されていますインターフェイスは、次のようになります。 findBestPositionを呼び出すたびに、そのビンのチャンクが一杯になるまで矩形に割り当てられ、それ以上は収まらなくなります（この場合、メソッドはfalseを返します）。
システムインターフェースが非常に小さいので、アルゴリズムはかなり複雑で、内部状態を検査することはできません。これについてユニットテストを書くにはどうすればいいですか？
私の直感は、ランダムに生成された矩形を大量に打ち込むだけでよいことを示しています。私は返品された付属品のリストを保持し、それらがビンの範囲内にあり、相互に分離しているかどうかをチェックします。しかし、縮退している特定のケース（片側にすべての長方形を積み重ね、80％以上の空白を残しておくなど）をテストしません。もちろん、アルゴリズムがフィッティングを拒否し始めるときに、許容される最大の廃棄率を定義して確認することもできます。
これにはいくつか不満な側面があります。
- 私は許さ廃棄物の割合を設定しますどのように？それはひどく恣意的で、私には嫌な思いがするようです。それをあまりにも低く設定すると、誤検知が多すぎるため、あまりにも高く設定すると、アルゴリズムの問題を逃してしまいます。
- 私は単体テストが決定論的で再現性があるのが好きです。ランダムなデータは正しく感じられません。しかし、もし私が不足しているもののリスクがあるたびに、同じ長方形のセットを使用すれば、
- 返されたフィッティングを追跡し、それらを分析すると、テスト自体が複雑になり、エラーが発生しやすくなります。単体テストは単純に死んではいけません。
- ある誤動作は、人間の目のデータを見るだけで明らかになります。アルゴリズムが「正常に動作している」ことを確認する方法が不明です。例えば、大きなギャップを残すか、効率を最大限にするために四角形を回転させることができないかもしれません。あるいは、それらをすべて間違った方向に回転させるかもしれません（符号エラー）...
私はテストする方法を知っていますそれは手作業ですが、そのためのテストスイートを書く方法は？私はこれをより困難にしていますか？私はそれをテストすることになると話している何をかなり確実決して思いません注意点が
を挿入しようR1 =（ax Gr）xa、R2 = ax（a/Gr）、... –