Проходил собеседованиях в крупных компаниях, работающих с высоконагруженными сервисами, и в обоих просили написать код решения задачи.
Написал код, а потом спрашивают "Как бы ты её тестировал?".
Сказал, что стал бы придумывать юнит-тесты сам и может быть сгенерил бы большой файл с входными данными для большой нагрузки. Кажись, я чего-то не сказал, потому что они задавали вопросы вроде:
— А как ты докажешь, что эти тесты покрывают все возможные случаи?
и т.п.

Так как тестировать критически ответственный алгоритм?
Спасибо!

Здравствуйте, Juster, Вы писали:

Смотрите в сторону тестирования белого ящика, покрытие ветвей, условий и т.д.

Code coverage

Здравствуйте, Juster, Вы писали:

J>Проходил собеседованиях в крупных компаниях, работающих с высоконагруженными сервисами, и в обоих просили написать код решения задачи.
J>Написал код, а потом спрашивают "Как бы ты её тестировал?".
J>Сказал, что стал бы придумывать юнит-тесты сам и может быть сгенерил бы большой файл с входными данными для большой нагрузки. Кажись, я чего-то не сказал, потому что они задавали вопросы вроде:
J>- А как ты докажешь, что эти тесты покрывают все возможные случаи?
J>и т.п.

J>Так как тестировать критически ответственный алгоритм?
J>Спасибо!

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

А доказывают их корректность математическим аппаратом.

Тестируют реализации алгоритмов.

В общем случае тестирование всех возможных вариантов невозможно, хотя бы потому что их бесконечное множество. Поэтому тестируют ключевые, особые случаи, точки бифуркации.


Ваш Кэп.

Здравствуйте, Juster, Вы писали:

J>Сказал, что стал бы придумывать юнит-тесты сам и может быть сгенерил бы большой файл с входными данными для большой нагрузки. Кажись, я чего-то не сказал, потому что они задавали вопросы вроде:
J>- А как ты докажешь, что эти тесты покрывают все возможные случаи?

Исходя из предположения, что собеседователи сами используют юнит- и прочие тесты (а не просто нашли повод повыделываться), догадываюсь, что выделенное — это и есть "не то".

В юнит-тестировании самое важное — это протестировать все возможные сценарии выполнения. Иными словами, нужно не просто покрыть все ветки алгоритма, а все возможные их комбинации. Напихивание большого объема данных на вход этого не гарантирует никоим образом, более того, оно может создать ложную иллюзию того, что все просто зашибись. Использование code coverage tool тоже весьма спорно, т.к. даже видимое 100% покрытие вовсе не гарантирует, что все возможные комбинации были протестированы.

J>Так как тестировать критически ответственный алгоритм?

Так же, как и любой другой. Тестируют реализацию, а не алгоритм. тесты пишутся на основе знаний о деталях реализации. Есть ветвление? Значит, нужно обеспечить такой набор входных параметров, чтобы проверить обе ветви. Есть вложенное ветвление, внутреннее состояние, цикл? То же самое.
Это, кстати, одно из следствий юнит-тестирования — для обеспечения тестируемости алгоритм нужно дробить на как можно более мелкие юниты, чтобы тестировать их по отдельности. Когда у тебя есть алгоритм, состоящий из 10 вложенных простых алгоритмов, и каждый имеет хотя бы 2 сценария выполнения, то в случае монолитной реализации тебе понадобится 2^10 тестов, чтобы прогнать все возможные варианты. Если же ты эти вложенные алгоритмы оформишь в виде отдельных юнитов, то тестов понадобится всего 2*10.
Возможно, что собеседователям могла не понравиться монолитность кода, не подразумевающая тестирования.

Здравствуйте, landerhigh, Вы писали:

L>В юнит-тестировании самое важное — это протестировать все возможные сценарии выполнения. Иными словами, нужно не просто покрыть все ветки алгоритма, а все возможные их комбинации. Напихивание большого объема данных на вход этого не гарантирует никоим образом, более того, оно может создать ложную иллюзию того, что все просто зашибись.
Точно так же слова программиста "я протестировал все возможные варианты" не гарантирует, что это действительно так. Прогон алгоритмов с рандомными данными — незаменимый инструмент, если мы говорим про солжные алгоритмы с большим числом крайних состояний, или если мы говорим про конкурентные алгоритмы. Они, напару с обычными юнит-тестами, должны дополнять друг друга.

L>Это, кстати, одно из следствий юнит-тестирования — для обеспечения тестируемости алгоритм нужно дробить на как можно более мелкие юниты, чтобы тестировать их по отдельности. Когда у тебя есть алгоритм, состоящий из 10 вложенных простых алгоритмов, и каждый имеет хотя бы 2 сценария выполнения, то в случае монолитной реализации тебе понадобится 2^10 тестов, чтобы прогнать все возможные варианты. Если же ты эти вложенные алгоритмы оформишь в виде отдельных юнитов, то тестов понадобится всего 2*10.
Это совершенно не так. Тестировать надо не только сами "под-алгоритмы", но и точки перехода от одного к другому. Поэтому разбиение одного монолитного метода на несколько маленьких никак не может уменьшить количество юнит-тестов при сохранении эквивалентного покрытия.

Здравствуйте, devcoach, Вы писали:

D>Точно так же слова программиста "я протестировал все возможные варианты" не гарантирует, что это действительно так. Прогон алгоритмов с рандомными данными — незаменимый инструмент,

отнюдь. Незаменимый он только тогда, когда можно 100% вычислить, что при конкретных случайных данных должно быть на выходе. А это может потребовать реализации алгоритма внутри самого юнит-теста, что влчечет за собой.
Хотя стабильность и непадучесть так можно опосредованно проверить. Впрочем, всякие приятности вроде расстрела памяти на граничных данных могут и не вылезти.

D>если мы говорим про солжные алгоритмы с большим числом крайних состояний, или если мы говорим про конкурентные алгоритмы. Они, напару с обычными юнит-тестами, должны дополнять друг друга.

Ну прогнал ты 2^30 степени комбинаций входных данных. Ну code coverage показал, что покрытие 100%. Гарантирует ли это, что проверены все комбинации внутренних состояний?

L>>Это, кстати, одно из следствий юнит-тестирования — для обеспечения тестируемости алгоритм нужно дробить на как можно более мелкие юниты, чтобы тестировать их по отдельности. Когда у тебя есть алгоритм, состоящий из 10 вложенных простых алгоритмов, и каждый имеет хотя бы 2 сценария выполнения, то в случае монолитной реализации тебе понадобится 2^10 тестов, чтобы прогнать все возможные варианты. Если же ты эти вложенные алгоритмы оформишь в виде отдельных юнитов, то тестов понадобится всего 2*10.
D>Это совершенно не так.

Опровергни с цифрами.

D>Тестировать надо не только сами "под-алгоритмы", но и точки перехода от одного к другому.

Что есть "точки перехода" и как, когда и почему их надо тестировать?

D>Поэтому разбиение одного монолитного метода на несколько маленьких никак не может уменьшить количество юнит-тестов при сохранении эквивалентного покрытия.

Уменьшает, как я это показал — вместо экспоненциального закона количество тестов растет линейно.

Здравствуйте, landerhigh, Вы писали:

L>Уменьшает, как я это показал — вместо экспоненциального закона количество тестов растет линейно.
Не уменьшает ни на единицу. Вы что, не можете понять такую простую вещь, что от разнесения методов кода меньше не стало? А раз кода столько же, то и тестов требуется столько же. Единственное, в чем это помогает — упрощает изоляцию ошибок.

Вариант 1:

int bigMethod(int x, int y, int z) {
    if (x ^ y == 0)
        return z;
    else 
        return -z;
}

Вариант 2:

int bigMethod(int x, int y, int z) {
    if (smallMethod(x, y))
        return z;
    else 
        return -z;
}

bool smallMethod(int x, int y) {
    return x ^ y == 0;
}

Из этого примера понятно, что такое "точки перехода"? Даже когда вы доказали, что smallMethod() возвращает правильные значения, вам надо проверить, что вы правильно интегрировали его в bigMethod(), что приводит нас к тому же количеству юнит-тестов.

Здравствуйте, devcoach, Вы писали:

D>Здравствуйте, landerhigh, Вы писали:

L>>Уменьшает, как я это показал — вместо экспоненциального закона количество тестов растет линейно.
D>Не уменьшает ни на единицу. Вы что, не можете понять такую простую вещь, что от разнесения методов кода меньше не стало? А раз кода столько же, то и тестов требуется столько же.

Это неверно. Важен не объем кода, а количество сценариев выполнения.

D>Единственное, в чем это помогает — упрощает изоляцию ошибок.

Уже одно это есть громадный плюс

	Скрытый текст
	D>Вариант 1: D> D>int bigMethod(int x, int y, int z) { D> if (x ^ y == 0) D> return z; D> else D> return -z; D>} D> D>Вариант 2: D> D>int bigMethod(int x, int y, int z) { D> if (smallMethod(x, y)) D> return z; D> else D> return -z; D>} D>bool smallMethod(int x, int y) { D> return x ^ y == 0; D>} D>

D>Из этого примера понятно, что такое "точки перехода"?

Это слишком простой пример, который не иллюстрирует принцип ограничения ответственности юнитов. И вообще, ввиду простоты такое разбиение код ни разу не упростило. А еще там логическая ошибка, по крайней мере, если собирать на плюсах. На знаю, на java может и исключение вылететь.

Вот более жизненный пример:

processedData processRawData(buffer RawData)
{
         if (buffer::size(RawData) == 0)
         {
        return processedData;    // or throw exception. To taste.
    }
    auto tmp_buffer;
    for (;;)
    {
        // Здесь - код выковыривания отсчетов из буфера. Samples помещаются в tmp_buffer
    }
    for (;;)
    {
        // Здесь - нормализуем отсчеты.
    }
    for (;;)
    {
        // А тут применяем window function
    }
    // а тут - применяем собственно наш алгоритм
    // и еще много чего

    return result;
}

Меняем:

processedData processRawData(buffer RawData, WindowFunction* pFunction)
{
         if (buffer::size(RawData) == 0)
         {
        return processedData;    // or throw exception. To taste.
    }
    return runAlgorithm(pFunction->Apply(normalize(extractSamples(RawData)));
}

buffer extractSamples(buffer _data);

buffer normalize(buffer _data);

processedData runAlgorithm(buffer normalizedSamples);

class WindowFunction
{
    public:
    virtual buffer Apply(buffer _normalizedSamples) = 0;
}

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

J>- А как ты докажешь, что эти тесты покрывают все возможные случаи?

Ну для начала: http://fprog.ru/2009/issue1/eugene-kirpichov-fighting-mutable-state/

J>Так как тестировать критически ответственный алгоритм?

Проверить крайние случаи, а там видно будет.

Здравствуйте, Juster, Вы писали:

J>Сказал, что стал бы придумывать юнит-тесты сам и может быть сгенерил бы большой файл с входными данными для большой нагрузки. Кажись, я чего-то не сказал, потому что они задавали вопросы вроде:

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

J>Так как тестировать критически ответственный алгоритм?

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

Автор(ы): Луиза Тамре
Издательство: Вильямс
Цена: 96р.

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

.

Здравствуйте, Juster, Вы писали:

J>Проходил собеседованиях в крупных компаниях, работающих с высоконагруженными сервисами, и в обоих просили написать код решения задачи.
J>Написал код, а потом спрашивают "Как бы ты её тестировал?".

Огласите данное вам задание.

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

Подозреваю что хотели узнать умеете ли вы использовать Dependency Injection.

Что такое конкурентные алгортмы?

Здравствуйте, Juster, Вы писали:

J>Проходил собеседованиях в крупных компаниях, работающих с высоконагруженными сервисами, и в обоих просили написать код решения задачи.
J>Написал код, а потом спрашивают "Как бы ты её тестировал?".
J>Сказал, что стал бы придумывать юнит-тесты сам и может быть сгенерил бы большой файл с входными данными для большой нагрузки. Кажись, я чего-то не сказал, потому что они задавали вопросы вроде:
J>- А как ты докажешь, что эти тесты покрывают все возможные случаи?
J>и т.п.

J>Так как тестировать критически ответственный алгоритм?
J>Спасибо!

есть тулзы для определения процента покрытия кода тестами
ну и пройтись по коду и выявить разные случаи которые надо покрыть
+интеграционные тесты с помощью каких нибудь других тулзов типа jmeter, где имитируется большая нагрузка

H_C>Что такое конкурентные алгортмы?
Видимо он имел ввиду алгоритмы в которых возникает борьба за ресурсы или состояние гонок, либо эксплуатируются побочные эффекты этого.

спинлок — это "конкурентный" алгоритм в его терминологии, насколько я понимаю.