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

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

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