51Testing软件测试论坛

标题: 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)

Reference:
Programming in lua




欢迎光临 51Testing软件测试论坛 (http://bbs.51testing.com/) Powered by Discuz! X3.2