为什么需要将在堆栈底部创建的大字符串保存在 Lua 字符串缓冲区中

Question

我最近阅读了 Lua 中编程的 11.6 String Buffers 部分。作者给出了一个类似于汉诺塔的算法，在逐行读取文本文件时，将创建的大字符串保留在堆栈底部。

为什么这种方法需要在字符串缓冲区数据结构中？这是某种加速内存操作的技巧吗？

我不明白的是作者为什么要把小串串成大串？

例如，为什么不将其用作 addString 函数？

function addString (stack, s)
    table.insert(stack, s)    -- push 's' into the the stack
end

Answer 1

For example, why not just use this as an addString function?

因为您仍然需要一种方法来连接您插入的所有字符串。您可能会使用 table.concat 来执行此操作，但所提供的算法显示了如何在不使用 table.concat 函数的情况下（以合理的性能方式）完成此操作。您可以按照您的建议简单地使用 table.insert，但该示例显示的是描述您将如何提高性能（即使相同的算法已经实现并可供您使用）。

[已更新以解决评论中关于不同之处的问题]

让我们看看从 GC 角度来看有什么不同。

local t = 0
function addString (stack, s)
  table.insert(stack, s)
  for i=#(stack)-1, 1, -1 do
    if string.len(stack[i]) > string.len(stack[i+1]) then
      break
    end
    print(#(stack[i+1]), #(stack[i]))
    t = t + #(stack[i+1]) + #(stack[i])
    stack[i] = stack[i] .. table.remove(stack)
  end
end

local s = {""}
local tbl = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f"}
for _, line in ipairs(tbl) do
  addString(s, line)
end
while #s > 1 do
  local i = #s-1
  print(#(s[i+1]), #(s[i]))
  t = t + #(s[i+1]) + #(s[i])
  s[i] = s[i] .. table.remove(s)
end
print(t, s[1])

local s = ""
local t = 0
for _, line in ipairs(tbl) do
  print(#s, #line)
  t = t + #s + #line
  s = s .. line
end
print(t, s)

如果我们运行建议算法和原始算法，如上所示，我们可以看到第一个算法报告释放字符串的长度为 65，第二个算法报告为 136。这就是内存重新分配节省的来源（即使两种情况下的操作数相同）。

您可以在最简单的情况下看到它：1, 1, 1, 1。第一个算法将它们组合为 1+1、1+1，然后是 2+2，结果字符串为 4 和释放的（中间）字符串为 1,1,1,1,2,2，总共 8 个。

朴素算法会执行 1+1,2+1,3+1，得到相同的字符串 4，但释放的字符串为 1,1,1,1,2,3，总共 9 .

连接的字符串越多，优势就越大。

为什么需要将在堆栈底部创建的大字符串保存在 Lua 字符串缓冲区中

Why need to keep the large strings created in the bottom of the stack in Lua string buffer

lua