回 帖 发 新 帖 刷新版面

主题:一个小方法

有时候可能需要用到循环队列,通常我们会这样遍历队列:
  如果需要一个N个元素的循环队列,用sub做下标,f表示队列的头,t表示尾部 
  for ( sub=f; sub != t ; )
    {
    ...
    sub = ++sub>=N ? 0 : sub;
    }
    
其实原理是一样的,只不过是用查表法来实现这一功能,下面我拿斐波那契数列来举例。
f(n) = f(n-1) + f(n-2);
下面的 b1,b2就是分别表示f(n-1),f(n-2)这两项的下标,cur表示的就是f(n)这一项的下标;
ret[cur]保存的是f(n),ret[b1],ret[b2]分别表示的是f(n-1),f(n-2); 
最开始ret放的是f(0),f(1),f(2);
计算f(3)的时候,b2,b1,cur按着顺时针的方向旋转一次;以后每次计算f(n)都会旋转一次。
下面是代码: [code=c]
#include <limits.h>
#include <errno.h>

#if  LONG_LONG_MAX  !=    9223372036854775807LL
#error  sizeof(unsigned long long) must be 4
#endif 

unsigned long long
( fun )(unsigned long long number)
{
const char sub[]={1,2,0}; /* 就是这个表 */
char       b2=0,   b1=1,   cur=2;
unsigned long long ret[]={0,1,1},   mask=(1ULL<<63);

if (number<3) return ret[number];

while(--number>1)
  {
  ret[ cur=sub[cur] ]  =  ret[ b1=sub[b1] ] + ret[ b2=sub[b2] ];
  //ret[ cur=(cur+1)%3 ]  =  ret[ b1=(b1+1)%3 ] + ret[ b2=(b2+1)%3 ];/* %如果不能用&代替,建议不要用这个方案 */
  if (ret[cur] & mask) /* 溢出 */
    {
    errno = ERANGE;
    return  ((unsigned long long)-1);
    }
  }

return ret[cur];
}
[/code]

回复列表 (共3个回复)

沙发

两个感觉,第一个是楼主厉害,第二个是程序没读明白,希望楼主的标新立异多用在算法、思路等上面,而不是用在编程风格上面。能写些容易读懂点的程序吗?你把多个功能的语句缩在一行里,这并不能提高效率,实现一个功能必然会使用一定量的汇编语句,编译器在编译的时候还是会把它们展开来,你把赋值写进数组下标对程序的效率会有提升?总而言之我觉得楼主你的编程风格很危险,踏踏实实去学,踏踏实实去编,这些华丽的东西不会给你带来任何好处。

板凳

用查表来代替if语句,有可能提升程序的性能,因为if语句对CPU的指令流水线有一定负面影响,而查表不会。但是查表会消耗内存,楼主的例子里面,因为表比较小(只有三个元素),所以看不出缺点,但如果对于“sub = ++sub>=N ? 0 : sub;”这样的语句,如果N特别大,则查表会消耗大量内存,并且对CPU的高速缓存来说也是一个考验,这样就不可取了。

斐波那契数列数列的基本算法本身就足够简单:
[code=c]unsigned long long fib(unsigned int number) {
    unsigned long long a = 1;
    unsigned long long b = 1;
    for (; number > 2; --number) {
        unsigned long long t = a + b;
        // 是否溢出?在此判断
        a = b;
        b = t;
    }

    return b;
}[/code]

3 楼

是我表达得不清楚。我本来想说的是 环形队列:用数组实现队列的时候有可能要移动数组元素。
用环形队列的思想来实现 斐波那契数列(用来读取队列数据的下标的循环是通过查表法来实现的,这样把队列变成了环形的)确实并不好,只是当时我没想到其他比较简单的例子才拿它来举例的。

我来回复

您尚未登录,请登录后再回复。点此登录或注册