Мой текущий проект, кратко, включает создание «случайно-случайных событий». Я в основном генерирую график проверок. Некоторые из них основаны на строгих расписаниях; Вы проводите проверку один раз в неделю в пятницу в 10:00. Другие проверки являются «случайными»; Существуют основные настраиваемые требования, такие как «проверка должна проводиться 3 раза в неделю», «проверка должна проводиться в период с 9 до 9 часов вечера» и «не должно быть двух проверок в течение одного 8-часового периода», но в рамках каких-либо ограничений, настроенных для определенного набора проверок, итоговые даты и время не должны быть предсказуемыми.
Модульные тесты и TDD, IMO, имеют большое значение в этой системе, так как их можно использовать для поэтапного построения ее, в то время как ее полный набор требований все еще не завершен, и убедитесь, что я не «чрезмерно разрабатываю» ее, чтобы делать то, что я делаю В настоящее время не знаю, что мне нужно. Строгие графики были сдобными для TDD. Однако мне трудно определить, что именно я тестирую, когда пишу тесты для произвольной части системы. Я могу утверждать, что все времена, создаваемые планировщиком, должны попадать в ограничения, но я мог бы реализовать алгоритм, который проходит все такие тесты без фактического времени, являющегося очень «случайным». На самом деле это именно то, что произошло; Я обнаружил проблему, когда время, хотя и не было предсказуемым, попало в небольшое подмножество допустимых диапазонов даты / времени. Алгоритм по-прежнему проходил все утверждения, которые я чувствовал, что я мог разумно сделать, и я не мог спроектировать автоматизированный тест, который потерпел бы неудачу в этой ситуации, но прошел, когда дали «более случайные» результаты. Я должен был продемонстрировать, что проблема была решена путем реструктуризации некоторых существующих тестов, чтобы они повторялись несколько раз, и визуально проверял, чтобы сгенерированное время находилось в полном допустимом диапазоне.
Есть ли у кого-нибудь советы по разработке тестов, которые должны ожидать недетерминированного поведения?
Спасибо всем за предложения. Похоже, что главное мнение заключается в том, что мне нужен детерминированный тест, чтобы получить детерминированные, повторяемые, утверждаемые результаты . Имеет смысл.
Я создал набор тестов «песочницы», которые содержат подходящие алгоритмы для процесса ограничения (процесс, при котором байтовый массив, который может быть любым длинным, становится длинным между минимальным и максимальным). Затем я запускаю этот код через цикл FOR, который дает алгоритму несколько известных байтовых массивов (значения от 1 до 10 000 000 только для начала), а алгоритм ограничивает каждое значение значением от 1009 до 7919 (я использую простые числа для обеспечения Алгоритм не будет проходить мимо некоторого случайного GCF между входным и выходным диапазоном). Результирующие ограниченные значения подсчитываются и создается гистограмма. Чтобы «пройти», все входные данные должны быть отражены в гистограмме (здравый смысл, чтобы гарантировать, что мы не «потеряли»), и разница между любыми двумя сегментами в гистограмме не может быть больше 2 (она действительно должна быть <= 1 , но следите за обновлениями). Алгоритм выигрыша, если таковой имеется, может быть вырезан и вставлен непосредственно в производственный код, а для регрессии введен постоянный тест.
Вот код:
private void TestConstraintAlgorithm(int min, int max, Func<byte[], long, long, long> constraintAlgorithm)
{
var histogram = new int[max-min+1];
for (int i = 1; i <= 10000000; i++)
{
//This is the stand-in for the PRNG; produces a known byte array
var buffer = BitConverter.GetBytes((long)i);
long result = constraintAlgorithm(buffer, min, max);
histogram[result - min]++;
}
var minCount = -1;
var maxCount = -1;
var total = 0;
for (int i = 0; i < histogram.Length; i++)
{
Console.WriteLine("{0}: {1}".FormatWith(i + min, histogram[i]));
if (minCount == -1 || minCount > histogram[i])
minCount = histogram[i];
if (maxCount == -1 || maxCount < histogram[i])
maxCount = histogram[i];
total += histogram[i];
}
Assert.AreEqual(10000000, total);
Assert.LessOrEqual(maxCount - minCount, 2);
}
[Test, Explicit("sandbox, does not test production code")]
public void TestRandomizerDistributionMSBRejection()
{
TestConstraintAlgorithm(1009, 7919, ConstrainByMSBRejection);
}
private long ConstrainByMSBRejection(byte[] buffer, long min, long max)
{
//Strip the sign bit (if any) off the most significant byte, before converting to long
buffer[buffer.Length-1] &= 0x7f;
var orig = BitConverter.ToInt64(buffer, 0);
var result = orig;
//Apply a bitmask to the value, removing the MSB on each loop until it falls in the range.
var mask = long.MaxValue;
while (result > max - min)
{
mask >>= 1;
result &= mask;
}
result += min;
return result;
}
[Test, Explicit("sandbox, does not test production code")]
public void TestRandomizerDistributionLSBRejection()
{
TestConstraintAlgorithm(1009, 7919, ConstrainByLSBRejection);
}
private long ConstrainByLSBRejection(byte[] buffer, long min, long max)
{
//Strip the sign bit (if any) off the most significant byte, before converting to long
buffer[buffer.Length - 1] &= 0x7f;
var orig = BitConverter.ToInt64(buffer, 0);
var result = orig;
//Bit-shift the number 1 place to the right until it falls within the range
while (result > max - min)
result >>= 1;
result += min;
return result;
}
[Test, Explicit("sandbox, does not test production code")]
public void TestRandomizerDistributionModulus()
{
TestConstraintAlgorithm(1009, 7919, ConstrainByModulo);
}
private long ConstrainByModulo(byte[] buffer, long min, long max)
{
buffer[buffer.Length - 1] &= 0x7f;
var result = BitConverter.ToInt64(buffer, 0);
//Modulo divide the value by the range to produce a value that falls within it.
result %= max - min + 1;
result += min;
return result;
}
... и вот результаты:
Отклонение LSB (сдвиг битов числа до тех пор, пока оно не попадает в диапазон) было УЖАСНЫМ по очень простой для объяснения причине; когда вы делите любое число на 2 до тех пор, пока оно не станет меньше максимума, вы выйдете из системы, как только оно произойдет, и для любого нетривиального диапазона это сместит результаты в верхнюю треть (как было видно из подробных результатов гистограммы). ). Это было именно то поведение, которое я видел из законченных дат; все время было днем, в очень конкретные дни.
Отклонение MSB (удаление наиболее значимого бита из номера один за раз, пока он не окажется в пределах диапазона) лучше, но опять же, поскольку вы отбираете очень большие числа с каждым битом, он распределяется неравномерно; маловероятно, что вы получите числа в верхнем и нижнем концах, поэтому вы получаете уклон в сторону средней трети. Это может принести пользу кому-то, кто хочет «нормализовать» случайные данные в кривую округлости, но сумма двух или более случайных чисел меньшего размера (аналогично бросанию игральных костей) даст вам более естественную кривую. Для моих целей это не удается.
Единственным, кто прошел этот тест, было ограничение по модулю, которое также оказалось самым быстрым из трех. По определению, модуль будет производить как можно более равномерное распределение с учетом доступных входных данных.
источник
Ответы:
Я предполагаю, что вы действительно хотите проверить здесь, что при заданном наборе результатов от рандомизатора остальная часть вашего метода работает правильно.
Если это то, что вы ищете, то смоделируйте рандомизатор, чтобы сделать его детерминированным в рамках теста.
У меня обычно есть фиктивные объекты для всех видов недетерминированных или непредсказуемых (на момент написания теста) данных, включая генераторы GUID и DateTime.Now.
Редактировать, из комментариев: Вы должны высмеивать PRNG (этот термин ускользнул от меня прошлой ночью) на самом низком возможном уровне - т.е. когда он генерирует массив байтов, а не после того, как вы превратите их в Int64. Или даже на обоих уровнях, так что вы можете проверить, что ваше преобразование в массив Int64 работает как задумано, а затем отдельно проверить, что ваше преобразование в массив DateTimes работает как задумано. Как сказал Джонатон, вы можете просто сделать это, задав ему начальное число, или вы можете дать ему массив байтов для возврата.
Я предпочитаю последнее, потому что оно не сломается, если изменится реализация PRNG. Тем не менее, одно преимущество, которое дает начальное значение, состоит в том, что если вы обнаружите, что дело в производстве не работает должным образом, вам нужно зарегистрировать только одно число, чтобы иметь возможность его реплицировать, а не весь массив.
Все это говорит, вы должны помнить , что это называется Псевдо генератор случайных чисел по причине. Может быть некоторый уклон даже на этом уровне.
источник
Это будет звучать как глупый ответ, но я собираюсь выкинуть его туда, потому что вот как я это делал раньше:
Отсоедините ваш код от PRNG - передайте начальное значение рандомизации во весь код, который использует рандомизацию. Затем вы можете определить «рабочие» значения из одного семени (или нескольких семен, которые помогут вам чувствовать себя лучше). Это даст вам возможность адекватно протестировать свой код без необходимости полагаться на закон больших чисел.
Это звучит глупо, но так поступают военные (или они используют «случайную таблицу», которая на самом деле не случайна вообще)
источник
«Это случайно (достаточно)» оказывается невероятно тонким вопросом. Короткий ответ заключается в том, что традиционный модульный тест просто не урежет его - вам нужно сгенерировать кучу случайных значений и отправить их в различные статистические тесты, которые дают вам высокую уверенность в том, что они достаточно случайны для ваших нужд.
Будет шаблон - мы используем генераторы псевдослучайных чисел в конце концов. Но в какой-то момент все будет «достаточно хорошо» для вашего приложения (где достаточно хорошее варьирует много между, скажем, играми на одном конце, где достаточно относительно простых генераторов, вплоть до криптографии, где вам действительно нужны последовательности, которые невозможно определить решительным и хорошо экипированным атакующим).
В статье Википедии http://en.wikipedia.org/wiki/Randomness_tests и ее последующих ссылках содержится больше информации.
источник
У меня есть два ответа для вас.
=== ПЕРВЫЙ ОТВЕТ ===
Как только я увидел название вашего вопроса, я пришел, чтобы вскочить и предложить решение. Мое решение было таким же, как и то, что предложили несколько других: макетировать ваш генератор случайных чисел. В конце концов, я построил несколько различных программ, которым требовался этот трюк для написания хороших модульных тестов, и я начал делать поддельный доступ к случайным числам стандартной практикой во всем моем кодировании.
Но потом я читаю ваш вопрос. И для конкретной проблемы, которую вы описываете, это не ответ. Ваша проблема заключалась не в том, что вам нужно было сделать предсказуемый процесс, использующий случайные числа (так что это было бы проверяемым). Скорее, ваша проблема состояла в том, чтобы убедиться, что ваш алгоритм отображал равномерно случайный выходной сигнал от вашего ГСЧ на выходной сигнал с единообразным ограничением из вашего алгоритма - что если базовый ГСЧ был однородным, это привело бы к равномерно распределенному времени проверки (при условии проблемные ограничения).
Это действительно сложная (но довольно четко определенная) проблема. Это означает, что это ИНТЕРЕСНАЯ проблема. Сразу же начал думать о некоторых действительно хороших идеях о том, как решить эту проблему. Когда я был горячим программистом, я мог начать что-то делать с этими идеями. Но я больше не программист ... Мне нравится, что я теперь более опытный и опытный.
Таким образом, вместо того, чтобы погрузиться в сложную проблему, я подумал про себя: какова ценность этого? И ответ был неутешительным. Ваша ошибка уже решена, и вы будете прилежны к этой проблеме в будущем. Внешние обстоятельства не могут вызвать проблему, только изменения в вашем алгоритме. ЕДИНСТВЕННАЯ причина для решения этой интересной проблемы состояла в том, чтобы удовлетворить методы TDD (Test Driven Design). Если есть одна вещь, которую я узнал, так это то, что слепое следование любой практике, когда она не является ценной, вызывает проблемы. Мое предложение таково: просто не пишите тест для этого и продолжайте.
=== ВТОРОЙ ОТВЕТ ===
Вау ... какая классная проблема!
Здесь вам нужно написать тест, который подтвердит, что ваш алгоритм выбора дат и времени проверки будет давать выходные данные, которые будут равномерно распределены (в пределах ограничений задачи), если используемый им ГСЧ выдает равномерно распределенные числа. Вот несколько подходов, отсортированных по уровню сложности.
Вы можете применить грубую силу. Просто запустите алгоритм целую кучу раз, с реальным RNG в качестве входных данных. Проверьте выходные результаты, чтобы увидеть, распределены ли они равномерно. Ваш тест должен будет провалиться, если распределение варьируется от идеально однородного более чем до определенного порогового значения, и чтобы гарантировать, что вы обнаружите проблемы, пороговое значение не может быть установлено СЛИШКОМ низким. Это означает, что вам понадобится ОГРОМНОЕ количество прогонов, чтобы быть уверенным, что вероятность ложного срабатывания (случайный сбой теста) очень мала (хорошо <1% для кодовой базы среднего размера; еще меньше для большая кодовая база).
Рассмотрим ваш алгоритм как функцию, которая принимает конкатенацию всех выходных данных ГСЧ в качестве входных данных, а затем выдает время проверки в качестве выходных данных. Если вы знаете, что эта функция является кусочно-непрерывной, то есть способ проверить ваше свойство. Замените ГСЧ на поддельный ГСЧ и запустите алгоритм несколько раз, создавая равномерно распределенный выход ГСЧ. Таким образом, если вашему коду потребовалось 2 вызова RNG, каждый в диапазоне [0..1], вы можете выполнить тестовый прогон алгоритма 100 раз, возвращая значения [(0.0,0.0), (0.0,0.1), (0.0, 0,2), ... (0,0,0,9), (0,1,0,0), (0,1,0,1), ... (0,9,0,9)]. Затем вы можете проверить, был ли выход 100 прогонов (приблизительно) равномерно распределен в пределах допустимого диапазона.
Если вам ДЕЙСТВИТЕЛЬНО необходимо проверить алгоритм надежным способом и вы не можете делать предположения относительно алгоритма ИЛИ запускаться большое количество раз, то вы все равно можете атаковать проблему, но вам могут потребоваться некоторые ограничения на то, как вы программируете алгоритм , Посмотрите на PyPy и подход к объектному пространству в качестве примера. Вы можете создать объектное пространство, которое вместо того, чтобы фактически выполнять алгоритм, вместо этого просто рассчитало форму выходного распределения (предполагая, что вход ГСЧ является однородным). Конечно, это требует, чтобы вы собрали такой инструмент и чтобы ваш алгоритм был построен в PyPy или каком-либо другом инструменте, где легко внести радикальные изменения в компилятор и использовать его для анализа кода.
источник
Для модульных тестов замените генератор случайных чисел классом, который генерирует предсказуемые результаты, охватывающие все угловые случаи . Т.е. убедитесь, что ваш псевдослучайный генератор генерирует наименьшее возможное значение и наивысшее возможное значение, и один и тот же результат несколько раз подряд.
Вы не хотите, чтобы ваши модульные тесты игнорировали, например, отдельные ошибки, возникающие, когда Random.nextInt (1000) возвращает 0 или 999.
источник
Возможно, вы захотите взглянуть на Sevcikova et al: «Автоматизированное тестирование стохастических систем: статистически обоснованный подход» ( PDF ).
Методология реализована в различных тестовых примерах для платформы моделирования UrbanSim .
источник
Простой гистограммный подход - хороший первый шаг, но его недостаточно для доказательства случайности. Для равномерного PRNG вы также (как минимум) сгенерировали бы двумерный график рассеяния (где x - предыдущее значение, а y - новое значение). Этот сюжет также должен быть равномерным. Это сложно в вашей ситуации, потому что в системе существуют преднамеренные нелинейности.
Мой подход будет следующим:
Каждый из этих тестов является статистическим и требует большого количества точек выборки, чтобы избежать ложных срабатываний и ложных отрицательных результатов с высокой степенью достоверности.
Что касается природы алгоритма преобразования / ограничения:
Дано: метод генерации псевдослучайного значения p, где 0 <= p <= M
Потребность: вывод y в (возможно, прерывистом) диапазоне 0 <= y <= N <= M
Алгоритм:
r = floor(M / N), то есть количество полных выходных диапазонов, которые соответствуют входному диапазону.p_max = r * Np_maxбудет найдено значение, меньшее или равноеy = p / rКлюч в том, чтобы отбрасывать неприемлемые значения, а не складывать неравномерно.
в псевдокоде:
источник
Помимо проверки того, что ваш код не дает сбоев или выдает правильные исключения в нужных местах, вы можете создать действительные пары ввода / ответа (даже вычисляя это вручную), передать входные данные в тесте и убедиться, что он возвращает ожидаемый ответ. Не очень, но это все, что ты можешь сделать, имхо. Тем не менее, в вашем случае это не совсем случайно, когда вы создаете расписание, вы можете проверить соответствие правилам - должно быть 3 проверки в неделю, между 9-9; нет никакой реальной необходимости или возможности проверять точное время, когда произошла проверка.
источник
На самом деле нет лучшего способа, чем запустить его несколько раз и посмотреть, получите ли вы нужный дистрибутив. Если у вас есть 50 допустимых графиков проверки, вы должны выполнить тест 500 раз и убедиться, что каждое расписание используется близко к 10 разам. Вы можете управлять своими генераторами случайных чисел, чтобы сделать их более детерминированными, но это также сделает ваши тесты более тесно связанными с деталями реализации.
источник
Невозможно проверить туманное состояние, которое не имеет конкретного определения. Если сгенерированные даты проходят все тесты, то теоретически ваше приложение работает правильно. Компьютер не может сказать вам, являются ли даты «достаточно случайными», потому что он не может подтвердить критерии для такого теста. Если все тесты пройдены, но поведение приложения все еще не подходит, то ваш тестовый охват эмпирически неадекватен (с точки зрения TDD).
На мой взгляд, вам лучше всего реализовать некоторые ограничения на генерацию произвольных дат, чтобы распределение прошло тест на человеческий запах.
источник
Просто запишите выходные данные вашего рандомизатора (будь то псевдо или квантово / хаотично или в реальном мире). Затем сохраните и воспроизведите те «случайные» последовательности, которые соответствуют вашим требованиям к тестам или которые раскрывают потенциальные проблемы и ошибки, по мере того, как вы создаете свои тестовые примеры.
источник
Этот случай кажется идеальным для тестирования на основе свойств .
В двух словах, это режим тестирования, при котором инфраструктура тестирования генерирует входные данные для тестируемого кода, а тестовые утверждения проверяют свойства выходных данных. Фреймворк может быть достаточно умным, чтобы «атаковать» тестируемый код и попытаться превратить его в ошибку Фреймворк, как правило, также достаточно умен, чтобы захватить ваш генератор случайных чисел. Как правило, вы можете сконфигурировать платформу для генерации не более N тестовых случаев или выполнения не более N секунд, а также запоминать неудачные тестовые примеры из последнего запуска и заново запускать их для более новой версии кода. Это учитывает быстрый цикл итерации во время разработки и медленное, всестороннее тестирование вне полосы / в CI.
Вот (тупой, неудачный) пример тестирования
sumфункции:sumвызывается и свойства результата проверяютсяЭтот тест обнаружит кучу «ошибок»
sum(прокомментируйте, если вы смогли угадать все это самостоятельно):sum([]) is 0(int, а не float)sum([-0.9])отрицательноsum([0.0])не является строго положительнымsum([..., nan]) is nanчто не является положительнымПри настройках по умолчанию
hpythesisпрерывает тест после того, как найден 1 «плохой» ввод, что хорошо для TDD. Я думал, что можно настроить его так, чтобы он сообщал о многих / всех «плохих» входах, но сейчас я не могу найти эти опции.В случае OP проверенные свойства будут более сложными: присутствует тип проверки A, вид проверки A трижды в неделю, время проверки B всегда в 12:00, тип проверки C с 9 до 9, [данный график рассчитан на неделю] проверки типов A, B, C все присутствует и т. Д.
Самая известная библиотека - QuickCheck для Haskell, список страниц на других языках см. На странице Википедии ниже:
https://en.wikipedia.org/wiki/QuickCheck
Гипотеза (для Python) имеет хорошее описание этого вида тестирования:
https://hypothesis.works/articles/what-is-property-based-testing/
источник
модульный тест позволяет определить, являются ли случайные даты действительными или нужно выбрать другую случайную дату.
Невозможно протестировать генератор случайных дат, кроме как получить несколько дат и решить, являются ли они случайными.
источник
Ваша цель - не писать модульные тесты и проходить их, а убедиться, что ваша программа соответствует ее требованиям. Единственный способ сделать это - в первую очередь точно определить ваши требования. Например, вы упомянули «три еженедельные проверки в случайное время». Я бы сказал, что следующие требования: (а) 3 проверки (не 2 или 4), (б) время от времени, которые не могут быть предсказаны людьми, которые не хотят, чтобы их неожиданно осматривали, и (в) не слишком близко друг к другу - две инспекции с интервалом в пять минут, вероятно, не имеют смысла, возможно, не слишком далеко друг от друга.
Таким образом, вы записываете требования более точно, чем я. (а) и (в) легко. Для (b) вы могли бы написать какой-нибудь код, настолько умный, насколько это возможно, который пытается предсказать следующую проверку, и для прохождения модульного теста этот код не должен быть в состоянии предсказать лучше, чем просто догадка.
И, конечно, вы должны знать, что если ваши проверки действительно случайны, любой алгоритм прогнозирования может быть правильным по чистой случайности, поэтому вы должны быть уверены, что вы и ваши юнит-тесты не паникуете, если это произойдет. Возможно, проведите еще несколько тестов. Я бы не стал проверять генератор случайных чисел, потому что в конечном итоге важен график проверок, и не имеет значения, как он был создан.
источник