shshsh_0510 发表于 2008-4-17 08:47:52

我觉得这个倒是可以比一比

http://topic.csdn.net/u/20080415/10/a676aaa4-766e-4429-a86d-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,3,179}

a={}//该vector为空

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

a={0,3,179}

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

....

a=...

先要对上述31万个vector <int>进行压缩,压缩原则为
1.空vector <int>删除,如a
2.“满”vector <int>删除,如a
3.相同vector <int>删除其中一个,如a和a相同,则删除其中任意一个
4.互补vector <int>删除其中一个,互补的意思是两vector <int>不相交且其并集为“满”vector <int>

无心人 发表于 2008-4-17 09:11:41

这个题目可如下操作
首先按尺寸排序,建尺寸索引
则尺寸为0的和为180的可删除了

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

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

所有操作都先在尺寸索引里进行,仅是个标记操作
然后统一删除

shshsh_0510 发表于 2008-4-17 09:14:00

呵呵,要那么多数学原理干啥,不知道曲高和寡么.

shshsh_0510 发表于 2008-4-17 09:19:07

就这样?太慢了吧

无心人 发表于 2008-4-17 09:20:34

:)

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

无心人 发表于 2008-4-17 09:22:18

:)

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

用SSE2汇编

mathe 发表于 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秒钟之内完成

shshsh_0510 发表于 2008-4-17 09:29:38

不要吧,什么都上汇编?
先分析主要问题,都解决完了再用汇编那种东西在小数点后趋近极限。
您老的方法O(n)是O(n),干什么还要“除了最后求互补的”?
并且O(n)还分O(1n),O(2n)呢,离汇编远着呢:lol

mathe 发表于 2008-4-17 09:31:01

原帖由 无心人 于 2008-4-17 09:20 发表 http://images.5d6d.net/dz60/common/back.gif
:)

除了最后求互补的
都是O(N)算法啊
排序不是O(N)的,是O(Nlog(N)).
当然用Hash表理论上可以达到O(N),但是实际应用上,我觉得不会比用快速排序快
页: [1] 2 3
查看完整版本: 我觉得这个倒是可以比一比