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