关于一个运算优化的问题

liangbch · 发表于 2009-3-13 10:08:07

我把ACM1000想复杂了，随便写了一个，轻易通过。

litaoye · 发表于 2009-3-13 13:54:35

原帖由 liangbch 于 2009-3-13 09:52 发表
我的一朋友问我一个问题，A+B 怎么回事？见http://acm.timus.ru/problem.aspx?space=1&num=1000
楼主应该是做过A+B的，这个问题中，既没有给出两个数的类型（整数，浮点数），有没有给出数的范围，你能告诉做这个 ...

呵呵,是最简单的int32加法,属于让你熟悉一下ACM环境!

我被那道题弄晕了,昨晚上好不容易修改了一个自己觉得满意的方法,本地测试要比以前的快,没想到放上去一跑,第3个测试就超时了!

搞不清怎么回事儿了!

litaoye · 发表于 2009-3-13 14:01:00

我用c#做的排序,10000条大概13毫秒吧!

昨天统计了一下,测试的是1-10000,本应当计算50000000次的,经过优化后,需要算17000000,大概是1/3吧!

看来优化效果不是很明显!

原帖由 无心人 于 2009-3-13 10:04 发表
宝宝，
用跳转表写
应该能消除大部分跳转指令

无心人 · 发表于 2009-3-13 14:41:58

你有测试文本么?

懒得用随机数自己生成

哈哈

无心人 · 发表于 2009-3-13 14:49:28

现在要两个表
1、是2进制最高位与log_10的值对照表
2、是1表在某些值上需要比较大小的值的表

无心人 · 发表于 2009-3-13 14:53:16

bsr可以这么用
struct int128
{
      DWORD u[4];
}

__declspec(naked)
DWORD __fastcall log2(DWORD n)
{
      __asm
   {
      bsr  eax, ecx
      ret
      }
}

DWORD inline log2_128(int128 n)
{
      return (n.u[3] != 0? log2(n.u[3]) + 96 : (n.u[2] != 0 ? log2(n.u[2]) + 64 : (n.u[1] != 0 ? log2(n.u[1])  + 32: log2(n.u[0]))))
}

litaoye · 发表于 2009-3-13 14:54:45

原帖由 无心人 于 2009-3-13 14:41 发表
你有测试文本么?

懒得用随机数自己生成

哈哈

也是随机生成的!

litaoye · 发表于 2009-3-13 15:05:47

原帖由 litaoye 于 2009-3-13 14:54 发表

也是随机生成的!

说实话,用这个随机生成的测我现在的程序,那真是跑的刷刷的,5000万次几乎只要算30-50万次就可以了!

不过如果数据大量重复的话,会比较慢!

无心人 · 发表于 2009-3-13 15:24:37

好，谢谢了

我有时间我写个看看

litaoye · 发表于 2009-3-13 15:26:39

似乎就是重复数据的问题,又针对这点修改了一下程序,test#3果然就通过了,而且还挺快的.

账号		自动登录	找回密码
密码			欢迎注册

[求助] 关于一个运算优化的问题