複雜度注釋

已完成

複雜度注釋可用來判斷學生的程式碼區塊在特定的複雜度層級內執行。 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

這就是參考實作端所需的一切。 檢查學生程式碼時間複雜度的實際工作是撰寫要提供給學生的 Scaffold,這必須使用 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 未執行筆記本以產生磁碟使用量的任何內容中),check_time_complexity 內容不會執行任何動作。 不過,當 PyBryt 執行程式碼時,該內容會追蹤執行區塊所需的步驟數目。 因為精確測量時間複雜度所需的輸入長度可能會變得過高,因此 PyBryt 不會追蹤這些內容內的值。 滿足值註釋所需的任何呼叫都必須在 內容「外部」check_time_complexity發生。 否則,PyBryt 不會看到學生磁碟使用量中的值。

檢定您的知識

1.

假設我們有下列時間複雜度區塊:

with pybryt.check_time_complexity("fib", 100):
    fib(100)

下列哪一個運算式會建立上述區塊可以搭配使用的批註?

2.

下列哪一個運算式會建立一種注釋,能夠判斷程式碼區塊是在對數還是線性時間中執行的?