标题: Lua的长字符串合并算法 [打印本页] 作者: 51testing 时间: 2008-1-10 17:34 标题: Lua的长字符串合并算法 形如:
-- WARNING: bad code ahead!!
local buff = ""
for line in io.lines() do
buff = buff .. line .. "\n"
end
1.每次buff = buff .. line .. "\n",导致新建一块内存,复制原buff内存,销毁原buff内存.
2.由于GC内存回收机制的的存在使得当字符串为几十k时,程序效率无法接受.
作如下算法:
function newStack ()
return { "" } -- starts with an empty string
end
-- 将每个字符串加入到stack table中
-- 规定table中的字符串从尾至前为从长度小的字符串到长度长的字符串.
-- 故,在加入一字符串时,检查其是否长于尾部的字符串,若长于前字符串,与之相加.
-- 接着再向前判断前方的元素,若相加后的字符串前元素,再如此向前.
function addString (stack, s)
table.insert(stack, s) -- 塞入尾部
for i=table.getn(stack)-1, 1, -1 do
if(string.len(stack[i+1]) > string.len(stack)) then
stack = stack .. table.remove(stack) -- 移出尾部元素,并相加.
else
break
end
end
end
-- 调用
local s = newStack()
for line in io.lines() do
addString(s, line .. "\n")
end
s = toString(s)