找回密码
 欢迎注册
查看: 17755|回复: 25

[擂台] 我觉得这个倒是可以比一比

[复制链接]
发表于 2008-4-17 08:47:52 | 显示全部楼层 |阅读模式

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

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

×
http://topic.csdn.net/u/20080415 ... d-821f2e5ff775.html
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 09:06:04 | 显示全部楼层
把内容转过来,不过这个利用的数学原理少
====================================================
我用了个最最笨的压缩方法,在P4,3.0G,512M内存的机器上运行了一天,没有出结果,然后跟踪估计了下时间,大约需要9天时间才能完成数据压缩,太慢了!不知道各位有没有好的压缩方法?

本人有近30万个vector <int>(每个vector <int>中的值为0~179),如:

vector <vector <int>> a;

a[0]={0,3,179}

a[1]={}//该vector为空

a[2]={2,6,8,56,119,36}

a[3]={0,3,179}

a[4]={1,2,3,4,5,6,7,8,9,10...,179}// “满”vector <int>,表示从0到179间的数均在该vector中

....

a[310000]=...

先要对上述31万个vector <int>进行压缩,压缩原则为
1.空vector <int>删除,如a[1]
2.“满”vector <int>删除,如a[4]
3.相同vector <int>删除其中一个,如a[0]和a[3]相同,则删除其中任意一个
4.互补vector <int>删除其中一个,互补的意思是两vector <int>不相交且其并集为“满”vector <int>
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 09:11:41 | 显示全部楼层
这个题目可如下操作
首先按尺寸排序,建尺寸索引
则尺寸为0的和为180的可删除了

然后对相同尺寸的,做一次遍历
删除完全相同的

互补的可按尺寸索引形成两个候选子序列
转换为小规模问题寻找

所有操作都先在尺寸索引里进行,仅是个标记操作
然后统一删除
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-17 09:14:00 | 显示全部楼层
呵呵,要那么多数学原理干啥,不知道曲高和寡么.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-17 09:19:07 | 显示全部楼层
就这样?太慢了吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 09:20:34 | 显示全部楼层


除了最后求互补的
都是O(N)算法啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 09:22:18 | 显示全部楼层


那帖子都说了
用位操作
很快的

用SSE2汇编
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 09:29:35 | 显示全部楼层
这个题目并不复杂,当然发这个人的问题犯了很多严重的错误,导致速度非常慢。
i)数据存储问题,显然里面的vector<int>应该用比特数组来表示,无论是直接用23个字节(其实为了对齐,还不如用24个字节),每个比特位表示一个数据是否出现,还是直接用STL中bitset都要好很多。这样至少可以节省大量的内存空间,减轻对内存的压力。
ii)无论用排序还是Hash方法都可以很好的解决这个问题,而决不能使用数据两两比较的方法。
使用hash的一种比较好的方法可以如下:
比如内部每个数据可以表示成179比特的数据,我们可以写成:
struct{
      long long x1:64;
     long long x2:64;
    long long x3:51;
    long long reverse:1;
};
其中,在表示方法中,如果这个数据中出现数字179,我们对所有数据取补,并且将reverse设置成1;不然,reverse设置为0,数据原样保存。
然后,我们对数据进行一次快速排序。
排序以后,在顺序查找,淘汰所有除了reverse项不同都同样的数据.(特殊情况是除了reverse项外,其他都是0的数据全部淘汰)
最后将没有淘汰的数据输出.输出时如果发现对应数据的reverse项为1时要将数据取反在输出。
对于30万个数据情况,应该可以在1秒钟之内完成

评分

参与人数 1金币 +2 鲜花 +2 收起 理由
liangbch + 2 + 2 观点精辟,我很赞同

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-17 09:29:38 | 显示全部楼层
不要吧,什么都上汇编?
先分析主要问题,都解决完了再用汇编那种东西在小数点后趋近极限。
您老的方法O(n)是O(n),干什么还要“除了最后求互补的”?
并且O(n)还分O(1n),O(2n)呢,离汇编远着呢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 09:31:01 | 显示全部楼层
原帖由 无心人 于 2008-4-17 09:20 发表


除了最后求互补的
都是O(N)算法啊

排序不是O(N)的,是O(Nlog(N)).
当然用Hash表理论上可以达到O(N),但是实际应用上,我觉得不会比用快速排序快
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 21:41 , Processed in 0.047271 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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