參考實作
參考實作會定義一組條件,以驗證問題的解決方案。 一組參考實作會為學生定義問題集的不同解決方案,並讓講師能驗證非結構化的學生程式碼,以確認演算法的正確性。 在 PyBryt 中,這些參考採用 pybryt.ReferenceImplementation
物件的形式,該物件會裝載一系列注釋,以判斷提交記憶體使用量的條件。
參考實作可以放入不同的用途:您可以根據正確的實作撰寫參考實作,以驗證提交遵循所接受的格式,或撰寫一些符合不正確解決方案的參考實作,以標幟出學生常見的問題。 結合這些驗證與描述性註解訊息,可針對學生工作提供健全的自動化意見反應系統。
建立和檢查參考實作
您可以透過幾種方式建立參考實作:以程式設計方式、將註解收集到清單中並具現化 pybryt.ReferenceImplementation
物件,或透過編譯包含註解的參考筆記本。 PyBryt 會自動追蹤所建立的每個註釋。 因此,編譯筆記本時,不需要將註釋收集到清單中,或建立參考實作物件。 相反地,PyBryt 會假設所有注釋都是單一參考實作的一部分,並為您建立物件。 您可以在此處深入了解關於編譯參考的資訊。
為了和此課程模組一樣,以程式設計方式建立參考實作,註解會收集到清單中,然後和參考的名稱一起傳遞至 pybryt.ReferenceImplementation
建構函式。 讓我們建構一個參考,以尋找數字的標記序列。 函式 hailstone
會以清單的形式傳回序列,並包含追蹤清單建構進度的註解。 註釋接著會儲存在 hailstone_annotations
中。
hailstone_annotations = []
def hailstone(n: int) -> List[int]:
if n == 1:
ret = [n]
elif n % 2 == 0:
ret = [n] + hailstone(n // 2)
else:
ret = [n] + hailstone(3 * n + 1)
hailstone_annotations.append(pybryt.Value(ret))
return ret
讓我們測試我們的 hailstone
實作。 函式 run_hailstone_test_cases
會在函式 hailstone_fn
上執行一些測試案例、傳回數位的標記序列,並在每次執行之前重設 hailstone_annotations
清單,以免我們建立重複的註解。 讓我們使用該清單來測試 hailstone
:
def run_hailstone_test_cases(hailstone_fn):
global hailstone_annotations
hailstone_annotations = []
assert hailstone_fn(9) == [9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
assert hailstone_fn(50) == \
[50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
assert hailstone_fn(117) == \
[117, 352, 176, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
run_hailstone_test_cases(hailstone)
現在讓我們使用 hailstone_annotations
清單建立參考實作。 呼叫參考 hailstone
。
hailstone_ref = pybryt.ReferenceImplementation("hailstone", hailstone_annotations)
使用內容管理員 pybryt.check
,我們可以針對此參考實作執行測試案例,以驗證一切正常運作:
>>> with pybryt.check(hailstone_ref):
... run_hailstone_test_cases(hailstone)
REFERENCE: hailstone
SATISFIED: True
使用多個參考實作
既然我們已了解如何建構單一參考,讓我們來看看如何結合多個參考。 PyBryt 的核心概念是彈性且不受學生實作限制,讓講師為各種學生撰寫多個參考實作,學生可以解決問題。 為了示範此彈性,讓我們為標記序列建立另一個參考。 先前實作使用遞迴從底部建構清單,並提供一系列如下所示的註解:
>>> [hailstone_annotations[i].initial_value for i in range(len(hailstone_annotations)) if i < 20]
[[1],
[2, 1],
[4, 2, 1],
[8, 4, 2, 1],
[16, 8, 4, 2, 1],
[5, 16, 8, 4, 2, 1],
[10, 5, 16, 8, 4, 2, 1],
[20, 10, 5, 16, 8, 4, 2, 1],
[40, 20, 10, 5, 16, 8, 4, 2, 1],
[13, 40, 20, 10, 5, 16, 8, 4, 2, 1],
[26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1],
[52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1],
[17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1],
[34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1],
[11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1],
[22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1],
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1],
[14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1],
[28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1],
[9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]]
但假設學生改為從上而下反復建構清單:
def iterative_hailstone(n: int) -> List[int]:
ret = [n]
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
ret.append(n)
hailstone_annotations.append(pybryt.Value(ret))
return ret
讓我們嘗試根據我們的參考測試此實作。 我們應該會看到此實作失敗,即使 run_hailstone_test_cases
不會引發任何錯誤也一樣。 此失敗是因為 iterative_hailstone
函式是正確的實作,但不符合演算法 hailstone_ref
預期。
>>> with pybryt.check(hailstone_ref):
... run_hailstone_test_cases(iterative_hailstone)
REFERENCE: hailstone
SATISFIED: False
若要解決此問題,讓我們將 iterative_hailstone
變成自己的參考:
>>> iterative_hailstone_ref = pybryt.ReferenceImplementation("iterative_hailstone", hailstone_annotations)
>>> iterative_hailstone_ref
<pybryt.reference.ReferenceImplementation at 0x7fe4c242aa10>
若要對多個參考實作執行檢查,請傳入其中一份清單。 讓我們使用 pybryt.check
來驗證的舊參考和新參考;應該會看到每個實作都滿足其中一個參考,讓我們檢查兩種不同類型的實作!
>>> with pybryt.check([hailstone_ref, iterative_hailstone_ref]):
... run_hailstone_test_cases(hailstone)
>>> print()
>>> with pybryt.check([hailstone_ref, iterative_hailstone_ref]):
... run_hailstone_test_cases(iterative_hailstone)
REFERENCE: hailstone
SATISFIED: True
REFERENCE: iterative_hailstone
SATISFIED: False
REFERENCE: hailstone
SATISFIED: False
REFERENCE: iterative_hailstone
SATISFIED: True