论坛 › 算法交流 › 关于一个运算优化的问题

shshsh_0510 发表于 2009-3-28 19:02:48

回复 188# litaoye 的帖子

原帖由 litaoye 于 2009-3-28 00:38 发表 http://bbs.emath.ac.cn/images/common/back.gif


是0.031，呵呵其实是大家的成绩，又优化了好几次，一直都是这个成绩，反正我到此算是才尽了
0.015就看各位了！
:b:快就是快，不用谦虚。

对这个我还有一点不太明白，为什么sort一下就会变快:Q:

无心人 发表于 2009-3-28 19:04:14

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

litaoye 发表于 2009-3-29 02:01:18

试了一下,出了一个编译错误!

这部分也确实属于调用次数较多的,不知道会比原来的快多少,原来的方法也就是几次位运算,似乎速度也还可以。

不过咱现在对汇编是一点不懂了，不知道这两种方法转化为汇编会差多少？

原帖由 无心人 于 2009-3-28 14:02 发表 http://bbs.emath.ac.cn/images/common/back.gif
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 ...

无心人 发表于 2009-3-29 08:53:45

少些了一个_
是__declspec(naked)

不好意思啊

litaoye 发表于 2009-3-29 12:51:41

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

原帖由 无心人 于 2009-3-29 08:53 发表 http://bbs.emath.ac.cn/images/common/back.gif
少些了一个_
是__declspec(naked)

不好意思啊

无心人 发表于 2009-3-29 12:54:33

50%左右吧

无心人 发表于 2009-3-29 12:57:17

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)
boolbitbool(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
shr eax, cl
and eax, 1
ret
}
}

8条
如果利用SSE2
可更短
但在某种意义上不如利用BT指令了
如果你的C/C++翻译成汇编，可能存在冗余指令
即更多指令了

另外，我那个版本
如果仅用0代表对应位是0，非零代表是1
则不需neg eax一条
即仅3条

liangbch 发表于 2009-4-2 17:53:47

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

无心人 发表于 2009-4-3 08:10:29

:b:

呵呵
还有可能改进么?

liangbch 发表于 2009-4-3 09:50:51

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

查看完整版本: 关于一个运算优化的问题