Big O в автоматизации тестирования

Усі статті, обговорення, новини про тестування — в одному місці. Підписуйтеся на DOU | QA!

Пугающей темой для многих программистов является «Big O Notation». Cказывается специфика украинского IT, где традиционно разработчики заточены под конкретный язык программирования, а требования к алгоритмической базе отходят на второй план.
Среди SDET / QA Automation разговоры на такие темы возникают не часто, так как требования к коду тестов зачастую ниже чем к продакшн коду приложения. Сегодня разберем почему важно понимать и применять концепцию Big O при написании тестов, а также рассмотрим как сделать код оптимальным и эффективным на реальных примерах из жизни.

Определение из википедии:

Big O — математические обозначения для сравнения асимптотического поведения (асимптотики) функций.

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

Две основные характеристики сложности это:

• Time complexity — временная сложность
• Space complexity — сложность по памяти

Сегодня поговорим о Time Complexity так как мало кто заморачивается о памяти ввиду ее дешевизны, а вот время выполнения становится решающим фактором. Временную сложность рассматривают не конкретными единицами времени, а в виде показателя роста количества выполняемых операций.

На графике приведены основные значения Time Complexity.

Разберем подробнее:

0(1) — константная. Постоянное количество операций. Пример — функция суммы двух чисел, которая всегда будет выполняться за константное время.

private int sum(int a, int b) {
        return a + b;
    }

private void function(int[] data) {
        for (int i = 1; i < data.length; i*=2) {
           System.out.println(i);
        }
    }

Типичным примером O (log N) является бинарный поиск, где в каждой итерации массив делится на 2 части и работа выполняется только над одной.


O(N) — линейная. Количество операций будет расти пропорционально входным данным. Пример — обход массива, где количество операций будет равно количеству элементов.

private void function(int[] nums) {
        for (var n : nums) {
            System.out.println(n);
        }
    }

private void function(int[] data) {
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data.length; j++) {
                System.out.println(data[i] + data[j]);
            }
        }
    }

Описанные выше примеры и график дают четкое понимание скорости работы функции. Важно осознанно подходить к этим вопросам при проектировании. Там где обрабатываются большие объемы данных, лучше подумать об оптимизации, O(1) и O(log N) являются самыми предпочтительными вариантами.

Эффективность работы структур данных

У каждой из структур данных есть свои преимущества и недостатки. При выборе важно четко понимать как идет работа под капотом и насколько оптимально она будет справляться с поставленной задачей. В основном автоматизатор использует разные реализации List, Set и Map.

Рассмотрим эффективность их работы:

О чем говорят эти данные?
Если нужен доступ по индексу, то лучше использовать ArrayList, если часто будут удаляться данные — LinkedList, с проверкой наличия элемента в списке лучше справится Set, а если требуется часто искать элемент по уникальному атрибуту, то хорошим вариантом будет Map<атрибут, объект>. Важно понимать что нет плохих и хороших структур данных, есть те, которые лучше подходят для конкретной задачи, а зная эффективность отработки операций, можно осознанно выбирать что будет работать продуктивнее.

Практические примеры

Пример 1

Автоматизируем API тесты работы приложения с документами. Цель проверки — убедиться что новые документы отображаются в списке «All documents».

class Document {
        String id;
        String type;
        String name;
        List<Fields> fields;
    }

После добавления выполняем запрос getAllDocuments(), который вернул 10000 документов.
Будем считать что equals() & hashCode() переопределены, тогда можно было бы проверить через containsAll() но, в случае проблемы, будет неочевидно какой сущности не хватает, поэтому самым простым и информативным вариантом будет проверка списка на contains() каждого конкретного документа.

List<Document> createdDocuments = addDocuments(newDocsList);
List<Document> allDocuments = getAllDocuments();

SoftAssert sa = new SoftAssert();
createdDocuments
      .stream()
      .forEach(d -> sa.assertTrue(allDocuments.contains(d), "document not found: " + d.id));
sa.assertAll();

Так как contains() в реализации List происходит за O(N), то time complexity такой проверки будет O(M*N), где M — количество созданных, а N — количество всех документов. И если создано 10, а общее количество 10000, то для проверки процессор выполнит 100000 операций.

А можно ли сделать лучше?
Заменим List на Set, где contains() выполняется за константное время O(1). Теперь для проверки выполнится всего 10 операций вместо 100000.

List<Document> createdDocuments = addDocuments(newDocsList);
Set<Document> allDocuments = getAllDocs().stream().collect(Collectors.toSet());

SoftAssert sa = new SoftAssert();
createdDocuments
        .stream()
        .forEach(d -> sa.assertTrue(allDocuments.contains(d), "document not found: " + d.id));
sa.assertAll();

Также можем использовать Map, где key будет document.id, а value сам документ. Метод containsKey() для Map также выполняется за O(1), что значит общая временная сложность будет O(N) где N — количество созданных документов, а в нашем случае 10.

List<Document> createdDocs = addDocuments(newDocsList);
Map<String, Document> allDocs = getAllDocs().stream()
                       .collect(Collectors.toMap(d -> d.id, Function.identity()));

SoftAssert sa = new SoftAssert();
createdDocs
     .stream()
     .forEach(d -> sa.assertTrue(allDocs.containsKey(d.id), "document not found: " + d.id));
sa.assertAll();

Замечу что в приведенных примерах не учитывается сложность перехода List → Set и List → Map, а показана эффективность отработки конкретной структуры данных.

Пример 2

Не будем далеко уходить от темы документов, теперь поработаем с полями. Поле содержит в себе два атрибута — уникальное имя и значение.

class Field {
        String name;
        String value;
    }

Цель проверки — заполнить поля и убедиться что данные правильно записались. Наипростейший способ — проходиться по списку, находить по имени нужное поле и сравнивать значение с ожидаемым. В таком случае time complexity будет O(N²), так как N раз будет происходить поиск среди N полей.

private Field getFieldByName(Document document, String name) {
        return document.fields
                .stream()
                .filter(f -> f.name.equals(name))
                .findFirst()
                .orElseThrow(()-> new FieldNotFoundException(name));
    }

SoftAssert sa = new SoftAssert();
sa.assertEquals(getFieldByName(doc,"field1").value, "value1", "[field1] value doesn't match");
sa.assertEquals(getFieldByName(doc,"field2").value, "value2", "[field2] value doesn't match");
sa.assertAll();

Как сделать лучше?
Готовим Map<field_name, field_value> с ожидаемыми значениями , а потом в аналогичном формате представляем текущие значения и сравниваем.

ImmutableMap<String, String> expectedFields = ImmutableMap.of("field1", "value1", "field2", "value2");
Map<String, String> actualFields = fields.stream()
                                .collect(Collectors.toMap(f -> f.name, f -> f.value));
assertEquals(actualFields, expectedFields, "fields data doesn't match")

Стоит заметить, что в случае ошибки, разбираться с проблемой будет не так удобно и для наглядного отчета лучше пройтись по каждому полю. Такая имплементация сделает репорт информативнее, а сообщение об ошибке будет содержать информацию только по проблемным полям.

SoftAssert sa = new SoftAssert();
for (var field : actualFields.entrySet()) {
  sa.assertEquals(field.getValue(), expectedFields.get(field.getKey()), field.getKey() + " data doesn't match");
}
sa.assertAll();

Так как get() в Map выполняется за константное время, то time complexity проверки уже будет O(N) вместо O(N²).

Пример 3

Следующий пример будет об эффективном использования API продукта. Рассмотрим как оптимизировать прекондишен. Для теста требуется достать информацию о юзере, зная только email, акцентирую что на этом этапе не тестируется API работы с юзером и не важно как данные будут получены.

Можно сделать запрос getUsers() и перебором найти нужный по email. Как правило, юзеров много и ответ может быть очень большим, также вероятно что там будет пагинация, а значит нужно будет сделать запрос на каждую страницу. Выглядит трудоемко и не оптимально.

Как сделать лучше?
Скорей всего API предусматривает поиск или фильтр по атрибуту, а значит можно использовать getUsers() с фильтром filter[email]=userEmail либо найти юзера через searchUser(userEmail).

Таким образом, вместо множества запросов и перебора списка на совпадение, данные будут получены за 1 запрос. Как бонус, проверим что back-end эффективно работает с фильтрацией, не перегружает базу или не отрабатывает слишком долго.

Пример 4

Если говорить о настроенных процессах тестирования, то автоматизация интегрируется с TMS (Test Management System) и в результате можно получить общий отчет об авто и мануальном тестировании. Рассмотрим как применить знания Big O в реализации такой интеграции.

Есть набор автотестов размером 10000 и тест-ран в TMS системе. Требуется записывать результаты прохождения по итогу тестового прогона.

Как сделать этот процесс эффективным?
Прежде всего лучше добавлять результаты в TMS систему bulk запросом, чтобы не пушить отдельно каждый, а собрать все и передать за 1 раз, на этом этапе количество операций уже уменьшилось с 10000 до 1.

Теперь известно что нужна эффективная структура для хранения 10000 сущностей и работы с ними, а основные требования — быстро найти нужный Case и обновить поля.

class Case {
        String id;
        String title;
        String status;
        String comment;
    }

Так как известен id каждого кейса, то идеальным вариантом хранения данных и работы с ними будет Map<case_id, case>.

Map<String, Case> cases = getAllCases().stream()
                 .collect(Collectors.toMap(case -> case.id, Function.identity()));

Теперь поиск Case и обновление полей будет происходить за O(1). В итоге time complexity составит O(N), где N — количество кейсов, а в конце тестового прогона 10000 результатов запишутся в TMS одним запросом.

Выводы

Основная идея — достигать результата эффективно, затрачивая минимум ресурсов для реализации конечной цели.
А базовые знания концепции Big O помогут писать оптимально работающий код, который будет отлично справляться с большими объемами данных и высокой нагрузкой.

Полезные материалы:

Data Structures and Algorithms: Deep Dive Using Java

Generics & Collections in Java

Big-O Cheat Sheet