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

Изначально задача возникла больше из академического интереса, чем из практических соображений. После того, как я узнал о 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. Серверная часть, одного из проектов, которым мы занимаемся в данный момент построена по модели акторов ^[1]. Система получилась довольно сложной, поэтому, чтобы контролировать эффективность обработки входящих сообщений, используются тесты, которые подменяют оригинальное сообщение на специальное, которое подсчитывает доступ к полям сообщения.

Автор: etyumentcev

Источник ^[2]