我觉得这个倒是可以比一比
http://topic.csdn.net/u/20080415/10/a676aaa4-766e-4429-a86d-821f2e5ff775.html 把内容转过来，不过这个利用的数学原理少====================================================
我用了个最最笨的压缩方法，在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> 这个题目可如下操作
首先按尺寸排序，建尺寸索引
则尺寸为0的和为180的可删除了
然后对相同尺寸的，做一次遍历
删除完全相同的
互补的可按尺寸索引形成两个候选子序列
转换为小规模问题寻找
所有操作都先在尺寸索引里进行，仅是个标记操作
然后统一删除 呵呵,要那么多数学原理干啥,不知道曲高和寡么. 就这样？太慢了吧 :)
除了最后求互补的
都是O(N)算法啊 :)
那帖子都说了
用位操作
很快的
用SSE2汇编 这个题目并不复杂，当然发这个人的问题犯了很多严重的错误，导致速度非常慢。
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秒钟之内完成 不要吧，什么都上汇编？
先分析主要问题，都解决完了再用汇编那种东西在小数点后趋近极限。
您老的方法O(n)是O(n),干什么还要“除了最后求互补的”？
并且O(n)还分O(1n),O(2n)呢，离汇编远着呢:lol 原帖由 无心人 于 2008-4-17 09:20 发表 http://images.5d6d.net/dz60/common/back.gif
:)
除了最后求互补的
都是O(N)算法啊
排序不是O(N)的，是O(Nlog(N)).
当然用Hash表理论上可以达到O(N),但是实际应用上，我觉得不会比用快速排序快