Lua 程式設計教學:陣列 (Array)、向量 (Vector)、矩陣 (Matrix)

PUBLISHED ON FEB 28, 2018 — PROGRAMMING

    由於 Lua 僅支援 table 這種資料結構,若要在程式中使用其他資料結構,需用模擬的方式;除非資料量大,用 table 模擬通常也夠用。Lua 官方教材對於資料結構的章節較注重其內部實作,筆者會習慣用物件包裝一下,將一些常用的功能包成方法,便於日後呼叫。由於資料結構的範例較長,我們會拆開在幾個章節中。

    註:在 The Implementation of Lua 5.0 這篇報告中提到 table 內部的實作方式,在 4.0 版之前,table 內部就是雜湊表,在 5.0 版以後,table 內部混合陣列和雜湊表兩種資料結構,Lua 會視情境自動呼叫合適的結構。對 Lua 程式撰寫者來說,不太會接觸到這些內部細節,將其視為雜湊表即可。

    陣列 (Array)

    Table 以數字做為索引時,可視為陣列,不太需要再做額外的包裝。可參考前文有關 table 的使用方式。

    向量 (Vector)

    向量內部以陣列表示即可,但直接操作陣列過程較為瑣碎;筆者會稍微用物件包裝一下向量,因 Lua 支援運算子重載,將向量包成物件後,可用較自然的方式呼叫向量。由於範例較長,可到這裡觀看完整程式碼,我們分段展示 Lua 實作。

    Lua 沒有制式的建構子 (constructor),只要名稱合理,可自由命名建構函式。我們在此處建立兩種建構子,一個建立空向量,一個從表 (table) 中初始化向量:

    function Vector:new(size)
      self = {}
      self._array = {}
    
      for i = 1, size do
        self._array[i] = 0
      end
    
      setmetatable(self, Vector)
      return self
    end
    
    function Vector:fromTable(t)
      local v = Vector:new(#t)
      for i = 1, #t do
        v:setAt(i, t[i])
      end
      return v
    end

    我們建立向量的 getter 和 setter,以存取向量中的元素:

    function Vector:at(i)
      return self._array[i]
    end
    
    function Vector:setAt(i, e)
      self._array[i] = e
    end

    由於 Lua 的陣列內部即儲存陣列長度的資訊,我們不需額外儲存,需要長度時直接呼叫內部陣列的長度即可:

    function Vector:len()
      return #(self._array)
    end

    為了簡化範例,我們這裡僅實作基本的四則運算,按照其數學定義實作即可;我們這裡展示加法的實作:

    Vector.__add = function(a, b)
      local function _scalar_add(s, v0)
        local v = Vector:new(v0:len())
        for i = 1, #v0 do
          v:setAt(i, v0:at(i) + s)
        end
        return v
      end
    
      if type(a) == "number" then
        return _scalar_add(a, b)
      end
    
      if type(b) == "number" then
        return _scalar_add(b, a)
      end
    
      assert(a:len() == b:len())
      local v = Vector:new(a:len())
      for i = 1, a:len() do
        v:setAt(i, a:at(i) + b:at(i))
      end
      return v
    end

    我們這裡充分善用運算子重載的機制,之後在進行向量四則運算時即可用內建的運算子,在語法上會比較簡潔。

    由於向量運算分為兩個向量間的運算和向量及純量間的運算,在我們的實作內部會根據值使用不同的運算方式。要注意減法和除法不具交換性,對於不同順序要實作兩次運算過程。

    矩陣 (Matrix)

    有兩種方式可以表示矩陣:

    • Table of table (即陣列的陣列)
    • 將二維索引轉為一維索引,內部仍然使用陣列

    一般來說,一維陣列比陣列的陣列效率好。雖然效率不是我們最重要的考量,這裡的範例也是以一維陣列來儲存矩陣。

    由於程式碼較長,我們將其放在這裡,讀者可自行前往觀看。我們會分段展示程式碼。

    我們建立兩種建構子,一種建立特定大小的空矩陣,一種從二維表中初始化矩陣:

    function Matrix:new(c, r)
        self = {}
        self._col = c
        self._row = r
        self._mtx = {}
        
        for i = 1, c * r do
            self._mtx[i] = 0
        end
        
        setmetatable(self, Matrix)
        
        return self
    end
    
    function Matrix:fromData(data)
        local r = #data
        local c = #(data[1])
        
        local m = self:new(c, r)
        
        for i = 1, c do
            for j = 1, r do
                m:setAt(i, j, data[j][i])
            end
        end
        
        return m
    end

    矩陣是二維的資料,大小會分為 column 和 row 兩種:

    function Matrix:col()
        return self._col
    end
    
    function Matrix:row()
        return self._row
    end

    建立 getter 和 setter 是基本的工作:

    function Matrix:at(c, r)
        local _c = c - 1
        local _r = r - 1
    
        return self._mtx[_c + _r * self:col() + 1]
    end
    
    function Matrix:setAt(c, r, value)
        local _c = c - 1
        local _r = r - 1
        
        self._mtx[_c + _r * self:col() + 1] = value
    end

    這裡以矩陣加法為例,展示如何進行矩陣的四則運算:

    Matrix.__add = function (a, b)
        local _scalar_add = function (s, m)
            local out = Matrix:new(m:col(), m:row())
            
            for i = 1, m:col() do
                for j = 1, m:row() do
                    out:setAt(i, j, s + m:at(i, j))
                end
            end
            
            return out
        end
        
        if type(a) == "number" then
            return _scalar_add(a, b)
        end
        
        if type(b) == "number" then
            return _scalar_add(b, a)
        end
        
        assert(a:col() == b:col())
        assert(a:row() == b:row())
        
        local out = Matrix:new(a:col(), a:row())
        
        for i = 1, a:col() do
            for j = 1, a:row() do
                out:setAt(i, j, a:at(i, j) + b:at(i, j))
            end
        end
        
        return out
    end

    矩陣乘法有三種,一種是成對元素間逐一相乘,一種是內積 (dot product),一種是外積 (cross product)。這裡展示內積的實作:

    Matrix.dot = function (a, b)
        assert(a:col() == b:row())
    
        local out = Matrix:new(a:row(), b:col())
    
        for i = 1, a:row() do
            for j = 1, b:col() do
                local temp = 0
                
                for k = 1, a:col() do
                    temp = temp + a:at(k, i) * b:at(j, k)
                end
                
                out:setAt(j, i, temp)
            end
        end
        
        return out
    end

    基本上,向量和矩陣的實作都不會太難,重點是熟悉其數學定義後,將其轉換成相對應的程式碼即可。

    comments powered by Disqus