平民程序 - linghuye's blog

天下风云出我辈,一入江湖岁月催。皇图霸业谈笑中,不胜人生一场醉。提剑跨骑挥鬼雨,白骨如山鸟惊飞。尘事如潮人如水,只笑江湖几人回。

随笔 - 221, 文章 - 0, 评论 - 680, 引用 - 0
数据加载中……

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[i])) then
    stack[i] = stack[i] .. 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

posted on 2006-01-15 15:20 linghuye 阅读(2004) 评论(1)  编辑 收藏 引用 所属分类: 游戏理论和技术

评论

# re: Lua的长字符串合并算法[未登录]  回复  更多评论   

toString是啥呀
2008-09-24 09:02 | abc
只有注册用户登录后才能发表评论。