복잡성 주석
복잡성 주석을 사용하면 학생 코드 블록이 특정 수준의 복잡성 내에서 실행된다고 어설션할 수 있습니다. PyBryt는 다양한 입력 길이에 대한 실행 단계 수를 비교하여 학생 코드 블럭의 복잡성을 확인합니다. 그런 다음, 최소 제곱을 사용하여 관계를 가장 잘 나타내는 복잡성 클래스를 결정합니다.
복잡성 주석을 사용하는 방법은 두 가지가 있습니다. 먼저, PyBryt가 메모리 공간에서 시간 복잡성을 찾도록 지시하는 주석을 생성해야 합니다. 둘째로, 학생의 제출물에서 PyBryt가 복잡성 검사를 실행할 코드 블록을 알려 주는 코드 블록도 생성해야 합니다.
주석 만들기는 간단합니다. pybryt.TimeComplexity 클래스를 인스턴스화하면 됩니다. 이 주석은 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]
또한 TimeComplexity 생성자에서는 name 옵션도 제공해야 합니다. 이것이 학생 제출물 데이터가 주석에 연결되는 방식이기 때문입니다.
>>> pybryt.TimeComplexity(cplx.linear, name="foo")
pybryt.TimeComplexity
참조 구현 끝에서 필요한 것은 이것이 전부입니다. 학생 코드의 시간 복잡성을 확인하는 실제 작업은 학생들에게 제공되는 스캐폴드를 작성하는 방식입니다. 스캐폴드는 PyBryt의 check_time_complexity 컨텍스트 관리자를 사용하여 코드 블록을 시간 복잡성을 확인해야 하는 블록으로 표시해야 합니다. 이 컨텍스트 관리자는 블록의 이름(주석에 제공된 name과 동일해야 함) 및 해당 컨텍스트에서 실행되는 입력 크기를 인수로 받아들입니다.
예를 들어 입력의 크기가 밑이 올라가는 거듭제곱이 되는 간단한 지수화 알고리즘을 생각해 보겠습니다.
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
하지만 하나의 데이터 요소로는 부족합니다. 여러 입력 크기에 대한 데이터를 수집하려면 동일한 이름으로 컨텍스트 관리자를 사용하고 입력 길이를 변경할 수 있습니다.
for p in [2, 5, 10, 15, 20]:
with pybryt.check_time_complexity("foo", p):
assert power(2, p) == 2 ** p
간단히 하기 위해 실행 중인 입력이 크기를 결정하기 위해 len을 지원하는 개체인 경우 입력 자체를 두 번째 인수로 전달할 수도 있습니다.
l = [1, 2, 3]
with pybryt.check_time_complexity("bar", l):
sort(l)
학생의 코드에서 사용되거나 메모리 공간을 생성하기 위해 PyBryt가 Notebook을 실행하지 않는 컨텍스트에서 사용되는 경우 check_time_complexity 컨텍스트는 아무 작업도 수행하지 않습니다. 그러나 PyBryt는 코드를 실행할 때 블록을 실행하는 데 걸리는 단계 수를 추적합니다. 시간 복잡성을 정확하게 측정하는 데 필요한 입력 길이는 작동하지 않을 수 있으므로 PyBryt는 이러한 컨텍스트 내의 값을 추적하지 않습니다. 값 주석을 충족하는 데 필요한 모든 호출은 check_time_complexity 컨텍스트 외부에서 발생해야 합니다. 그렇지 않으면 PyBryt에서 학생의 메모리 공간 값이 표시되지 않습니다.