用 Lua 编程：11.6 - Lua 编程语言

第一版是针对 Lua 5.0 编写的。虽然在很大程度上仍然适用于更高版本，但有一些差异。
第四版针对 Lua 5.3，可在亚马逊和其他书店购买。
购买本书，您还可以帮助支持 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 个字节的新字符串，并将 50 KB 从 buff 复制到这个新字符串中。也就是说，对于每一行，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在此空字符串之前添加的额外换行符位于结果字符串的末尾，正如我们所希望的那样。