为什么需要在Lua字符串缓冲区中保留创建的大字符串

2021-9-1 15:58:59
收藏：0
阅读：153
评论：1

我最近阅读了《Programming in Lua》的11.6节“String Buffers”部分。作者提供了一种类似汉诺塔的算法，用于在逐行读取文本文件时将创建的大字符串保存在堆栈底部。

这种方法为什么需要在字符串缓冲区数据结构中使用？这是一种加快内存操作的黑科技吗？

我不明白的是，为什么作者要将小字符串连接成一个大字符串？

例如，为什么不只是使用这个作为“addString”函数？

function addString (stack, s)
    table.insert(stack, s)    -- 将's'压入堆栈中
end

原文链接 https://stackoverflow.com/questions/69014494

点赞
stackoverflow用户1442917
stackoverflow用户1442917

例如，为什么不仅使用此函数作为addString函数？

因为你仍需要一种方法来连接你插入的所有字符串。你可能会使用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)

如果我们运行建议的算法和naive算法，如上所示，我们可以看到第一个算法报告了65个释放字符串的长度，第二个算法报告了136个。这就是内存重新分配的节省之处（尽管在两种情况下操作数量相同）。

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

naive算法将执行1+1，2+1，3+1，结果字符串相同为4，但是释放的字符串为1,1,1,1,2,3，总共为9。

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

2021-09-01 17:46:02

作者:

stackoverflow用户4658633

stackoverflow用户4658633
推荐文章