美思 [Lua] 程式設計教學:實作陣列 (Array)、向量 (Vector)、矩陣 (Matrix)

Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

由於 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

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

關於作者

身為資訊領域碩士,美思認為開發應用程式的目的是為社會帶來價值。如果在這個過程中該軟體能成為永續經營的項目,那就是開發者和使用者雙贏的局面。

美思喜歡用開源技術來解決各式各樣的問題,但必要時對專有技術也不排斥。閒暇之餘,美思將所學寫成文章,放在這個網站上和大家分享。