アルゴリズムの複雑さの自動テストを作成する方法は？

最初は、実際の検討よりも学問的関心からタスクが発生しました。 Mockオブジェクトについて知った後、Mockオブジェクトを使用してテストを記述できるが、状態テストではできないような状況があるのではないかと思いました。 文字通り、頭に浮かんだ最初の考えは、アルゴリズムの計算の複雑さについてでした。 特定の状況で特定の複雑さのアルゴリズムが使用されていることを確認する自動テストを作成することはできますか？



ソリューションのアイデアは非常に単純です： 入力データセットを処理するアルゴリズムがあるとします。 そのアルゴリズムの複雑さは、このセットで実行される操作の数と構成によって決まります。 Mockオブジェクトを入力に送信すると（メソッドの呼び出しごとにカウントされます）、アルゴリズムが完了すると、操作に必要なアクションの正確な数とタイプを計算できます。 Assertステートメントを記録するためだけに残ります。

制限：このメソッドでは、モックオブジェクトの置換を実行するために、静的または動的なポリモーフィズムを使用することが不可欠です。

C ++の例でこれがどのように機能するかを示しましょう。

Mockオブジェクトから始めましょう。 C ++でデータ構造を使用する場合は、比較演算子<および==、および代入演算子とコピー演算子をオブジェクトに対して定義する必要があります。 最初の2つの操作はオブジェクトの読み取りであり、最後の2つの操作は書き込みです。 読み取り操作と書き込み操作を別々に読み取るクラスを作成します。

class Mock { public: Mock(): someValue(0){} Mock(int value): someValue(value) {} Mock(Mock const& other) { ++Mock::writeCounter; //    ++Mock::readCounter; //    this->someValue = other.someValue; } Mock& operator=(Mock const& other) { ++Mock::writeCounter; //    ++Mock::readCounter; //    this->someValue = other.someValue; return *this; } static int HasBeenRead() { return readCounter; } static int HasBeenWritten() { return writeCounter; } static void Clear() { readCounter = 0; writeCounter = 0; } private: int someValue; static int readCounter; //   static int writeCounter; //   friend bool operator==(Mock const& m1, Mock const & m2); friend bool operator<(Mock const& m1, Mock const & m2); }; int Mock::readCounter = 0; int Mock::writeCounter = 0; bool operator==(Mock const& m1, Mock const & m2) { Mock::readCounter += 2; //    return m1.someValue == m2.someValue; } bool operator<(Mock const& m1, Mock const & m2) { Mock::readCounter +=2; //    return m1.someValue < m2.someValue; } 

C ++ STLライブラリのアルゴリズムとデータ構造に関するアイデアをテストしてみましょう。

リストへの賭けの複雑さはO（定数）です。

 list<Mock> list; for(int i = 999; i >= 0; --i) list.insert(list.begin(), Mock(i)); cout << "Insert to list: read " << Mock::HasBeenRead() << " write " << Mock::HasBeenWritten() << endl; 

コンソール出力：

 Insert to list: read 1000 write 1000 

最悪の場合、線形配列の検索の複雑さはO（n）です。

 find(list.begin(), list.end(), Mock(999)); cout << "Find in list: read " << Mock::HasBeenRead() << " write " << Mock::HasBeenWritten() << endl; 

コンソール出力：

 Find in list: read 3000 write 1000 

バランスの取れたバイナリツリーにn個の要素を挿入すると、次数O（n * log_2（n））の複雑さがあります。 このためのC ++標準に要件があるかどうかはわかりませんが、Microsoft STLライブラリでは、マップはバイナリバランスツリーに基づいて実装されます。
計算：

 map<Mock,int> map; for(int i = 0; i < 1024; ++i) map[Mock(i)] = i; cout << "Insert to map 1024 items: read " << Mock::HasBeenRead() << " write " << Mock::HasBeenWritten() << endl; 

コンソール出力：

 Insert to map 1024 items: read 65704 write 2048 

この結論から言えること：最初に、オブジェクトごとに2つの書き込み操作があります！ これは、状態が分離されていない大きなオブジェクトの場合は高価になる可能性があります。 第二に、もちろん、オブジェクトあたり約60の読み取り操作は非常に予測可能です-log_2（1024）= 10ですが、規模を感じ始め、ハッシュテーブルが優れている理由を理解し始めます。

これは実際に役立つでしょうか？

正直に言って、私の実践では、実際に役立つケースは3つしかありませんでしたが、テスト自体よりも問題を検出するために2つのケースが必要でした。

1. 約8年前、Qt 4.0でアプリケーションをデバッグする必要がありました。 問題はこれでした。特定のフォームを開くと、アプリケーション全体の速度が大幅に低下し始めました。 フォームを閉じるとすぐに、アプリケーションは正常に動作します。 この記事で説明した手法により、Qt 4.0ではイベントを受信および処理できるすべてのコントロールが線形リストにあることがわかりました。 イベントが発生すると、リスト全体が調べられます。 もちろん、何らかのコントロールがメッセージを処理したと判断した場合、メッセージはチェーンに沿ってそれ以上転送されません。 しかし、メッセージを処理したい人がいない場合は、チェーン全体を通過します。 たとえば、マウスカーソルがアプリケーション上を移動するイベント。 そのため、ブレーキにつながったフォームは400以上のコントロールで構成されていました！ 外部では、フォームは20列20行のテーブルに似ていますが、これは外部のみです！ テーブルは個別のコントロールを使用してエミュレートされました。
2. 約5年前、新しいクライアントからほぼ同じ苦情が寄せられましたが、このアプリケーションはすでにC＃のDevExpressライブラリにありました。 残念ながら、詳細を忘れていましたが、問題はライブラリ内にO（n ^ 2）ではなくO（n ^ 4）の次数の複雑さを持つコンポーネントがあったことです。
3. 現在作業中のプロジェクトのサーバー部分は、アクターのモデルに基づいて構築されています。 システムは非常に複雑であることが判明したため、着信メッセージの処理の有効性を制御するために、元のメッセージをメッセージフィールドへのアクセスをカウントする特別なものに置き換えるテストが使用されます。