三種模式
「最快」和「最能證明」是兩個不同的問題。
模式不是速度開關。它決定選擇器要最小化哪一個量,而那兩個量是真的會分歧的 —— 30 個基準案例裡有 24 個選出不同路徑。
效能模式
選出「機器校正後的經驗預測成本」最低的路徑。它是贏得基準的那個模式,中位 regret 為 1.000 —— 有一半的案例,它挑的就是事後諸葛的 oracle 會挑的那一條。
它的最壞情況是 oracle 的 4.210 倍。那個數字,就是另一個模式存在的誠實理由。
保證模式
選出「route-conditional 共形成本上界」最低的路徑。它在整個基準上花 188.089 ms,而效能模式是 99.995 ms,最大 regret 6.745 倍。
花將近兩倍的代價換來更慢,聽起來是筆爛交易 —— 直到問題換了。效能模式回答的是哪條路大概最快;保證模式回答的是哪條路讓我說得出一個我辯護得了的成本。只有後者能寫進合約。
未覆蓋
上界在 30 個案例中守住 28 個 —— 93.333%。它是逐路徑校準的,而且不是對「所有正在被適應性比較的路徑」的同時性保證。
這個區分,正是這個版本之所以是候選而非穩定 1.0 的四個理由中的第三個。
批次模式
登錄表小的時候用逐一 GCD;當候選登錄表與批次都夠大,就換共用餘數樹。交叉點是量出來的,不是假設的 —— 專案記錄了上界從 97 到 100,000 的探針成本。
| 引擎 | 時間 | 相對 |
|---|---|---|
| 逐一 GCD | 1.666 ms | 1.000× |
remainder_tree | 0.663 ms | 快 2.513 倍 |
在批次 128、上界 10,000 的條件下,校正選出的引擎與實測最佳引擎相同。那個一致性是被記錄成一個結果,不是被假設成一個性質。
模式不決定什麼
- 選一個模式選一個答案 —— 兩種模式都會正確分解同一個整數
- 較低的預測成本較低實際成本的保證
- 一個共形上界對適應性比較路徑的同時性保證
- 校正曾經與實測一致校正在一般情況下正確