MMPF 1.0.0rc1
English

三種模式

「最快」和「最能證明」是兩個不同的問題。

模式不是速度開關。它決定選擇器要最小化哪一個量,而那兩個量是真的會分歧的 —— 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 的探針成本。

引擎時間相對
逐一 GCD1.666 ms1.000×
remainder_tree0.663 ms快 2.513 倍

在批次 128、上界 10,000 的條件下,校正選出的引擎與實測最佳引擎相同。那個一致性是被記錄成一個結果,不是被假設成一個性質。

模式不決定什麼

  • 選一個模式選一個答案 —— 兩種模式都會正確分解同一個整數
  • 較低的預測成本較低實際成本的保證
  • 一個共形上界對適應性比較路徑的同時性保證
  • 校正曾經與實測一致校正在一般情況下正確