我们项目的服务器是C++结合Lua的形式，所以也对Lua有些兴趣，花了些时间去看，不得不说Lua这个语言确实很简洁，优美，灵活。

 

今天正在看Lua安装目录下的Examples，其中有一个fib.lua，这里是源码：

 

--

 fibonacci function with cache

--

 very inefficient fibonacci function

function fib(n)

    N=N+

1

    

if n<

2 

then

        

return n

    

else

        

return fib(n-

1)+fib(n-

2)

    

end

end

--

 a general-purpose value cache

function cache(f)

    

local c={}

    

return 

function (x)

        

local y=c[x]

        

if 

not y 

then

            y=f(x)

            c[x]=y

        

end

        

return y

    

end

end

--

 run and time it

function test(s,f)

    N=

0

    

local c=

os.clock()

    

local v=f(n)

    

local t=

os.clock()-c

    

print(s,n,v,t,N)

end

n=arg[

1] 

or 

24        

--

 for other values, do lua fib.lua XX

n=

tonumber(n)

print(

"",

"

n

",

"

value

",

"

time

",

"

evals

")

test(

"

plain

",fib)

fib=cache(fib)

test(

"

cached

",fib)

 

  

这里的优化思想是用一个映射表保存已经计算过的数，两个方法的对比天差地别。

这种优化思想应该是比较常见的优化了，这里巧妙的是用的闭包，对原来的fib方法经过cache这层转换后，语义已经改变了。

当再次调用fib时实际上不再是调用之前定义的那个fib，而是由cache返回的一个匿名方法。

而更有意思的是，fib会递归的调用自身，由于语义的改变，变成调用寻附上匿名方法。

cache这里的闭包保存了两个值，一个f（即原来的fib），另一个是c（映射表） 。

所以这里的调用通过cache巧妙的转换之后达到的优化的目的。

 

我用AS3把代码重新翻译了一下：

 

var fib:Function = 

function(n:int):int

{

    

if (n < 2)

    {

        

return n;

    }

    

else

    {

        

return fib(n - 1) + fib(n - 2);

    }

}

var cache:Function = 

function(f:Function):Function

{

    

var dic:Dictionary = new Dictionary();

    

return 

function(n:int):int

    {

        

var r:int = dic[n];

        

if (!r)

        {

            r = f(n);

            dic[n] = r;

        }

        

return r;

    }

}

var num:int = 30;

XPerf.perf("fib");

Log.print(fib(num))

XPerf.stop();

fib = cache(fib);

XPerf.perf("cache")

Log.print(fib(num))

XPerf.stop();

 

 

*这里关键的是fib只能定义成一个Function变量 ，而不能定义成一个成员方法。 

 

*附XPerf、Log代码

package org.easily.debug

{

    

import flash.utils.getTimer;

    

public 

class Log

    {

        

public 

static 

var enabled:

Boolean = 

true;

        

        

public 

static 

function print(...args):void

        {

            

if (enabled)

            {

                

var msg:

String = getTimer().toString() + " : ";

                

for each (

var arg:

Object 

in args)

                {

                    msg += arg.toString() + " ";

                }

                trace(msg);

            }

        }

    }

}

package org.easily.debug

{

    

import flash.utils.getTimer;

    

public 

class XPerf

    {

        

private 

static 

var data:Array = [];

        

public 

static 

function perf(name:

String):void

        {

            

var obj:

Object = {name:name, time:getTimer()};

            data.push(obj);

        }

        

public 

static 

function stop():void

        {

            

var obj:

Object = data.pop();

            

var len:int = data.length;

            

var t:

String = "";

            

for (

var i:int = 0; i < len; i++)

            {

                t += ">";

            }

            Log.print("Perf:" + t + obj.name + "=" + (getTimer() - obj.time) + " ms");

        }

    }

}