Тестирование колоды карт shuffler

Ваша цель - протестировать shuffle (). Поскольку вы знаете, как вы построили shuffle (), это был бы детерминированный модульный тест вашей исходной колоды по сравнению с перетасованной, если бы вы могли знать серию сгенерированных чисел.

Это случай, когда метод внедряется в ваш класс Deck () во время тестирования может сделать вашу функцию перемешивания детерминированной.

Создайте свой класс для использования функции random () по умолчанию, но для использования заранее определенной функции генерации чисел при введении. Например, в Python вы можете:

class Deck():
   def __init__(self, rand_func = random.random):
      self._rand = rand_func
   def rand(self):
      return self._rand()

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

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

Что касается других ответов, связанных со статистическим моделированием: я думаю, что это тесты приемлемого уровня, чтобы доказать правильность алгоритма «перемешивания», но он не детерминированно тестирует реализацию функции shuffle ().

Чтобы переключиться между внедренной версией и действительно случайной версией, вы можете детерминированно провести модульное тестирование shuffle () и при этом иметь случайное поведение во время выполнения. Вы даже можете сгенерировать несколько различных числовых последовательностей, если есть угловые случаи, которые вы хотите проверить.

Что касается других ответов, связанных со статистическим моделированием: я думаю, что это тесты приемлемого уровня, чтобы доказать правильность алгоритма «перемешивания», но он не детерминированно тестирует реализацию функции shuffle ().

Чтобы переключиться между внедренной версией и действительно случайной версией, вы можете детерминированно провести модульное тестирование shuffle () и при этом иметь случайное поведение во время выполнения. Вы даже можете сгенерировать несколько различных числовых последовательностей, если есть крайние случаи, которые вы хотите проверить.

Что касается других ответов, связанных со статистическим моделированием: я думаю, что это тесты приемлемого уровня, чтобы доказать правильность алгоритма «перемешивания», но он не детерминированно тестирует реализацию функции shuffle ().

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

Есть простые подводные камни, с которыми вы можете столкнуться, если не выполните FY должным образом:

• Возьмите каждую карту i и замените ее другой случайной картой j в колоде, где j может быть любой картой, даже одной из уже посещенной позиции. Это тасование со смещением.
• Получение вывода RNG mod 52 для получения случайных позиций карт. Также ведет к небольшому смещению.

Несколько лет назад была тема исчерпывающей (или утомительной) темы в списке TDD Yahoo Groups. У Рона Джеффриса есть полезные идеи , но лучше всего начинать с вершины .

Хороший вопрос. Во-первых, абсолютный тест «годен / не годен»: после перемешивания мультимножество (например, сравнение после сортировки) должно быть неизменным.

Чтобы проверить случайность, вам необходимо выполнить достаточное перемешивание, чтобы вероятность ложного «недостаточно случайна» "неудача исчезающе мала. Например:

Существует вероятность 0,0000001%, что из 10000 перетасовок конкретная карта окажется в одном из указанных 52 ячеек меньше (1-e) / 52 или больше, чем (1 + e) ​​/ 52. (для некоторого маленького e, я не знаю, как его вычислить.)

Правильная программа может "провалить" такой тест, но не должна терпеть неудачу очень часто.

Что касается перемешивания; одна распространенная ошибка - сделать это:

для i от 1..52:
выберите случайный j из 1 .. 52 и поменяйте местами карту i с картой j ( неверно )

Это не дает вам никакой перестановки с равной вероятностью; это, однако, делает:

для i от 1..52:
выберите случайный j из i .. 52 и поменяйте местами карту i с картой j ( справа )

1. Создайте список.
2. Создайте полную копию этого списка.
3. Перемешайте первый список .
4. Assert list1! = List2

Добавьте дополнительные описательные тесты по мере необходимости. Качество тасования, случайность и т. Д.

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

Лучшим результатом является то, что каждая карта позиция изменилась. Это означает, что каждая из 52 карт теперь в новой позиции. Вы можете воспользоваться моим подходом, описанным выше, записать количество различных элементов и установить порог для теста.

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

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