Mi proyecto actual, sucintamente, implica la creación de "eventos aleatorios restringidos". Básicamente estoy generando un cronograma de inspecciones. Algunos de ellos se basan en estrictas restricciones de programación; realiza una inspección una vez por semana los viernes a las 10:00 a.m. Otras inspecciones son "aleatorias"; existen requisitos configurables básicos como "una inspección debe realizarse 3 veces por semana", "la inspección debe realizarse entre las 9 AM y las 9 PM" y "no debe haber dos inspecciones dentro del mismo período de 8 horas", pero dentro de cualquier restricción que se haya configurado para un conjunto particular de inspecciones, las fechas y horas resultantes no deberían ser predecibles.
Las pruebas unitarias y TDD, IMO, tienen un gran valor en este sistema, ya que se pueden usar para construirlo de forma incremental mientras su conjunto completo de requisitos aún está incompleto, y asegúrese de que no esté "sobre-ingenierándolo" para hacer cosas que no hago. Actualmente no sé lo que necesito. Los horarios estrictos fueron pan comido para TDD. Sin embargo, me resulta difícil definir realmente lo que estoy probando cuando escribo pruebas para la parte aleatoria del sistema. Puedo afirmar que todos los tiempos producidos por el planificador deben estar dentro de las restricciones, pero podría implementar un algoritmo que pase todas esas pruebas sin que los tiempos reales sean muy "aleatorios". De hecho, eso es exactamente lo que sucedió; Encontré un problema en el que los tiempos, aunque no eran predecibles exactamente, caían en un pequeño subconjunto de los rangos de fecha / hora permitidos. El algoritmo aún pasó todas las afirmaciones que sentí que podía hacer razonablemente, y no pude diseñar una prueba automatizada que fallara en esa situación, sino que pasara cuando recibiera resultados "más aleatorios". Tuve que demostrar que el problema se resolvió mediante la reestructuración de algunas pruebas existentes para que se repitan varias veces y verifique visualmente que los tiempos generados caen dentro del rango completo permitido.
¿Alguien tiene algún consejo para diseñar pruebas que deberían esperar un comportamiento no determinista?
Gracias a todos por las sugerencias. La opinión principal parece ser que necesito una prueba determinista para obtener resultados deterministas, repetibles y afirmables . Tiene sentido.
Creé un conjunto de pruebas de "sandbox" que contienen algoritmos candidatos para el proceso de restricción (el proceso por el cual una matriz de bytes que podría ser larga se convierte en larga entre un mínimo y un máximo). Luego ejecuto ese código a través de un bucle FOR que le da al algoritmo varios conjuntos de bytes conocidos (valores de 1 a 10,000,000 solo para comenzar) y hace que el algoritmo restrinja cada uno a un valor entre 1009 y 7919 (estoy usando números primos para asegurar un el algoritmo no pasaría por un GCF fortuito entre los rangos de entrada y salida). Los valores restringidos resultantes se cuentan y se produce un histograma. Para "pasar", todas las entradas deben reflejarse dentro del histograma (cordura para garantizar que no "perdimos" ninguna), y la diferencia entre dos cubos en el histograma no puede ser mayor que 2 (realmente debería ser <= 1 , pero estad atentos). El algoritmo ganador, si lo hay, se puede cortar y pegar directamente en el código de producción y se puede establecer una prueba permanente para la regresión.
Aquí está el código:
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;
}
... y aquí están los resultados:
El rechazo de LSB (desplazamiento de bits del número hasta que cae dentro del rango) fue TERRIBLE, por una razón muy fácil de explicar; cuando divide cualquier número entre 2 hasta que sea inferior al máximo, abandona tan pronto como sea, y para cualquier rango no trivial, eso sesgará los resultados hacia el tercio superior (como se vio en los resultados detallados del histograma ) Este fue exactamente el comportamiento que vi en las fechas terminadas; Todas las horas eran en la tarde, en días muy específicos.
El rechazo de MSB (eliminar el bit más significativo del número uno a la vez hasta que esté dentro del rango) es mejor, pero nuevamente, debido a que está cortando números muy grandes con cada bit, no se distribuye uniformemente; es poco probable que obtenga números en los extremos superior e inferior, por lo que obtiene un sesgo hacia el tercio medio. Eso podría beneficiar a alguien que busca "normalizar" datos aleatorios en una curva de campana, pero una suma de dos o más números aleatorios más pequeños (similar a tirar dados) le daría una curva más natural. Para mis propósitos, falla.
El único que pasó esta prueba fue restringir por división de módulo, que también resultó ser la más rápida de las tres. El módulo, por su definición, producirá una distribución lo más uniforme posible dadas las entradas disponibles.
fuente
Respuestas:
Supongo que lo que realmente quiere probar aquí es que, dado un conjunto específico de resultados del aleatorizador, el resto de su método funciona correctamente.
Si eso es lo que está buscando, simule el aleatorizador para que sea determinista dentro de los ámbitos de la prueba.
Por lo general, tengo objetos simulados para todo tipo de datos no deterministas o impredecibles (al momento de escribir la prueba), incluidos los generadores GUID y DateTime.Now.
Editar, a partir de los comentarios: tienes que burlarte del PRNG (ese término se me escapó anoche) en el nivel más bajo posible, es decir. cuando genera la matriz de bytes, no después de convertirlos en Int64. O incluso en ambos niveles, para que pueda probar su conversión a una matriz de Int64 que funcione según lo previsto y luego probar por separado que su conversión a una matriz de DateTimes funciona según lo previsto. Como dijo Jonathon, puedes hacer eso dándole una semilla establecida, o puedes darle la matriz de bytes para devolver.
Prefiero el último porque no se romperá si cambia la implementación del marco de un PRNG. Sin embargo, una ventaja de darle la semilla es que si encuentra un caso en producción que no funcionó según lo previsto, solo necesita haber registrado un número para poder replicarlo, en lugar de toda la matriz.
Dicho todo esto, hay que recordar que se llama un pseudo generador de números aleatorios por una razón. Puede haber algún sesgo incluso a ese nivel.
fuente
Esto va a sonar como una respuesta estúpida, pero lo voy a arrojar porque así es como lo he visto antes:
Desacople su código del PRNG: pase la semilla de aleatorización a todo el código que usa la aleatorización. Luego puede determinar los valores de 'trabajo' a partir de una sola semilla (o varias semillas de eso lo haría sentir mejor). Esto le dará la capacidad de probar adecuadamente su código sin tener que depender de la ley de grandes números.
Suena absurdo, pero así es como lo hacen los militares (o eso o usan una 'tabla aleatoria' que no es realmente aleatoria)
fuente
"Es aleatorio (suficiente)" resulta ser una pregunta increíblemente sutil. La respuesta breve es que una prueba de unidad tradicional simplemente no es suficiente: deberá generar un montón de valores aleatorios y enviarlos a varias pruebas estadísticas que le brinden una alta confianza de que son lo suficientemente aleatorios para sus necesidades.
Habrá un patrón: después de todo, estamos utilizando generadores de números aleatorios psuedo. Pero en algún momento las cosas serán "lo suficientemente buenas" para su aplicación (donde lo suficientemente bueno varía MUCHO entre los juegos en un extremo, donde los generadores relativamente simples son suficientes, hasta la criptografía donde realmente necesita secuencias para ser inviables para determinar por un atacante decidido y bien equipado).
El artículo de Wikipedia http://en.wikipedia.org/wiki/Randomness_tests y sus enlaces de seguimiento tienen más información.
fuente
Tengo dos respuestas para ti.
=== PRIMERA RESPUESTA ===
Tan pronto como vi el título de su pregunta, vine a saltar y proponer la solución. Mi solución fue la misma que varias otras han propuesto: burlarse de su generador de números aleatorios. Después de todo, he creado varios programas diferentes que requieren este truco para escribir buenas pruebas unitarias, y he comenzado a hacer que el acceso simulacro a números aleatorios sea una práctica estándar en toda mi codificación.
Pero luego leí tu pregunta. Y para el problema particular que describe, esa no es la respuesta. Su problema no era que necesitara hacer un proceso predecible que utilizara números aleatorios (por lo que sería comprobable). Por el contrario, su problema era verificar que su algoritmo asignara la salida aleatoria uniforme de su RNG a la salida uniforme dentro de las restricciones de su algoritmo, que si el RNG subyacente fuera uniforme resultaría en tiempos de inspección distribuidos uniformemente (sujeto a la restricciones del problema).
Ese es un problema realmente difícil (pero bastante bien definido). Lo que significa que es un problema interesante. Inmediatamente comencé a pensar en algunas ideas realmente geniales sobre cómo resolver esto. Cuando era un programador hotshot, podría haber comenzado a hacer algo con estas ideas. Pero ya no soy un programador hotshot ... Me gusta que ahora tenga más experiencia y más habilidad.
Entonces, en lugar de sumergirme en el difícil problema, pensé: ¿cuál es el valor de esto? Y la respuesta fue decepcionante. Su error ya se resolvió y será diligente con este problema en el futuro. Las circunstancias externas no pueden desencadenar el problema, solo cambian su algoritmo. La ÚNICA razón para abordar este interesante problema fue para satisfacer las prácticas de TDD (Test Driven Design). Si hay algo que he aprendido es que cumplir ciegamente cualquier práctica cuando no es valiosa causa problemas. Mi sugerencia es esta: simplemente no escriba una prueba para esto y continúe.
=== SEGUNDA RESPUESTA ===
Wow ... qué problema tan genial!
Lo que debe hacer aquí es escribir una prueba que verifique que su algoritmo para seleccionar fechas y horas de inspección producirá resultados distribuidos uniformemente (dentro de las restricciones del problema) si el RNG que usa produce números distribuidos uniformemente. Aquí hay varios enfoques, ordenados por nivel de dificultad.
Puedes aplicar fuerza bruta. Simplemente ejecute el algoritmo MUCHAS veces, con un RNG real como entrada. Inspeccione los resultados de salida para ver si están distribuidos uniformemente. Su prueba deberá fallar si la distribución varía de perfectamente uniforme en más de un umbral determinado, y para asegurarse de detectar problemas, el umbral no se puede establecer DEMASIADO bajo. Eso significa que necesitará una GRAN cantidad de ejecuciones para asegurarse de que la probabilidad de un falso positivo (una falla de prueba por azar) es muy pequeña (bueno <1% para una base de código de tamaño mediano; incluso menos para Una gran base de código).
Considere su algoritmo como una función que toma la concatenación de toda la salida RNG como una entrada, luego produce tiempos de inspección como una salida. Si sabe que esta función es continua por partes, entonces hay una manera de probar su propiedad. Reemplace el RNG con un RNG simulable y ejecute el algoritmo varias veces, produciendo una salida de RNG distribuida uniformemente. Entonces, si su código requirió 2 llamadas RNG, cada una en el rango [0..1], es posible que la prueba ejecute el algoritmo 100 veces, devolviendo los valores [(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)]. Luego, puede verificar si la salida de las 100 ejecuciones se distribuyó (aproximadamente) de manera uniforme dentro del rango permitido.
Si REALMENTE necesita verificar el algoritmo de manera confiable y no puede hacer suposiciones sobre el algoritmo O ejecutar una gran cantidad de veces, entonces aún puede atacar el problema, pero es posible que necesite algunas restricciones sobre cómo programar el algoritmo . Echa un vistazo a PyPy y su enfoque de Object Object como ejemplo. Puede crear un espacio de objetos que, en lugar de ejecutar realmente el algoritmo, calcule la forma de la distribución de salida (suponiendo que la entrada RNG sea uniforme). Por supuesto, esto requiere que construyas una herramienta así y que tu algoritmo se construya en PyPy o en alguna otra herramienta donde sea fácil hacer modificaciones drásticas en el compilador y usarlo para analizar el código.
fuente
Para las pruebas unitarias, reemplace el generador aleatorio con una clase que genere resultados predecibles que cubran todos los casos de esquina . Es decir, asegúrese de que su pseudoaleatorizador genere el valor más bajo posible y el valor más alto posible, y el mismo resultado varias veces seguidas.
No desea que sus pruebas unitarias pasen por alto, por ejemplo, errores ocasionales cuando Random.nextInt (1000) devuelve 0 o 999.
fuente
Es posible que desee echar un vistazo a Sevcikova et al: "Pruebas automatizadas de sistemas estocásticos: un enfoque estadísticamente fundamentado" ( PDF ).
La metodología se implementa en varios casos de prueba para la plataforma de simulación UrbanSim .
fuente
Un enfoque de histograma simple es un buen primer paso, pero no es suficiente para probar la aleatoriedad. Para un PRNG uniforme, también (como mínimo) generaría un diagrama de dispersión bidimensional (donde x es el valor anterior e y es el nuevo valor). Esta trama también debe ser uniforme. Esto es complicado en su situación porque hay no linealidades intencionales en el sistema.
Mi enfoque sería:
Cada una de estas pruebas es estadística y requiere una gran cantidad de puntos de muestra para evitar falsos positivos y falsos negativos con un alto grado de confianza.
En cuanto a la naturaleza del algoritmo de conversión / restricción:
Dado: método para generar un valor pseudoaleatorio p donde 0 <= p <= M
Necesidad: salida y en rango (posiblemente discontinuo) 0 <= y <= N <= M
Algoritmo:
r = floor(M / N), es decir, el número de rangos de salida completos que se ajustan al rango de entrada.p_max = r * Np_maxse encuentray = p / rLa clave es descartar valores inaceptables en lugar de doblar de manera no uniforme.
en seudocódigo:
fuente
Además de validar que su código no falla o arroja excepciones correctas en los lugares correctos, puede crear pares de entrada / respuesta válidos (incluso calculando esto manualmente), alimentar la entrada en la prueba y asegurarse de que devuelva la respuesta esperada. No es genial, pero eso es todo lo que puedes hacer, en mi humilde opinión. Sin embargo, en su caso no es realmente aleatorio, una vez que crea su horario puede probar la conformidad de la regla: debe tener 3 inspecciones por semana, entre 9-9; no hay una necesidad real o la capacidad de probar los tiempos exactos cuando se realizó la inspección.
fuente
Realmente no hay mejor manera que ejecutarlo varias veces y ver si obtienes la distribución que deseas. Si tiene 50 cronogramas de inspección potenciales permitidos, ejecuta la prueba 500 veces y se asegura de que cada cronograma se use cerca de 10 veces. Puede controlar sus semillas generadoras aleatorias para hacerlo más determinista, pero eso también hará que sus pruebas estén más estrechamente acopladas a los detalles de implementación.
fuente
No es posible probar una condición nebulosa que no tiene una definición concreta. Si las fechas generadas pasan todas las pruebas, teóricamente su aplicación funciona correctamente. La computadora no puede decirle si las fechas son "lo suficientemente aleatorias" porque no puede reconocer los criterios para dicha prueba. Si todas las pruebas pasan pero el comportamiento de la aplicación aún no es adecuado, entonces su cobertura de prueba es empíricamente inadecuada (desde una perspectiva TDD).
En mi opinión, lo mejor es implementar algunas restricciones de generación de fechas arbitrarias para que la distribución pase una prueba de olor humano.
fuente
Simplemente grabe la salida de su aleatorizador (ya sea pseudo o cuántico / caótico o del mundo real). Luego guarde y reproduzca esas secuencias "aleatorias" que se ajustan a sus requisitos de prueba, o que exponen posibles problemas y errores, a medida que construye sus casos de prueba de unidad.
fuente
Este caso parece ideal para pruebas basadas en propiedades .
En pocas palabras, es un modo de prueba donde el marco de prueba genera entradas para el código bajo prueba y las aserciones de prueba validan las propiedades de las salidas. El marco puede ser lo suficientemente inteligente como para "atacar" el código bajo prueba e intentar arrinconarlo en un error. El marco generalmente también es lo suficientemente inteligente como para secuestrar su semilla generadora de números aleatorios. Por lo general, puede configurar el marco para generar como máximo N casos de prueba o ejecutar como máximo N segundos, y recuerde los casos de prueba fallidos de la última ejecución y vuelva a ejecutarlos en la versión de código más reciente primero. Esto permite un ciclo de iteración rápido durante el desarrollo y pruebas lentas y exhaustivas fuera de banda / en CI.
Aquí hay un ejemplo (tonto, fallido) que prueba la
sumfunción:sumse llama y se validan las propiedades del resultadoEsta prueba encontrará un montón de "errores" en
sum(comente si fue capaz de adivinar todo esto usted mismo):sum([]) is 0(int, no un flotador)sum([-0.9])es negativosum([0.0])no es estrictamente positivosum([..., nan]) is nanlo cual no es positivoCon la configuración predeterminada,
hpythesisaborta la prueba después de encontrar 1 entrada "incorrecta", lo cual es bueno para TDD. Pensé que era posible configurarlo para informar muchas / todas las entradas "malas", pero ahora no puedo encontrar esas opciones.En el caso de OP, las propiedades validadas serán más complejas: tipo de inspección A presente, tipo de inspección A tres veces por semana, tiempo de inspección B siempre a las 12 p.m., tipo de inspección C de 9 a 9, [el horario dado es para una semana] inspecciones de tipos A, B, C todos los presentes, etc.
La biblioteca más conocida es QuickCheck para Haskell, consulte la página de Wikipedia a continuación para obtener una lista de dichas bibliotecas en otros idiomas:
https://en.wikipedia.org/wiki/QuickCheck
La hipótesis (para Python) tiene una buena reseña sobre este tipo de pruebas:
https://hypothesis.works/articles/what-is-property-based-testing/
fuente
lo que puede hacer una prueba unitaria es la lógica para determinar si las fechas aleatorias son válidas o si se debe seleccionar otra fecha aleatoria.
No hay forma de probar un generador de fechas aleatorias antes de obtener un montón de fechas y decidir si son adecuadamente aleatorias.
fuente
Su objetivo no es escribir pruebas unitarias y aprobarlas, sino asegurarse de que su programa cumpla con sus requisitos. La única manera de hacerlo es definir con precisión sus requisitos en primer lugar. Por ejemplo, mencionó "tres inspecciones semanales en momentos aleatorios". Yo diría que los requisitos son: (a) 3 inspecciones (no 2 o 4), (b) en momentos que no son predecibles por personas que no desean ser inspeccionadas inesperadamente, y (c) no demasiado juntas: dos inspecciones separadas por cinco minutos probablemente no tengan sentido, tal vez tampoco estén demasiado separadas.
Entonces escribes los requisitos con mayor precisión que yo. (a) y (c) son fáciles. Para (b), puede escribir un código lo más inteligente posible que intente predecir la próxima inspección, y para pasar la prueba de la unidad, ese código no debe ser capaz de predecir mejor que una suposición pura.
Y, por supuesto, debe tener en cuenta que si sus inspecciones son realmente aleatorias, cualquier algoritmo de predicción podría ser correcto por pura casualidad, por lo que debe asegurarse de que usted y sus pruebas unitarias no entren en pánico si eso sucede. Tal vez realice algunas pruebas más. No me molestaría en probar el generador de números aleatorios, porque al final es el cronograma de inspección lo que cuenta, y no importa cómo se haya creado.
fuente