Как написать автоматический тест на алгоритмическую сложность?

Изначально задача возникла больше из академического интереса, чем из практических соображений. После того, как я узнал о Mock-объектах, мне стало интересно, а существует ли такая ситуация, для которой можно написать тест с помощью Mock-объекта, но нельзя с помощью тестов состояния. Буквально первая мысль, которая пришла в голову, была про вычислительную сложность алгоритмов. Можно ли написать автоматический тест, проверяющий, что в конкретной ситуации используется алгоритм определенной сложности?

Идея решения очень проста: Предположим, некоторый алгоритм обрабатывает входной набор данных. Тогда его алгоритмическая сложность определяется количеством и составом операций, выполненных над этим набором. Если на вход подать Mock-объекты, которые будут считать каждый вызов своего метода, то после завершения работы алгоритма мы сможем посчитать точное количество и тип действий, которое потребовалось для его работы. Остается только записать Assert-утверждение.

Ограничение: для данного метода существенно использование статического или динамического полиморфизма, чтобы осуществить подмену на Mock-объект.

Продемонстрируем как это работает на примере С++.

Начнем с Mock-объекта. При работе со структурами данных в C++ требуется, чтобы для объекта были определены операции сравнения < и ==, а также оператор присваивания и оператор копии. Первые две операции — это чтение объекта, а последние две — записи. Напишем класс, который будет отдельно считать операции чтения и операции записи.

class Mock { public:   Mock(): someValue(0){}   Mock(int value): someValue(value) {}   Mock(Mock const& other)   {     ++other.writeCounter;  // подсчет операций записи     this->someValue = other.someValue;   }   Mock& operator=(Mock const& other)   {     ++other.writeCounter; // подсчет операций записи     this->someValue = other.someValue;     return *this;   }    static int HasBeenRead()   {     return readCounter;   }   static in HasBeenWritten()   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) {   ++m1.readCounter; // подсчет операций чтения   return m1.someValue == m2.someValue; } bool operator<(Mock const& m1, Mock const & m2) {   ++m1.readCounter; // подсчет операций чтения   return m1.someValue < m2.someValue; } 

Апробируем нашу идею нашу идею на алгоритмах и структурах данных библиотеки STL языка С++.

Сложность ставки в список O(Const).

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 0 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 1000 write 0 

Вставка n элементов в бинарное сбалансированное дерево имеет сложность порядка O(n *log_2(n)). Не знаю, есть ли какое-то требование в стандарте С++ на этот счет, но в библиотеке STL от Microsoft, map реализован на основе бинарного сбалансированного дерева. Чтобы посчитать сложность операций при работе c map для нашего Mock объекта потребуется дополнительный метод для сравнения пар:

bool operator==(std::pair<const Mock, int> & p1, std::pair<const Mock, int> & p2) {   return p1.first == p2.first; } 

Теперь можно посчитать:

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 31828 write 2048 

Что можно сказать по этому выводу: во-первых на один объект приходится две операции записи! Это может быть накладно для больших объектов без разделения состояния. Во-вторых, конечно, около 30 операций чтения на один объект вполне предсказуемы — log_2(1024) = 10, но начинаешь ощущать масштаб и понимать, почему хэш-таблицы — это хорошо.

Может ли это пригодиться на практике?

Честно говоря, в моей практике было всего три случая, когда это действительно пригодилось, и то, два из них, были больше нужны для обнаружения проблемы, чем для самого теста.

1. Лет восемь назад мне пришлось отлаживать приложение на Qt 4.0. Проблема заключалась в следующем: при открытии определенной формы все приложение сильно начинало тормозить. Как только закрываешь форму — приложение работает нормально. Описанный в статье прием позволил мне выяснить, что в Qt 4.0 все элементы управления, которые могут получать и обрабатывать события, находятся в линейном списке. При возникновении события — оно проходит по всему списку. Конечно, если какой-то элемент управления решает, что он обработал сообщение, то сообщение по цепочке дальше не передается. Но, если желающих обработать сообщение не находится, то оно проходит через всю цепочку. Как например, событие о перемещении курсора мыши над приложением. Так вот, та форма, которая приводила к тормозам, состояла больше, чем из 400 элементов управления! Внешне форма напоминала таблицу из 20 столбцов и 20 строк, но это только внешне! Таблица была сэмулирована с помощью отдельных элементов управления.
2. Лет 5 назад к нам обратился новый клиент с примерно такой же жалобой, но это приложение было уже на библиотеке DevExpress под C#. К сожалению подзабыл детали — но проблема заключалась в том, что внутри библиотеки был компонент, который имел сложность порядка O(n^4), вместо O(n^2).
3. Серверная часть, одного из проектов, которым мы занимаемся в данный момент построена по модели акторов. Система получилась довольно сложной, поэтому, чтобы контролировать эффективность обработки входящих сообщений, используются тесты, которые подменяют оригинальное сообщение на специальное, которое подсчитывает доступ к полям сообщения.