Lua 程式設計教學:雜湊表 (Hash Table) 和集合 (Set)

PUBLISHED ON MAR 7, 2018 — PROGRAMMING

雜湊表 (Hash Table)

由於 Lua 的表 (table) 內部即是雜湊表 (hash table),另外再以表重新實作雜湊表的意義不大;請各位讀者自列參考本系列文章有關表的章節即可。

集合 (Set)

集合是指數學上有關集合論 (set theory) 的概念;理論上,很多資料結構都可以用來實作集合,若考量效率,使用雜湊表 (hash table) 或樹 (tree) 來實作較佳;由於 Lua 的表即為雜湊表,會比另外實作樹好一些。通常筆者會將集合包成物件,因為集合論一些基本的操作,包括聯集、交集、差集等,若直接操作表會過於瑣碎。

由於程式碼略長,我們在這裡展示完整程式碼,讀者可自行前往閱讀。我們接著會分段展示相關程式碼。

首先,撰寫建構函式。此處我們撰寫兩種建構函式,一種建立空集合,一種從表中初始化集合:

function Set:new()
    self = {}
    self._set = {}
    setmetatable(self, Set)
    return self
end

function Set:fromData(data)
    local s = self:new()
    
    for _, e in ipairs(data) do
        s:add(e)
    end
    
    return s
end

由於集合儲存不重覆的元素,我們內部不儲存元素數量,僅儲存元素存在的狀態:

function Set:add(e)
    self._set[e] = true
end

利用表可以快速檢查元素是否存在:

function Set:contains(e)
    return self._set[e] == true
end

利用表也可以快速移除元素:

function Set:remove(e)
    if self._set[e] == true then
        self._set[e] = nil
    end
end

在檢查集合是否相等時,我們利用運算子重載簡化公開介面:

Set.__eq = function (a, b)
    for e in a:iter() do
        if not b:contains(e) then
            return false
        end
    end
    
    for e in b:iter() do
        if not a:contains(e) then
            return false
        end
    end
    
    return true
end

我們用先前提到的迭代器的手法走訪集合:

function Set:iter()
    local out = {}
    
    for k, _ in pairs(self._set) do
        table.insert(out, k)
    end
    
    local n = 0
    
    return function ()
        n = n + 1
        
        if n <= #out then
            return out[n]
        else
            return nil
        end
    end
end

我們將聯合 (union) 運算包在物件中,簡化外部公開介面:

Set.union = function (a, b)
    local out = Set:new()

    for e in a:iter() do
        out:add(e)
    end
    
    for e in b:iter() do
        out:add(e)
    end

    return out
end

有關交集 (intersection) 和差集 (difference) 的部分可自行觀看我們所附的連結。

TAGS: LUA, LUA 語法, SET, TABLE
comments powered by Disqus