資料偏好

有沒有煩惱過問題 X 應該要用資料結構 Y 還是 Z 來處理?本篇文章將圍繞這種困擾來展開。

備註

本文中參考使用了「[什麼什麼]-時間」格式。該術語來自演算法分析中的 大 O 符號 (英文)

長話短說,這種方式是用來表示最糟情況下所需要的執行事件。用業餘的方式來說:

「隨著問題領域變大,演算法的執行時間長度…」

  • 常數時間, O(1) :「…不會增加。」

  • 對數時間, O(log n) :「…緩慢增加。」

  • 線性時間, O(n) :「…等速增加。」

  • …等。

試想一下需要在每幀處理 300 萬筆資料點的情況。這時候就沒辦法使用線性時間演算法,因為隨著資料大小的增加,執行時間也會大幅增加。相較之下,使用常數時間演算法來處理就沒有問題。

大致上來說,開發人員總是希望能儘可能避免使用線性時間操作。但,若只保持小規模的線性時間操作,且不需要常常有這類操作,則還算可接受。在需求間找到平衡點,並依據正在進行的任務選擇正確的演算法與資料型別即是使程式設計師技術有價值的部分。

陣列 vs. 字典 vs. 物件

Godot 將腳本 API 中所有的變數都保存在 Variant 類別內。Variant 可以保存 Variant 相容的資料結構,如 ArrayDictionary 以及 Object

Godot 以 Vector<Variant> 來實作陣列。引擎會將陣列的內容儲存在一段連續的記憶體當中。也就是說,陣列的元素是相鄰的。

備註

對不熟悉 C++ 的人來說,Vector 是在傳統 C++ 函式庫中陣列物件的名稱,是一種「樣板化 (Templated)」型別。這代表,Vector 內的記錄只能包含特定型別 (在角括號內標示)。因此,舉例來說, PoolStringArray 就是類似 Vector<String> 之類的東西。

連續記憶體儲存,也就代表了下列操作效能:

  • 迭代: 最快。最適合迴圈。

    • 操作:迭代要做的就是增加計數器來移動到下一筆資料。

  • 插入、移除、移動: 取決於位置。普通慢。

    • 操作:新增/移除/移動會需要移動相鄰的記錄 (才能騰出空間/填補空間)。

    • 從結尾 新增/移除 - 快速。

    • 從任意位置 新增/移除 - 慢。

    • 從最前面 新增/移除 - 最慢。

    • 從前面 進行插入/移除多筆資料,則...

      1. 反轉陣列。

      2. 執行從陣列 結尾 更改的迴圈。

      3. 重新反轉陣列。

      這樣一來,比起平均要複製 N 次大約 1/2 個陣列 (線性時間), 就只會產生 2 個陣列的副本 (一樣是常數時間,但比較慢)。

  • Get, Set: Fastest by position. E.g. can request 0th, 2nd, 10th record, etc. but cannot specify which record you want.

    • 操作:需要 1 個額外的操作來將陣列從起始位置移至需要的位置。

  • 搜尋: 最慢。找到一個值的索引/位置。

    • 操作:必須要迭代陣列並比較各個值,直到找到相符的元素。

      • 效能還會依據是否需要完整的搜尋而有所不同。

    • 若陣列有排序,則搜尋操作可達對數時間 (相對較快)。不過,業餘使用者可能會不太習慣這種方法。這種方法會需要在每次編輯陣列後進行重新排列,並編寫適用於有序陣列的搜尋演算法。

Godot 通過 OrderedHashMap<Variant, Variant> 來實作字典 (Dictionary) 型別。Godot 會儲存一個小型索引鍵/值配對的陣列 (初始化為 2^3 或 8 筆記錄)。當使用者存取數值時,這組陣列就會提供索引鍵。接著再對索引鍵進行 雜湊 ,如將其轉換為數字。這裡的「雜湊」是用於將索引計算到陣列中。由於是陣列,OHM 會快速地「查表」來將索引鍵對應到數值上。如果 HashMap 變得太滿的話,Godot 會將其大小增加到下一個 2 的冪次 (也就是 16 筆資料,然後是 32 筆…以此類推),然後重新建立這個架構。

雜湊是為了降低索引鍵碰撞的機率。若發生碰撞,表格就必須要為該數值重新計算另一個索引來處理前一個位置。這樣一來,就可以常數時間來存取所有記錄,但卻需要犧牲一些記憶體與執行效率。

  1. 對每個索引鍵雜湊任意次。

    • 雜湊操作為常數時間,所以即使某個演算法需要被執行超過一次,只要雜湊計算的數字不要太依賴表格的密度,就能保持高速。這樣一來…

  2. 維護表格持續增長的大小。

    • 雜湊表 (HashMap) 會維護穿插在表格間所沒有使用到的記憶體空間,來減少雜湊碰撞的機率並保持存取的速度。這也是為什麼雜湊表大小成長的速度是以 2 的冪次在成長的。

我們可以說,字典可以做一些陣列沒辦法做的任務。下面列出一些字典能做的操作:

  • 迭代: 快速。

    • 操作:在映射表內部的雜湊向量間迭代。回傳每個索引鍵。然後,使用者便能通過該索引鍵來跳至並回傳所需的值。

  • 插入、移除、移動: 最快。

    • 操作:雜湊給定的索引鍵。需要 1 個額外操作來找到適當的值 (陣列起始 + 偏移)。移動是由這其中的兩個操作組成的 (一個新增、一個刪除)。映射表為了保持其功能性,必須要做一些維護操作:

      • 更新記錄的有序列表。

      • 判斷表格的密度,決定是否有需要增加表格的大小。

    • 字典會記得使用者插入索引鍵的順序。這樣一來在執行迭代的時候就能確保可靠性。

  • 取值、設值: 最快。與 以索引鍵 查詢相同。

    • 操作:與插入/移除/移動相同。

  • 查詢: 最慢。需要找出值的索引鍵。

    • 操作:必須要在每個記錄間迭代,並比較各個值來找出相符合的項目。

    • 請注意,Godot 並沒有直接提供這個功能 (因為字典並非設計來做這項工作)。

Godot 實作物件的方法很單純,但卻有動態資料內容容器。物件會在被要求的時候查詢資料來源。舉例來說,當物件需要回答「你有沒有一個叫『position』的屬性?」這種問題時,物件可能會詢問 ScriptClassDB 。更多關於物件的資訊以及物件如何運作的資訊,請參考 在 Godot 中套用物件導向原則 一文。

此處有一個重要的細節,就是有關物件任務中的複雜度。每當物件執行一次這種多來源的查詢時,物件會執行 多個 迭代迴圈以及雜湊表查詢。而且,查詢的線性時間會依據物件的繼承與層級大小而異。若物件查詢的類別 (目前的類別) 沒有找到任何東西,則查詢會被傳遞到更上一層,直到最原始的 Object 類別。雖然這些操作單獨來看都很快,但事實上因為這些操作需要做到很多確認,所以會讓查詢比起查詢陣列或字典的兩種方法都來得慢。

備註

當開發人員提到腳本的 API 有多慢時,指的是這個查詢鏈很慢。跟經過編譯的 C++ 程式碼比起來,這些 C++ 程式在查詢會知道要讀取的準確位置,因此相比起來腳本 API 就不可避免地慢很多。腳本 API 必須要在嘗試存取資料前找過所有相關資料的來源。

GDScript 比較慢的原因就是因為在執行所有操作前都必須要經歷過一次這個系統。

C# 可以通過最佳化的 Bytecode 來以更快的速度處理一些內容。但是,若 C# 腳本要呼叫引擎的類別內容,或是腳本試圖存取腳本外部的東西,則還是需要走過一次這個過程。

NativeScript C++ 則更進一步,預設會將所有東西都保持在內部。呼叫外部結構的時候會經過腳本 API。在 NativeScript C++ 中,必須要手動註冊方法並將方法暴露給腳本 API。這樣一來,非 C++ 類別就可以通過 API 來找到這些方法。

因此,假設我們需要繼承 Reference 來建立一個資料結構,類似 Array 或 Dictionary,誰還要用 Object 而不用 Array 或 Dictionary 呢?

  1. 控制: 因為物件能建立更複雜的結構,所以我們可以將資料抽象化成抽象層,來確保對外的 API 不會因為內部資料結構的更改而需要跟著改變。而且,物件還可以有訊號,可以作出回應式的行為。

  2. 明確: 當使用到腳本與引擎類別定義的資料時,物件是可信任的資料結構。屬性中的值可能與使用者期望的不同,但是在使用時不需要擔心物件上是否有某個屬性。

  3. 便利: 在已有類似資料結構的情況下,就可以通過繼承現有類別來更輕鬆地製作資料結構。相較起來,陣列與字典並非適用於所有情況。

物件也讓使用者有機會製作更專門的資料結構。使用物件,開發人員就能設計客製化的列表、二元搜尋樹、堆積、Splay Tree、Graph、非交集集合以及其他選項。

可能有人會問,「為什麼不用 Node 來處理樹狀結構?」。其實,Node 節點包含了一些與客製化資料結構不相關的東西,因此,在自行製作樹狀結構的時候,可以考慮自行建立自製的 Node 型別。

extends Object
class_name TreeNode

var _parent : TreeNode = null
var _children : = [] setget

func _notification(p_what):
    match p_what:
        NOTIFICATION_PREDELETE:
            # Destructor.
            for a_child in _children:
                a_child.free()
// Can decide whether to expose getters/setters for properties later
public class TreeNode : Object
{
    private TreeNode _parent = null;

    private object[] _children = new object[0];

    public override void Notification(int what)
    {
        switch (what)
        {
            case NotificationPredelete:
                foreach (object child in _children)
                {
                    TreeNode node = child as TreeNode;
                    if (node != null)
                        node.Free();
                }
                break;
            default:
                break;
        }
    }
}

就這樣,我們能製作適用於特定功能的客製化結構。

列舉類型:整數 vs. 字串

大多數語言都提供了列舉類型,GDScript 也不例外。但與其他語言不同的是,GDScript 的列舉類型值只允許要嘛使用整數,要嘛就是字串 (而字串只允許在 GDScript 中使用 export 關鍵字時使用)。這裡便沿伸出了一個問題,「要使用哪一個?」

用一句話來回答的話,就是「哪個用習慣就用哪個。」。這項特性是 GDScript 特有的,而不是 Godot 中所有的腳本語言都這樣。GDScript 首先考慮的是易用性而非效能。

但技術上來說,整數型別的比較 (常數時間) 比字串比較 (線型時間) 要來得快。如果想保持與其他語言一樣的慣例,則應該用整數。

當我們想 印出 列舉類型時,就會遇到使用整數的主要問題了。使用整數時,嘗試印出 MY_ENUM 會得到 5 這樣的值,而不是 "MyEnum" 。如果要印出整數列舉類型,就必須要寫一個將字串值映射到各個列舉值的字典 (Dictionary)。

若使用列舉類型的主要是為了要印出數值,而且想將相關的概念群組化,則可以使用字串。這樣一來,就不需要在印出數值時使用另一個分開的資料結構。

AnimatedTexture vs. AnimatedSprite vs. AnimationPlayer vs. AnimationTree

在哪個情況下該用哪個 Godot 動畫類別?對於新的 Godot 使用者來說,可能無法馬上清楚答案。

AnimatedTexture 是引擎繪製為動畫循環的紋理貼圖,而不是靜態圖片。使用者可以進行如下操作……

  1. 在紋理貼圖的各個部分移動的速率 (FPS)。

  2. 紋理貼圖中包含的區域數量 (幀數)。

Godot 的 VisualServer 接著會依指定的速度來按照區域的順序繪製。好消息是,這個過程不會在引擎這邊產生額外的邏輯。但壞消息是,使用者幾乎沒什麼控制權。

另外也要注意,AnimatedTexture 是一個 資源 ,而不像這裡討論的其他東西是 節點 。我們可以建立一個 Sprite 節點,然後使用 AnimatedTexture 來當作 Sprite 的貼圖。或是 (其他動畫類別做不到的) 我們可以將 AnimatedTexture 作為圖塊來加到 TileSet 中,然後跟 TileMap 整合使用,來製作許多會在單一繪製呼叫中同時算繪的自動動畫背景。

當我們將 AnimatedSprite 節點與 SpriteFrames 資源一起使用時,就可以通過 SpriteSheet 來製作許多不同種類的動畫序列、反覆播放動畫,並且可以控制動畫的播放速度、區域偏移量與方向。這種使用方式盒適合用來控制基於影格的 2D 動畫。

如果有需要觸發其他與動畫更改有關的效果 (如,建立粒子效果、呼叫函式或是操作基於影格的動畫之其他周邊元素),則需要使用 AnimationPlayer 來搭配 AnimatedSprite。

當想設計更複雜的 2D 動畫系統時,AnimationPlayer 也是必要工具。更複雜的 2D 動畫系統包含…

  1. 剪影動畫: 在執行階段編輯 Sprite 的變換。

  2. 2D 網格動畫: 為 Sprite 的材質定義一個區域,並將其骨骼固定在裡面。接著我們為骨骼製作動畫,依據骨骼之間互相的關係來縮放紋理貼圖。

  3. 上述類型的組合。

雖然我們需要 AnimationPlayer 來設計遊戲的個別動畫序列,但 AnimationPlayer 也適合用來混合各個動畫,如,在這幾個動畫間平滑地轉換。我們在設計物件的時候,可能也會在動畫間設計出階層結構。這幾種狀況就很適合 AnimationTree 。有關使用 AnimationTree 更深入的指南,請參考 這裡