关于一个运算优化的问题

shshsh_0510

原帖由 litaoye 于 2009-3-28 00:38 发表 是0.031，呵呵其实是大家的成绩，又优化了好几次，一直都是这个成绩，反正我到此算是才尽了 0.015就看各位了！

快就是快，不用谦虚。 对这个我还有一点不太明白，为什么sort一下就会变快

无心人

我估计是Cache数据到二级缓存造成的

litaoye

试了一下,出了一个编译错误! 这部分也确实属于调用次数较多的,不知道会比原来的快多少,原来的方法也就是几次位运算,似乎速度也还可以。 不过咱现在对汇编是一点不懂了，不知道这两种方法转化为汇编会差多少？

原帖由 无心人 于 2009-3-28 14:02 发表 bool bitbool(UINT128 *Item,int index) { DWORD * cItem = (DWORD *)Item; int bit = index >> 5; int current = index & 0x1F; return (*(cItem + bit) >> current) & 1; } 这个可以改成： _declspec(na ...

无心人

少些了一个_ 是__declspec(naked) 不好意思啊

litaoye

其实相比给出程序,给我讲一下这两者转化为汇编,效率差距有多大?会更有意义!

原帖由 无心人 于 2009-3-29 08:53 发表 少些了一个_ 是__declspec(naked) 不好意思啊

无心人

50%左右吧

无心人

bool bitbool(UINT128 *Item,int index) { DWORD * cItem = (DWORD *)Item; int bit = index >> 5; int current = index & 0x1F; return (*(cItem + bit) >> current) & 1; } 这个最优化的汇编是 假设采取__fastcall调用方式 __declspec(naked) bool bitbool(UINT128 *Item,int index) { /* DWORD * cItem = (DWORD *)Item; int bit = index >> 5; int current = index & 0x1F; return (*(cItem + bit) >> current) & 1; */ __asm { mov eax, index mov ecx, eax shr eax, 5 and ecx, 31 mov eax, dword ptr Item[4 * eax] shr eax, cl and eax, 1 ret } } 8条 如果利用SSE2 可更短 但在某种意义上不如利用BT指令了 如果你的C/C++翻译成汇编，可能存在冗余指令 即更多指令了 另外，我那个版本 如果仅用0代表对应位是0，非零代表是1 则不需neg eax一条 即仅3条

liangbch

我的0.062秒的源代码，提交ID: 2516093， 见 http://acm.timus.ru/rating.aspx?space=1&num=1318

游客，本帖隐藏的内容需要积分高于 1000 才可浏览，您当前积分为 0

无心人

呵呵 还有可能改进么?

liangbch

用我自己的算法，性能应该到头了。使用楼主的代码，将关键部分用汇编优化，或许有提速的可能