用Redis进行fibonacci数列计算

Redis 2.6就快要发布了,预计下周应该会发布第一个RC版本。2.6 版本的最大亮点莫过于对lua脚本的支持,这一灵活性的加入,让Redis的角色又会进行一些转变,相信又会催生出很多新的用法。下面就是一个有意思的脚本,它的目的是使用Redis的lua功能进行fibonacci数列的计算。

简单介绍一下fibonacci数列,fibonacci数列是以其发现者,法国数学家Leonardo Fibonacci命名,它的规则是数列中的某个数总等于其前面两个数之和,如下:

1, 1, 2, 3, 5, 8, 13, 21, 34 ….

关于fibonacci的神奇之处就不多说了,看官们有兴趣wiki之就行了。

对于这个数列,问题经常是求其从1开始的第N项是多大。最简单的算法莫过于从头开始加,经过N次运算后就能得出来。在程序实现上可以用递规。而另一种优化的方法是将计算结果存起来,这样尽可能的利用已计算的数据来减少运行步骤。

好了,介绍就到这里,下面我们来看看Redis结合lua脚本的实现,可以说是计算加缓存的一个完美结合。

require "redis"

r = Redis.new

LuaScript = <<EOF
function best online casino  fib(n)
 if n < 2 then return n end

 local a = redis.call("hget",KEYS[1],n-1) or fib(n-1)
 local b = redis.call("hget",KEYS[1],n-2) or fib(n-2)
 local ret = a b
 redis.call("hset",KEYS[1],n,ret)
 return ret
end

return fib(tonumber(ARGV[1]))
EOF

puts r.eval(LuaScript,1,:fibcache,ARGV[0])

上面在调用这个函数的时候,在没有数据的时候通过递规调用来获取相应的值。如果N-1或N-2已缓存,就直接取缓存,不用计算。然后计算完成后再把N对应的数值进行缓存。这样就把计算和存储完美的结合起来了。

关于Redis lua脚本能做的一些好玩有用的事,相信还有很多,等待大家来发掘。也欢迎将有趣的用法分享到NoSQLFan。

本文来源:blog.sparsegraph.com

anyShare分享此文章的同学,将有机会送我iphone5!
          

无觅相关文章插件,快速提升流量

分类 Redis · tag , ,

  1. 哈哈,乍一看一位是ruby写的呢,原来是lua
    给个ruby的fib数列的写法:

    hash = Hash.new{|h,k|h [k] = h[k-1] + h[k-2]}
    h[0]=0
    h [1] =1
    h[100]是瞬间的事情