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