Lua+字符串缓冲：concat的O(n²)陷阱

【语法算法】

字符串拼接的性能陷阱就这一行：

s = s .. item

每次 .. 都创建一个新字符串——循环拼接 n 次，Lua 内部分配 n 个临时字符串，总内存开销 O(n²)。table.concat 一次拼接，O(n)。今天拆开。

一、问题、方案、分界三段

字符串拼接的三段。问题：s = s .. item 每次拼接都创建新字符串——Lua 的字符串是不可变的，每次拼接都分配新内存、拷贝旧内容加新内容——循环 100 次就是 100 次内存分配加 100 次拷贝，总拷贝量是 O(n²)。方案：先把碎片放进表里，最后一次 table.concat——表里存的是引用不是拷贝，插入碎片是 O(1)，最后 concat 一次遍历所有碎片计算总长度、分配一次内存、一次拷贝到位——总开销 O(n)。分界：拼接次数少于 10 次用 .. 没问题（开销可忽略），超过 10 次必须用 table.concat——分界线不是拍脑袋，是 Lua 内部对短字符串有优化，少量拼接的实际开销和 concat 差不多。

graph LR
    A["循环拼接 s = s .. item"] --> B["每次分配新内存"]
    B --> C["拷贝旧内容+新内容"]
    C --> D["总开销 O(n²)"]
    E["table.concat(t)"] --> F["一次计算总长度"]
    F --> G["一次分配一次拷贝"]
    G --> H["总开销 O(n)"]

二、concat 的正确写法

local t = {}
for i = 1, 1000 do
    t[#t + 1] = "item_" .. i
end
local result = table.concat(t, ",")

t[#t + 1] 是 Lua 的 push 操作——往表尾插入元素是 O(1)——最后 table.concat(t, ",") 用逗号拼接所有元素——一次分配、一次拷贝、一次到位。

三、插入计数的技巧与分隔符的坑

t[#t + 1] 比 table.insert(t, v) 快——table.insert 是函数调用有开销，#t + 1 是直接的长度操作——循环里省的函数调用次数乘以循环次数就是省掉的总开销。分隔符也有坑：table.concat(t) 不传分隔符默认用空串拼接——如果要用逗号分隔必须显式传 ","——忘了传分隔符，所有元素粘成一坨，排查半小时。最后一条：拼接的元素如果本身是数字，table.concat 自动做 tostring 转换——但如果表里混了 nil，concat 直接报错——入表前过滤 nil，这是 concat 的使用纪律。