Annotazioni di complessità
Le annotazioni di complessità possono essere usate per affermare che un blocco di codice studente viene eseguito all'interno di un determinato livello di complessità. PyBryt determina la complessità di un blocco di codice studente confrontando il numero di passaggi di esecuzione per varie lunghezze di input. Usa quindi i quadrati minimi per determinare quale classe di complessità rappresenta meglio la relazione.
L'uso delle annotazioni di complessità è un'operazione in due parti: in primo luogo, è necessario creare un'annotazione che indichi a PyBryt di cercare la complessità temporale nel footprint della memoria. In secondo luogo, è anche necessario creare un blocco di codice nell'invio dello studente che indichi a PyBryt il blocco di codice su cui eseguire il controllo della complessità.
La creazione dell'annotazione è semplice: è sufficiente creare un'istanza della classe pybryt.TimeComplexity. Questa annotazione accetta come argomento una classe di complessità fornita dal modulo 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]
Il costruttore TimeComplexity richiede anche che venga fornita l'opzione name, perché questa opzione rappresenta il modo in cui i dati dell'invio dello studente sono associati all'annotazione.
>>> pybryt.TimeComplexity(cplx.linear, name="foo")
pybryt.TimeComplexity
Questo è tutto ciò che serve dal lato dell'implementazione di riferimento. Il vero lavoro di controllo della complessità temporale del codice degli studenti avviene durante la scrittura dello scaffolding fornito agli studenti, che deve usare la gestione contesto check_time_complexity di PyBryt per contrassegnare un blocco di codice come blocco che deve essere controllato per la complessità temporale. Questa gestione contesto accetta come argomenti il nome del blocco (che deve essere lo stesso del name fornito nell'annotazione) e le dimensioni dell'input in esecuzione in tale contesto.
Si consideri, ad esempio, un algoritmo di elevamento a potenza di base in cui le dimensioni dell'input sono la potenza a cui viene generata 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
Un punto dati, tuttavia, non è sufficiente. Per raccogliere i dati per più dimensioni di input, è possibile usare la gestione contesto con lo stesso nome e variare la lunghezza di input:
for p in [2, 5, 10, 15, 20]:
with pybryt.check_time_complexity("foo", p):
assert power(2, p) == 2 ** p
Per semplicità, se l'input in esecuzione è un oggetto che supporta len per determinare le dimensioni, è anche possibile passare l'input stesso come secondo argomento:
l = [1, 2, 3]
with pybryt.check_time_complexity("bar", l):
sort(l)
Quando viene usato nel codice dello studente, o in qualsiasi contesto in cui PyBryt non sta eseguendo il notebook per generare un footprint della memoria, il contesto check_time_complexity non esegue nulla. Tuttavia, quando PyBryt esegue il codice, tiene traccia del numero di passaggi necessari per eseguire il blocco. Poiché le lunghezze di input necessarie per misurare accuratamente la complessità temporale possono diventare eccessivamente elevate, PyBryt non traccia i valori all'interno di questi contesti. Tutte le chiamate necessarie per soddisfare le annotazioni di valore devono verificarsi all'esterno di un contesto check_time_complexity. In caso contrario, PyBryt non visualizza il valore nel footprint della memoria dello studente.