荣誉版主
- 积分
- -2403
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2010-5-4
- 最后登录
- 1970-1-1
|
回复 wwwyhx
关键是你要频繁做访存,你又不能保证你的查表的表一定在cache里,只要有一次访问它不在cache里,嘿嘿,访问内存需要的时钟周期可是比加加减减神马的多几个数量级的哦。
这东西必然要到实际机器上跑一跑测一测的,究竟哪个效率更好从体系结构到操作系统都关系很大的。
有的cpu里面有专门的指令用来算popcount的,感觉上那一定超级快吧?有人测试过,sometimes没有并行的算法快,虽然看上去指令数更多,但是消耗的时钟周期却更少。
Etrnls 发表于 2011-5-2 00:39 ![]()
对cpu,体系结构啥的没啥研究,但是我的感觉(不确定)是~~
操作系统一般有提供以页面为单位,一定驻留内存的机制。
就算偶尔失配(没有其他太耗内存因素的干扰下几乎不可能),
也赶不上每个数多算那么几次*n的开销
我感觉那个操作花费的时钟周期啥的不会比直接读个内存取个数啥的少。
为啥popcount函数没用map方式可能是因为它觉得对于计算一个数来说,不值得分配一个256k内存再释放,这样内存分配释放的过程比较耗,但是如果需要计算很多数,就值得了。
同意因该测试得出结论,不过... 这里也没太大必要.. 大家发表一下意见就行了 |
|