向“世界上最快的判断32位整数二进制中1的个数的算法”挑战

connet

原帖由 unicorns 于 2006-7-20 11:03 发表
http://bbs.chinaunix.net/viewthr ... p;extra=&page=1

一年多了.........

果然以前有人讨论过

isjfk

AMD 平台内存速度一直是拖后腿的地方，因此集中在 CPU 寄存器上进行的运算反而比需要访问内存的优化算法快。Intel 平台的内存带宽很大，lz 算法的优势就体现出来了。

看来优化的时候平台的特性也必须考虑进去，空间换时间并不总是有效的。

liubinbj

楼主如果真是想挑战最快，那请用我的算法来对比吧，在我的《放出一个世界上最快的判断32位整数二进制中1的个数的算法》帖子里，楼主用于对比的方法已经被证明比我的算法慢，它不是最快的。

yulc

原帖由 isjfk 于 2006-7-20 11:44 发表
AMD 平台内存速度一直是拖后腿的地方，因此集中在 CPU 寄存器上进行的运算反而比需要访问内存的优化算法快。Intel 平台的内存带宽很大，lz 算法的优势就体现出来了。

看来优化的时候平台的特性也必须考虑进去， ...

楼上的,请教一下.
如书上所说, 不管你内存速度有多快, 但总是比不过寄存器的呀, 难道Inter平台上,访问内存的速度会快过寄存器?

isjfk

我说过内存速度比寄存器快？

我只是说空间换时间的方法在内存 IO 比较低的平台上可能得不到预期的效果。

内存 IO 只是影响算法速度的一个因素，没有多少算法是只访问寄存器或者只访问内存的。

yulc

理解错了...
我知道你要表达的意思了.

connet

原帖由 liubinbj 于 2006-7-20 11:48 发表
楼主如果真是想挑战最快，那请用我的算法来对比吧，在我的《放出一个世界上最快的判断32位整数二进制中1的个数的算法》帖子里，楼主用于对比的方法已经被证明比我的算法慢，它不是最快的。

你怎么测试的呢？
我测试下来你的最慢。

connet

P4 2.8G redhat 9.0, kernel 2.4.32
不优化    liubinbj方法    网上方法     我的方法
              154.6641     63.7537    31.7395
O2优化    liubinbj方法   网上方法     我的方法
              78.1829       19.3305    13.0671

VIA C7 1.3G , 2.6.16.22
不优化    liubinbj方法   网上方法      我的方法
                431.7528   151.2660   169.5686
O2优化    liubinbj方法   网上方法     我的方法
                277.4617    58.1803    59.8410

AMD64 3000+  FC5, 2.6.16-1.2122_FC5
不优化    liubinbj方法   网上方法     我的方法
               180.3114    51.2969    62.6047
O2优化    liubinbj方法   网上方法     我的方法
               85.9299       21.0763    24.1614

任何平台下 liubinbj方法 最慢， 是其余方法的 3-5倍时间
欢迎挑战，欢迎测试
程序存为 one.c
不优化 gcc -o one one.c
优化  gcc -O2 -o one2 one.c
运行 one 和 one2 得到结果

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

unsigned int count=0x7FFFFFFF;


    static struct timeval _tstart, _tend;
    static struct timezone tz;

    void time_start(void)
    {
        gettimeofday(&_tstart, &tz);
    }
    void time_end(void)
    {
        gettimeofday(&_tend,&tz);
    }

    double time_val()
    {
        double t1, t2;

        t1 =  (double)_tstart.tv_sec + (double)_tstart.tv_usec/(1000*1000);
        t2 =  (double)_tend.tv_sec + (double)_tend.tv_usec/(1000*1000);
        return t2-t1;
    }
   
unsigned int func(unsigned int x)
{
    x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
    x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 0-4 in 4 bits
#if 1
    // Version 1
    x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 0-8 in 8 bits
    x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 0-16 in 16 bits
    x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); // 0-31 in 32 bits
    return x;
#else
    // Version 2
    x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
    x += x >> 8; // 0-16 in 8 bits
    x += x >> 16; // 0-32 in 8 bits
    return x & 0xff;
#endif
}

int one_in_char[256];
int func2(unsigned int  *v)
{
//    int n=v;
    unsigned char *ptr=(unsigned char *)v;
    return one_in_char[ptr[0]]+one_in_char[ptr[1]]+one_in_char[ptr[2]]+one_in_char[ptr[3]];
}

int func3(unsigned int n){
      
        int count=0;
        //高16位
        if(n&0xFFFF0000) {
                //高8
                if(n&0xFF000000) {
                        //高4
                        if(n&0xF0000000) {
                                if(n&0x10000000) count++;
                                if(n&0x20000000) count++;
                                if(n&0x40000000) count++;
                                if(n&0x80000000) count++;
                        }
                        //低4
                        if(n&0x0F000000) {
                                if(n&0x01000000) count++;
                                if(n&0x02000000) count++;
                                if(n&0x04000000) count++;
                                if(n&0x08000000) count++;
                        }                       
                }
                //低8
                if(n&0x00FF0000) {
                        //高4
                        if(n&0x00F00000) {
                                if(n&0x00100000) count++;
                                if(n&0x00200000) count++;
                                if(n&0x00400000) count++;
                                if(n&0x00800000) count++;
                        }
                        //低4
                        if(n&0x000F0000) {
                                if(n&0x00010000) count++;
                                if(n&0x00020000) count++;
                                if(n&0x00040000) count++;
                                if(n&0x00080000) count++;
                        }      
                }
        }
      
        //低16位
        if(n&0x0000FFFF) {
                //高8
                if(n&0x0000FF00) {
                        //高4
                        if(n&0x0000F000) {
                                if(n&0x00001000) count++;
                                if(n&0x00002000) count++;
                                if(n&0x00004000) count++;
                                if(n&0x00008000) count++;
                        }
                        //低4
                        if(n&0x00000F00) {
                                if(n&0x00000100) count++;
                                if(n&0x00000200) count++;
                                if(n&0x00000400) count++;
                                if(n&0x00000800) count++;
                        }      
                }
                //低8
                if(n&0x000000FF) {
                        //高4
                        if(n&0x000000F0) {
                                if(n&0x00000010) count++;
                                if(n&0x00000020) count++;
                                if(n&0x00000040) count++;
                                if(n&0x00000080) count++;
                        }
                        //低4
                        if(n&0x0000000F) {
                                if(n&0x00000001) count++;
                                if(n&0x00000002) count++;
                                if(n&0x00000004) count++;
                                if(n&0x00000008) count++;
                        }      
                }
        }

        return count;
}

void test_1()
{
  unsigned int i;
  char v, v2=0;
  time_start();
  for (i=0; i<count; i++)
    {
      v = func(i);
       v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
    }
  time_end();
        printf("test func use %0.4f seconds, v2=%d\n",time_val(), v2);
}

void test_2()
{
  unsigned int i;
  char v, v2=0;
  for (i=0; i<256; i++)
    one_in_char[i]=i%8;  /* 这 256 为硬编码， 为简便起见，随便设，不影响计算时间 */
  time_start();
  for (i=0; i<count; i++)
    {
      v = func2(&i);
       v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
    }
  time_end();
        printf("test func2 use %0.4f seconds, v2=%d\n",time_val(), v2);
}

void test_3()
{
  unsigned int i;
  char  v, v2=0;
  time_start();
  for (i=0; i<count; i++)
    {
      v = func3(i);
       v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
    }
  time_end();
        printf("test func3 use %0.4f seconds, v2=%d\n",time_val(), v2);
}

int main(int argc, char **argv)
{
  test_1();
  test_2();
  test_3();
  return 0;
}

Arghawk

你这个方法跟http://bbs.chinaunix.net/viewthr ... p;extra=&page=1里面那个方法是一样的嘛，只是他算的是char中有多少个1，你算的是一个int中有多少个1

connet

原帖由 Arghawk 于 2006-7-20 13:56 发表
你这个方法跟http://bbs.chinaunix.net/viewthr ... p;extra=&page=1里面那个方法是一样的嘛，只是他算的是char中有多少个1，你算的是一个int中有多少个1

恩， 我看到了， 前面  unicorns  已经告诉我了。

你有更好的方法？