技术说明 9

逐个部分创建字符串

摘要

在 Lua 中，“累积”字符串结果（即循环处理类似于 s = s..x 的代码）可能非常昂贵。本说明介绍了一种在 Lua 中逐个部分高效创建字符串的方法。

问题

假设您正在逐个部分构建一个字符串，例如逐行读取一个文件。您的典型代码看起来如下所示

-- WARNING: bad code ahead!!
local buff = ""
while 1 do
  local line = read()
  if line == nil then break end
  buff = buff..line.."\n"
end

尽管此代码看起来很无害，但对于大型文件，它在 Lua 中可能会导致巨大的性能损失：例如，读取一个 350 KB 的文件需要将近一分钟。

通常这不是问题。对于小字符串，上述循环是合适的。要读取整个文件，您可以使用 "*all" 选项，它会一次性读取文件。但有时您没有如此简单的解决方案。那么，唯一解决方案就是为您的问题找到一种更有效的算法。我们在此展示一种算法（算法，而不是问题）。

解决方案

该算法的核心是一个堆栈，它将已创建的大字符串保存在其底部，而小字符串则从顶部进入。此堆栈的主要不变性类似于程序员中流行的“河内塔”：堆栈中的字符串永远不会位于较短的字符串之上。每当一个新字符串被推送到较短的字符串之上时，算法就会（并且仅会）连接两者。此连接创建一个较大的字符串，现在它可能大于其在上一层中的邻居。如果发生这种情况，它们也会连接。这些连接会一直向下进行，直到循环到达一个较大的字符串或堆栈底部。

function newBuffer ()
  return {n=0}     -- 'n' counts number of elements in the stack
end

function addString (stack, s)
  tinsert(stack, s)       -- push 's' into the top of the stack
  for i=stack.n-1, 1, -1 do
    if strlen(stack[i]) > strlen(stack[i+1]) then break end
    stack[i] = stack[i]..tremove(stack)
  end
end

要获取缓冲区的最终内容，我们只需要连接底部的所有字符串即可

function toString (stack)
  for i=stack.n-1, 1, -1 do
    stack[i] = stack[i]..tremove(stack)
  end
  return stack[1]
end

使用此新数据结构，我们可以将我们的程序重写如下

local s = newBuffer()
while 1 do
  local line = read()
  if line == nil then break end
  addString(s, line.."\n")  
end
s = toString(s)

此新程序将我们读取 350 KB 文件的原始时间从 40 秒减少到 0.5 秒。（调用 read"*all" 仍然更快，可在 0.02 秒内完成工作。）

说明

为了理解朴素方法会发生什么，让我们假设我们正在读取过程中；buff 已经是一个 50 KB 的字符串，并且每行有 20 个字节。在分配之后

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

buff 是一个带有 50,020 字节的新字符串，而旧字符串现在是垃圾。经过两个循环周期后，buff 是一个带有 50,040 字节的字符串，并且有两个旧字符串，总共超过 100 KB 的垃圾。因此，Lua 正确地决定现在是运行其垃圾回收器的好时机，因此它释放了这 100 KB。问题是每两个周期就会发生这种情况，因此在完成循环之前，Lua 将运行其垃圾回收器两千次。即使做了所有这些工作，其内存使用量也将大约是文件大小的三倍。更糟糕的是，每个连接都必须将整个字符串内容（50 KB 且不断增长）复制到新字符串中。

此问题并非 Lua 独有：其他具有真正垃圾回收功能的语言（其中字符串是不可变对象）表现出类似的行为（Java 是最著名的示例）。

我们最初的循环对问题采取“线性”方法，将小字符串一个接一个连接到累加器中。新算法避免了这种情况，而是使用了二进制方法。它在它们之间连接了许多小字符串，并且偶尔将结果大字符串连接到更大的字符串中。

上次更新：2002 年 8 月 12 日星期一 15:51:58 EST