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

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Пугающей темой для многих программистов является «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;
    }


O (log N) — логарифмическая. В таком случае количество операций растет медленнее чем количество входных данных. Простейший пример приведен ниже, каждую итерацию i будет увеличиваться в 2 раза и в обработку пойдут не все элементы массива.
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);
        }
    }


O(N2) — квадратичная сложность. Количество операций будет N*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.

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

Listgetaddcontainsremove
ArrayListO(1)O(1)O(N)O(N)
LinkedListO(N)O(1)O(N)O(1)


Setaddcontains
SetO(1)O(1)
LinkedHashSetO(1)O(1)


MapgetputcontainsKey
HashMapO(1)O(1)O(1)
LinkedHashMapO(1)O(1)O(1)

О чем говорят эти данные?
Если нужен доступ по индексу, то лучше использовать 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(N2), так как 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(N2).

Пример 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

👍НравитсяПонравилось10
В избранноеВ избранном10
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Задача оптимизации в автотестах встречается не так уж и редко. Когда встречается, доставляет много проблем. Те кто говорят о бесполезности, возможно, сами не подозревают, что их прекрасные тесты могут проходить в 2 раза быстрее, занимать в 10 раз меньше ресурсов и проходить в 100 раз стабильней, если бы не дилетантство автора.

мало кто заморачивается о памяти ввиду

того что не он занимается распределением казеных ресурсов

Сегодня поговорим о Time Complexity так как мало кто заморачивается о памяти ввиду ее дешевизны

Ну... мне было как-то в лом оптимизировать код, и я запускал его в клауде на машине с 1T оперативной памяти: $100 за три дня вычислений. Ну и сам приценивался к аналогичной конфиругации, не могу сказать, что это было дешёво.

Хорошо бы знать, но в большинстве наших проектов, к сожалению, абсолютно бесполезно и посему невостребовано.

Что есть loot в программировании?
Например, написали мы код, он какое-то время поработал, а потом и он и тесты его покрывающие устарели.
Вот это и есть loot. Закладывались ли деньги на амортизацию рабочего кода? С тем, чтобы когда условия изменились (а балансовая стоимость кода стала равна 0) можно было закупиться у галер новым кодом.
Но что делать со старым?
Вы не поверите, но старый код надо разбирать (а это деньги) поддерживать (и это деньги) стирать с дисков и удалять из архивов (кажется это тоже деньги)
То есть деньги на демонтаж кода должны закладываться в аморт.отчисления.
А вот на одной бирже одна американская компания не удалила с дисков код старой программы, а потом в силу изменившихся требований биржи поверх накатала нового кода.
Но на одном сервере что-то пошло не так и все. Нет больше той компании — проторговалась за 40 минут.
Но все еще хуже: деньги которые не платят за должное обслуживание лута это зазор который обычно считают прибылью.

А еще проблема чистого/грязного кода. И тот и другой работают. Но что делает чистый? Облегчает демонтаж. То есть — кодеры, когда пишут чистый код отрабатывают стоимость демонтажа бесплатно?

Ну-ну.

Иногда я думаю, как бы все изменилось, если бы за каждый бит информации люди должны были бы платить 1 копейку в фонд разработчиков новых технологий хранения данных.
Ну или если бы идентификаторы контента были бы догекоинами (обязательное требование) ?

Свіженька стаття про те, як розробники GTA Online провтикали і випадково заюзали O(N^2) алгоритм замість O(N): nee.lv/...​line-loading-times-by-70 і через це народ 6 хвилин (!) чекав загрузки матчу, замість 1хв.

TL;DR: розробники парсили json через scanf і випадково O(N) раз викликали scanf, який сам по собі працює O(N) => O(N^2).

Обговорення на hacker news теж дуже доречні: news.ycombinator.com/item?id=26296339

мало кто заморачивается о памяти ввиду ее дешевизны

Разработчик Хрома, перелогиньтесь

Дать нормальное определение О-большому — это слишком сложно и не все поймут? («О-большое это функция которая будет ограничивать сверху время выполнения программы в зависимости от размера входа (начинания с какого-то порога)» и нарисовать пару графиков). И да, варианты O(N log N) — это норма например

Пример кода на логарифм лольный, почему нельзя было сразу показать двоичный поиск в отсортированном массиве

слишком сложно и не все поймут?

да. Как по мне, отлично объяснено в статье.

Пример кода на логарифм лольный, почему нельзя было сразу показать двоичный поиск в отсортированном массиве

Это ж нужно рекурсию понимать, а ее не все девелоперы нормально умеют имплементировать.

Это ж нужно рекурсию понимать, а ее не все девелоперы нормально умеют имплементировать

Для двоичного поиска рекурсия точно необязательна

можно. Менее очевидно, что объем данных уменьшается в сколько-то раз.

И много у нас вакансий на Big O?

Трустори: после каждого билда интеграционные тесты у нас занимают 14 часов. И всегда бесит, когда хочешь отдать уже билд, а тесты завалились.

Секрет Полишинеля: надо иметь два набора тестов. Те которые «для покрытия 100% кода» [и всегда с гарантией проходят], и те которые реально требуются и покрывают функционал.

PS. За 14 часом можно и в проде оттестить. Как минимум в бете.
PPS. А потестить только тот участок, который менял — слабо? Чтобы знать заранее, что тесты завалятся.

Секрет Полишинеля: надо иметь два набора тестов. Те которые «для покрытия 100% кода», и те которые реально требуются и покрывают функционал.

Сорян, но 14 часов покрывают функционал.

PS. За 14 часом можно и в проде оттестить. Как минимум в бете.

И получить п-ды от кастомера за горелые железки ценой в 10к$ за штуку?

PPS. А потестить только тот участок, который менял — слабо? Чтобы знать заранее, что тесты завалятся.

Тесты в первую очередь нужны для того, чтобы обнаружить что завал мог быть в другом месте

Да, есть такие проекты, где 14 часов работы кода покрывают функционал. Есть и дольше. Но сколько сотых процента таких задач вообще попадает на аутсорс в Щеневмерлую?

Я уж не говорю, сколько из проектов железные. Ещё и ценой в 10 килобаксов за единицу.

Вот ты не поверишь, но при таком редком для наших краёв раскладе дешевле таки нанять спеца по highload и по security, и уже они пусть рулят проектом с технической точки зрения. А не те джуны, в кого поверил главный маркетолух. Львиную долю ошибок они найдут просто читая код и видя где пытались срезать углы. А тесты будут летать — именно потому, что писаны спецами по highload или по крайней мере под их контролем.

Да, с железом всё по-другому. Если бы в Украине, к примеру, выпускали мобильные телефоны (а я не вижу ровно никаких препятствий иметь вообще свой бренд, программно выпускаемый для себя и соседей, из Китая приходящий в виде болванок) — тогда да, суровые тесты, R&D, и большие проблемы от того что у кого-то батарейка в самолёте загорелась (кстати, до сих пор не знаю, как решили проблему низкого давления для лития).

Но когда по 14 часов начинают тестить какую-то козявочку, где тест включает построение архитектуры с нуля и работает через пень-колоду в условиях виртуальной машины... уж извините. Но надо иметь и короткие наборы тестов. Зачем? Чтобы запуская 14-часовой тест, быть уверенным на 99.99997%, что он пройдёт без ошибок.

Но сколько сотых процента таких задач вообще попадает на аутсорс в Щеневмерлую?

Дарагой, от чего вы проценты считать пытаетесь и что хотите этим числом сказать? Такие задачи есть и все тут.

Если бы в Украине, к примеру, выпускали мобильные телефоны (а я не вижу ровно никаких препятствий иметь вообще свой бренд, программно выпускаемый для себя и соседей, из Китая приходящий в виде болванок) — тогда да, суровые тесты, R&D, и большие проблемы от того что у кого-то батарейка в самолёте загорелась (кстати, до сих пор не знаю, как решили проблему низкого давления для лития).
Если бы в Украине

Первая ссылка в гугле: sigmamobile.net/o-nas намекает что вы пытаетесь рассуждать о вещях, в которых имеете весьма посредственное познание.

Но когда по 14 часов начинают тестить какую-то козявочку, где тест включает построение архитектуры с нуля и работает через пень-колоду в условиях виртуальной машины... уж извините. Но надо иметь и короткие наборы тестов. Зачем? Чтобы запуская 14-часовой тест, быть уверенным на 99.99997%, что он пройдёт без ошибок.

Смысл иметь два набора тестов, если нужно убедится что проходят оба?

Смысл иметь краткие наборы — в том чтобы сократить время если тесты НЕ проходят.

СигмаМобайл помню. Жадные они, за что и были вышвырнуты из тренда. В 2021 продавать телефон с разрешением HD Ready по цене вменяемого аппарата — моветон.

Жадные они, за что и были вышвырнуты из тренда. В 2021 продавать телефон с разрешением HD Ready по цене вменяемого аппарата — моветон.

В iPhone XR разрешение 1792×828.

В других телефонах до 10к грн тоже разрешение невысокое. Алсо, не нужно — dpi и угловое разрешение и так зашкаливают, и там уже больше пиписькомерие начинается чем что-то действительно нужное

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

А ещё про них отзывы мягко скажем не лучшие. Подробностей не помню, но когда выбирал себе железяку — по итогу так их и не купил, нашёл более-менее вменяемый чехол на классику.

Це взагалі ніяк не розпаралелити? Якщо ніяк, то звучить так, наче код погано задизайнений і тому дуже нетестабельний...

Це взагалі ніяк не розпаралелити?

Может быть и можно, но это в 2-3 раза

Якщо ніяк, то звучить так, наче код погано задизайнений і тому дуже нетестабельний...

Как ты предлагаешь тестировать гуй?

Как ты предлагаешь тестировать гуй?

Я по тестуванню гуі не спеціалість, але хіба там не можна дико розпаралелити все? Я в свій час писав watir тести, це таке собі задоволення, але навіть мої гівнотести всерівно виконувались менше хвилини... Зараз же є ціла область RPA, які, грубо кажучи, мають дофіга досвіду взаємодії з різними інтерфейсами — я чомусь впевнений, що ці чуваки точно зможуть підказати як тестити гуі.

Якщо більш абстрактно, то в принципі про тестувабельний код у Гугла є дуже хороша TechTalk «How to Write Clean, Testable Code»: www.youtube.com/watch?v=XcT4yYu_TTs
(імхо одна з найкращих технічних лекцій в принципі). Я буквально пару тижнів назад на цих принципах побудував дуже прикольні test suites для кількох хардкорних і класично важких для тестування алгоритмах.

Розпаралелити не можна. Але можна мати малий набір тестів, який тупо перевірить саме ту частину, яка змінювалася. Доповнивши це тестом ФАЙЛІВ на ідентичність, можна скоротити шлях. Тобто, якщо якась пачка файлів НЕ мінялась, то і тести по ній гнати не критично. А презумпція що все залежить від усього — то міф, а тих хто спробує такі милиці ставити, тупо звільняти після першого ж тесту.

Що це дасть: швидке виправлення багів. Коли виставили версію — чимось не сподобалось, швидко поправили, знову виставили, і таких виправлень може бути кілька за тиждень. І що, на кожне 14 годин лише на спробу? А я нагадаю, що проблема може бути й не в коді, а в самих тестах, які також слід міняти разом із кодом.

Ти і є «Уставший архитектор»?

Розпаралелити не можна.

Що там за ГУІ тест такий, який ваще ніяк не паралелиться?

Який не буде швидшим від того, що його паралелять. На те вони й інтеграційні тести.

Ти і є «Уставший архитектор»?

Еще есть Олег Дорожко и Михаил Кузьмин — тоже наши виртуалы.

Що там за ГУІ тест такий, який ваще ніяк не паралелиться?

Это тот который требует специальных железок для запуска. Ну его можно попробовать распараллелить на 2-3, ну а дальше — не

Розпаралелити не можна.

веб гуй параллельно тестится аж бегом. Кроме разве что IE.

Не поверишь, никак. Львиная доля гуя не заслуживает сурового тестирования. Бывают проекты, где гуй критичен — для этого есть фреймворки сравнения скриншотов с подсветкой отличий.

Но я бы сначала оттестил человеческий фактор, так чтобы система обратной связи работала как японские часы. Притом, в разных режимах оттестил, в том числе и на граничных условиях. Уверяю, человеческий фактор это всегда непросто, его раз в 1-3 месяца тестить надо.

Статья полезная, только «поговорим о Time Complexity так как мало кто заморачивается о памяти ввиду ее дешевизны» — убило. Свопфайл вам на все разделы, зачем это популяризовать?

Какой контекст отсылки к Ракутену?

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

Ну с памятью действительно чаще другие проблемы типа мемори лика или из-за того что люди генерят сильно много объектов а потом частые GC cycles приводят к проседание производительности. А memory complexity проблемы обычно крайне бинарны — или все упало и надо срочно фиксить или все забивают болт и не мониторят так как все в целом работает.

«не мониторят так как все в целом работает» — я об этом, да :(

Подписаться на комментарии