用 Lua 程式設計：11.6 - Lua 程式語言

第一版是針對 Lua 5.0 編寫的。儘管在很大程度上仍然適用於後續版本，但仍有一些差異。
第四版針對 Lua 5.3，可在 Amazon 和其他書店購買。
購買本書，您也可以協助支援 Lua 專案。

11.6 – 字串緩衝區

假設您正在逐行讀取檔案，逐步建立字串。您的典型程式碼看起來像這樣

    -- WARNING: bad code ahead!!
    local buff = ""
    for line in io.lines() do
    buff = buff .. line .. "\n"
    end

儘管看起來很單純，但對於大型檔案而言，Lua 中的程式碼可能會造成巨大的效能損失：例如，讀取 350 KB 的檔案需要將近一分鐘。（這就是 Lua 提供 io.read("*all") 選項的原因，它可以在 0.02 秒內讀取整個檔案。）

這是為什麼呢？Lua 使用真正的垃圾回收演算法；當它偵測到程式使用過多記憶體時，它會遍歷所有資料結構並釋放不再使用的結構（垃圾）。通常，此演算法具有良好的效能（Lua 如此快速並非偶然），但上述迴圈會讓演算法表現最差。

為了瞭解發生了什麼事，讓我們假設我們位於讀取迴圈的中間；buff 已經是一個 50 KB 的字串，每行有 20 個位元組。當 Lua 串接 buff..line.."\n" 時，它會建立一個包含 50,020 個位元組的新字串，並從 buff 中複製 50 KB 到這個新字串。也就是說，對於每一行，Lua 都會移動 50 KB 的記憶體，而且會越來越多。在讀取 100 行新資料（僅 2 KB）後，Lua 已經移動了超過 5 MB 的記憶體。更糟的是，在指派之後

        buff = buff .. line .. "\n"

舊字串現在變成了垃圾。在兩個迴圈週期後，會有兩個舊字串，總計超過 100 KB 的垃圾。因此，Lua 正確地決定，這是執行垃圾回收器的時機，於是它釋放了這 100 KB。問題在於，這將每兩個週期發生一次，因此在讀取整個檔案之前，Lua 將執行垃圾回收器兩千次。即使在執行所有這些工作後，其記憶體使用量仍將大約是檔案大小的三倍。

這個問題並非 Lua 特有的：其他具有真正垃圾回收功能且字串為不可變物件的語言也會出現類似的行為，最著名的例子就是 Java。（Java 提供 StringBuffer 結構來改善這個問題。）

在我們繼續之前，我們應該注意到，儘管我說了這麼多，但這種情況並非常見問題。對於小字串，上述迴圈是沒問題的。要讀取整個檔案，我們使用 "*all" 選項，它會一次讀取檔案。但是，有時沒有簡單的解決方案。然後，唯一的解決方案就是更有效率的演算法。我們在此展示一個。

我們的原始迴圈以線性方式解決問題，將小字串一個一個串接至累加器中。這個新演算法避免了這種情況，而是使用二元方式。它會串接多個小字串，偶爾會將結果的大字串串接成更大的字串。演算法的核心是一個堆疊，它將已建立的大字串保存在底部，而小字串則從頂部進入。這個堆疊的主要不變性與廣受（至少在程式設計師之間）歡迎的河內塔類似：堆疊中的字串永遠不會出現在較短的字串之上。每當一個新字串推送到較短的字串之上時，演算法就會（且僅會）串接兩者。此串接會建立一個較大的字串，現在它可能比前一層中的鄰近字串更大。如果發生這種情況，它們也會被串接。這些串接會沿著堆疊向下進行，直到迴圈到達一個較大的字串或堆疊底部。

    function newStack ()
      return {""}   -- starts with an empty string
    end
    
    function addString (stack, s)
      table.insert(stack, s)    -- push 's' into the the stack
      for i=table.getn(stack)-1, 1, -1 do
        if string.len(stack[i]) > string.len(stack[i+1]) then
          break
        end
        stack[i] = stack[i] .. table.remove(stack)
      end
    end

若要取得緩衝區的最終內容，我們只需串接所有字串至底部即可。table.concat 函式執行此動作：它會串接清單中的所有字串。

使用這個新的資料結構，我們可以將程式改寫如下

    local s = newStack()
    for line in io.lines() do
      addString(s, line .. "\n")
    end
    s = toString(s)

這個新程式將我們原本讀取 350 KB 檔案所需的時間從 40 秒減少至 0.5 秒。呼叫 io.read("*all") 仍然更快，在 0.02 秒內完成工作。

實際上，當我們呼叫 io.read("*all") 時，io.read 使用的正是我們在此介紹的資料結構，但它是用 C 實作的。Lua 函式庫中的其他幾個函式也使用這個 C 實作。其中一個函式是 table.concat。使用 concat，我們可以簡單地收集表格中的所有字串，然後一次串接所有字串。由於 concat 使用 C 實作，因此即使對於巨大的字串也很有效率。

concat 函式接受一個選用的第二個引數，它是一個要插入在字串之間的分隔符號。使用這個分隔符號，我們不需要在每一行之後插入換行符號

    local t = {}
    for line in io.lines() do
      table.insert(t, line)
    end
    s = table.concat(t, "\n") .. "\n"

（io.lines 迭代器會傳回不含換行符號的每一行。）concat 會在字串之間插入分隔符號，但不會在最後一個字串之後插入，因此我們必須新增最後一個換行符號。這個最後的串接會複製結果字串，而它可能會很大。沒有選項可以讓 concat 插入這個額外的分隔符號，但我們可以欺騙它，在 t 中插入一個額外的空字串

    table.insert(t, "")
    s = table.concat(t, "\n")

concat 在這個空字串之前新增的額外換行符號會出現在結果字串的結尾，正如我們所希望的。