数学研发论坛

 找回密码
 欢迎注册
查看: 29381|回复: 211

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

[复制链接]
发表于 2009-3-12 14:00:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
精华
是一个ACM的题,地址如下。

http://acm.timus.ru/problem.aspx?space=1&num=1318

大概意思就是给出5000个左右的128位的整数,求:


我也作了不少优化(包括分治),虽然可以过,但似乎同别人的算法似乎还有不小的差距,请高手们帮我想想还有什么好的方法没有!
我想用二叉树可能会好一点,但思路还不太清晰。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 14:46:27 | 显示全部楼层
$A_k, A_j$什么关系,可以相等么?
首先排序么?

我看不懂他的意思
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 14:47:45 | 显示全部楼层
论坛有计算$log_10$的代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-12 14:48:07 | 显示全部楼层
可以相等,初始是无序的,不过可以排序!
另外忘了说明了,LOG10之后,只保留整数部分就可以!

原帖由 无心人 于 2009-3-12 14:46 发表
$A_k, A_j$什么关系,可以相等么?
首先排序么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 14:50:42 | 显示全部楼层
是$A_k, A_j$遍取所有的可能?

即如果有100个,则生成10000个XOR值??
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-12 14:53:55 | 显示全部楼层
原帖由 无心人 于 2009-3-12 14:50 发表
是$A_k, A_j$遍取所有的可能?

即如果有100个,则生成10000个XOR值??


是这个意思!然后取log10的整数部分,都加在一起!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 14:55:29 | 显示全部楼层
按照我目前的理解

如果无序,且遍取所有可能
是无需排序的

只要进行一次遍历就可以了
大概1000万次的XOR
然后求$log_10$
这个是整数算法
应该能在1秒左右完成
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 14:57:31 | 显示全部楼层
5000 的128位值还不需要用文件操作
直接能一次读取到内存

然后是个
for (i = 0; i < N - 1; i ++)
    for (j = i + 1, j < N; j ++)
的两重循环
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-12 15:00:21 | 显示全部楼层
就是测试128位数字的$ log_10$麻烦些

不过, 用个Cache,加上几个判断就能做好
完全的整数运算
很快的

看论坛有求32位的代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-12 15:04:02 | 显示全部楼层
我说一下我现在用的方法吧!先求出10^0 - 10 ^ 38,并分别计算最高位所在的位置。

对A数组排个序,然后只需计算A[k]同比A[k]小的数logXor就可以了,最后的结果*2

在计算过程中,先求出5000个数的最高位,并分类,如果最高位m高于10^n,且低于10^n+1,那么这个数同最高位小于m的数进行Xor并取log10后的结果,都是n,因此有些数是可以批量算的(但所占比例不是很大)。

基本上就是做了这些优化。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-7-22 11:14 , Processed in 0.057580 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表