Anotaciones de complejidad
Las anotaciones de complejidad se pueden usar para declarar que un bloque de código de un alumno se ejecuta dentro de un cierto nivel de complejidad. PyBryt determina la complejidad de un bloque de código de los alumnos al comparar el número de pasos de ejecución para varias longitudes de entrada. A continuación, usa mínimos cuadrados para determinar qué clase de complejidad representa mejor la relación.
El uso de las anotaciones de complejidad es una tarea de dos pasos: Primero, debes crear una anotación que le diga a PyBryt que busque la complejidad temporal en la superficie de memoria. En segundo lugar, deberá crear un bloque de código en el envío del alumno que le indique a PyBryt en qué bloque de código debe ejecutar la comprobación de complejidad.
La creación de la anotación es sencilla: solo tiene que crear una instancia de la clase pybryt.TimeComplexity. Esta anotación toma como argumento una clase de complejidad proporcionada por el módulo pybryt.complexities:
>>> import pybryt.complexities as cplx
>>> cplx.complexity_classes
[pybryt.annotations.complexity.complexities.constant,
pybryt.annotations.complexity.complexities.logarithmic,
pybryt.annotations.complexity.complexities.linear,
pybryt.annotations.complexity.complexities.linearithmic,
pybryt.annotations.complexity.complexities.quadratic,
pybryt.annotations.complexity.complexities.cubic]
El constructor TimeComplexity también requiere que se le proporcione la opción name, ya que así es como se asociarán los datos del envío del alumno a la anotación.
>>> pybryt.TimeComplexity(cplx.linear, name="foo")
pybryt.TimeComplexity
Y eso es todo lo que se necesita en cuanto a la implementación de referencia. El trabajo real de comprobar la complejidad del tiempo del código de los alumnos es escribir el scaffold que se proporciona a los alumnos, que debe usar el administrador de contexto check_time_complexity de PyBryt para marcar un bloque de código como un bloque donde debe comprobarse la complejidad del tiempo. Este administrador de contexto acepta como argumentos el nombre del bloque (que debe ser el mismo que el name proporcionado a la anotación) y el tamaño de la entrada que se ejecuta en ese contexto.
Por ejemplo, imagine un algoritmo de exponenciación sencillo donde el tamaño de la entrada es la potencia a la que se eleva la base.
def power(b, p):
if p == 0:
return 1
return b * power(b, p - 1)
with pybryt.check_time_complexity("foo", 10):
assert power(2, 10) == 2 ** 10
Sin embargo, un punto de datos no es suficiente. Para recopilar datos de varios tamaños de entrada, puede usar el administrador de contexto con el mismo nombre y variar la longitud de entrada:
for p in [2, 5, 10, 15, 20]:
with pybryt.check_time_complexity("foo", p):
assert power(2, p) == 2 ** p
Por simplicidad, si la entrada que ejecuta es un objeto que admite len para determinar su tamaño, también puede simplemente pasar la propia entrada como segundo argumento:
l = [1, 2, 3]
with pybryt.check_time_complexity("bar", l):
sort(l)
Cuando se usa en el código del alumno (o en cualquier contexto donde PyBryt no ejecute el cuaderno para generar una superficie de memoria), el contexto check_time_complexity no hace nada. Sin embargo, cuando PyBryt ejecuta el código, hace un seguimiento del número de pasos que da para ejecutar el bloque. Dado que las longitudes de entrada que se necesitan para medir con precisión la complejidad temporal pueden aumentar de forma ininterrumpida, PyBryt no hace un seguimiento de los valores dentro de estos contextos. Las llamadas necesarias para satisfacer las anotaciones de valor deben producirse fuera de un contexto check_time_complexity. De lo contrario, PyBryt no ve el valor en la superficie de memoria del alumno.