淺談指令效能分析

--- title: 淺談指令效能分析 tags: math, started --- # 淺談指令效能分析指令效能分析是指令設計中非常重要的一環，指令設計方式差者可以嚴重影響到地圖的順暢度，故我們之後會特別將其額外分離成一個研究主題，其中將低效能(低順暢度)轉換成高效能(高順暢度)的步驟又稱之為 優化(Optimize)，而在此篇中我們只會淺談與淺度分析一些常見的優化指令技巧 > 詳細的分析可以查看我們的另一個文章分類：[Minecraft 指令效能分析](https://hackmd.io/@mccmd-analyzed/By-kvNtUO) --- # 一、時間複雜度(Time Complexity) ### 一般的表示法(T) 其記錄數值的方式，便是用一個字母「T」的函式形式做表達，代表一個時間(Time)消耗的概念 * 執行 $n$ 次 $⇒ T(n)$ ### Big-O表示法(O) 其記錄數值的方式，便是用一個字母「O」的函式形式做表達，其表示法常會省略掉 係數、常數項、低次項 的部分，以下舉例： `ex.` $T(50n)$ $⇒ O(n)$ `ex.` $T(7n^2+3n+1)$ $⇒ O(n^2)$ `ex.` $T(10⋅(\log_2n)^3 + 1000⋅\log_2n)$ $⇒ O(\log^3n)$ `ex.` $T(\sqrt{n}+(\log_2n)^3+\log_2n)$ $⇒ O(\sqrt n)$ 假設目標是生成n隻殭屍，那麼其「生成殭屍所消耗的時間」會被計為 $O(n)$ > 對數(Logarithm) : $a^y=x \Rightarrow \log_a x=y$ > > 以下的 $\log N$ 皆為 $\log_2N$ 的簡寫，而不是 $\log_{10}N$ > 請注意，log函式的省略底數格式，在電腦時間分析相關部分，其底數通常為2 其順序比較是這樣排序的： $O(1) < O(\log n) < O(\sqrt n) < O(n) < O(n\log n) < O(n^2) < O(a^n) < O(n!)$ ![](https://i.imgur.com/O58Qvwo.png =65%x) 在此篇分析大部分「指令執行時間」上，我們會使用此兩種方式來表示，在大多情況我們會更傾向使用Big-O表示法 (因為T的係數項大多情況是無法得知的) --- # 二、集合(Set) 在分析上，我們可以利用數學中的集合來將目標實體用符號表示的方式分群，這也是我們本篇會常出現的方式，範例為假設有一集合 $S = \{1,2,3\}$ | 符號表示法 | | 範例 | | | ---------- | ------------ | -- | -- | | $E\in S$ | $E$ 屬於 $S$ | $1\in S$ | $1$ 屬於 $S$ | | $\|S\|$ | $S$ 的元素個數 | $\|S\|=3$ | $S$ 有三個元素 | | $A\subset S$ | $A$ 包含於 $S$ // $A$ 被 $S$ 包含 | $\{1,2\}\subset S$ | $\{1,2\}$ 包含於 $S$ | > 小小的英文科普 > 屬於：A belongs to B > 包含於：A is a subset of B --- # 三、實體選擇器(selector)的運作方式首先要特別留意的一點，selector除了`@s`之外，皆會搜索全部的實體或玩家，假設玩家(Players)的集合為 $P$、實體(Entities)的集合為 $E$，且 $P\subset E$ (實體中含有玩家)，以下我們會區分幾種複雜度的變數分別為： | 選擇器 | 掃描目標的範圍，以及其時間複雜度的分析 | | -------- | -------- | | `@a` | 複雜度至少為 $O(\|P\|)$，代表掃描全部共 $\|P\|$ 個玩家 | | `@e, @p` | 複雜度至少為 $O(\|E\|)$，代表掃描全部共 $\|E\|$ 個實體 | | `@s` | 複雜度為 $O(1)$，僅掃描自己本身 (最優的選擇器) | --- # 四、Minecraft 背景演算法與資料結構 * 儲存實體：**Array List** * 選擇實體時亦會創建並傳遞一個實體List * 實體排序：**Merge Sort** * 排序的時間為：$O(n \log n)$，$n$ 為實體或目標數量，會生成一個新的Array List * 數量指定(`limit`)：整個都排序完後才會抓數量，會消耗額外時間 * 預處理： * 當List中的實體只剩下一個時，不會執行排序的動作 * 當List中只有玩家的時候，會只跑「玩家的排序算法」 * 實體儲存Tags：**Hash Set<String>** * 查詢、插入與移除的時間皆為：$O(1)$ * 呼叫Function : **Immutable HashMap** * 查詢、插入與移除的時間皆為：$O(1)$ --- # 五、一些實體選擇器的時間分析範例以下簡寫 $|E|$ 為$E$、$|P|$ 為$P$，以避免太過眼花撩亂 | 指令 | 時間複雜度 | | --------------------- | ---------- | | `execute as @e as @e` | $O(E^2)$ | | `execute as @a as @e` | $O(P\cdot E)$ | | `execute as @e as @a` | $O(E\cdot P)$ | | `execute as @e[tag=target_tag]` | $O(E)$ | | `execute as @s[tag=target_tag]` | $O(1)$ | | `execute as @e[sort=nearest]` | $O(E\log E)=T(E+E\log E)$ | | `execute as @e[sort=nearest,limit=3]` | $O(E\log E)=T(E+E\log E+$$3$$)$| | `execute as @e[sort=nearest,limit=7] as @a` | $O(E\log E+P)=T(E+E\log E+$$7$$+$$7$$P)$| | `execute as @p` | $O(P)=T(P)$ | --- # 六、選擇器優化範例以下提共幾種常見的選擇器執行時間優化技巧 --- ## 提出判斷共同項優化主要處理：重複引用相同的選擇器項目的情況 ``` # old:a.mcfunction execute as @a[tag=target,score={object=1}] run ... execute as @a[tag=target,score={object=2}] run ... execute as @a[tag=target,score={object=3}] run ... execute as @a[tag=target,score={object=4}] run ... ``` ─── ⇓ (optimization line) ⇓ ─── ``` # new:a.mcfunction execute as @a[tag=target] run function new:b ``` ``` # new:b.mcfunction execute if entity @s[score={object=1}] run ... execute if entity @s[score={object=2}] run ... execute if entity @s[score={object=3}] run ... execute if entity @s[score={object=4}] run ... ``` ### ──────────🕝 執行時間效能分析 🕘────────── * $P$ : 玩家總數量 * $P_t$ : tag為target的玩家數量 * $C_{tag}$ : 比較tag的消耗 * $C_{sc}$ : 比較score的消耗 * $f$ : 呼叫function的消耗 old和new的時間分析以及其二者的時間差如下： * $T_\text{old}=T(4(P\cdot(C_{tag}+C_{s})))=T(4PC_{tag}+4PC_{sc})$ * $T_\text{new}=T(PC_{tag}+P_t(4C_{sc}+f))=T(PC_{tag}+4P_tC_{sc}+P_tf)$ * 時間差：$\Delta T=T_\text{new}-T_\text{old}=T(P_tf-3PC_{tag}-4C_{sc}(P-P_t))$ 整合後的判斷分支有 $k$ 條時： * $T_\text{old}=T(kPC_{tag}+kPC_{sc})$ * $T_\text{new}=T(PC_{tag}+k\cdot P_tC_{sc}+P_tf)$ * $\Delta T=T(P_tf-(k-1)PC_{tag}-k\cdot C_{sc}(P-P_t))$ > $P_t \le P$，因為有target的tag之玩家數量必定小於等於總玩家數 > $f, C_{tag}, C_{sc}$ 皆為常數，其時間複雜度為HashMap的 $O(1)$ > 當 $k$ 越多，優化的效果就越明顯 > 當 $P=P_t$ 時，其差值 $=T(P\cdot(f-(k-1)C_{tag})$，只要$f < (k-1)C_{tag}$ 即恆滿足優化註：此結果仍可以再更優化，詳細請看[指令效能分析]() --- ###### `more about` 其餘效能分析詳細請參考另一篇Hackmd文章：[Minecraft 指令效能分析](https://hackmd.io/@mccmd-analyzed/By-kvNtUO)