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

shshsh_0510

http://topic.csdn.net/u/20080415 ... d-821f2e5ff775.html

无心人

把内容转过来，不过这个利用的数学原理少 ==================================================== 我用了个最最笨的压缩方法，在P4,3.0G,512M内存的机器上运行了一天，没有出结果，然后跟踪估计了下时间，大约需要9天时间才能完成数据压缩，太慢了！不知道各位有没有好的压缩方法？ 本人有近30万个vector （每个vector 中的值为0~179），如： vector > 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 ,表示从0到179间的数均在该vector中 .... a[310000]=... 先要对上述31万个vector 进行压缩，压缩原则为 1.空vector 删除，如a[1] 2.“满”vector 删除，如a[4] 3.相同vector 删除其中一个，如a[0]和a[3]相同，则删除其中任意一个 4.互补vector 删除其中一个，互补的意思是两vector 不相交且其并集为“满”vector

无心人

这个题目可如下操作 首先按尺寸排序，建尺寸索引 则尺寸为0的和为180的可删除了 然后对相同尺寸的，做一次遍历 删除完全相同的 互补的可按尺寸索引形成两个候选子序列 转换为小规模问题寻找 所有操作都先在尺寸索引里进行，仅是个标记操作 然后统一删除

shshsh_0510

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

shshsh_0510

就这样？太慢了吧

无心人

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

无心人

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

mathe

这个题目并不复杂，当然发这个人的问题犯了很多严重的错误，导致速度非常慢。 i)数据存储问题，显然里面的vector应该用比特数组来表示，无论是直接用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

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

mathe

原帖由 无心人 于 2008-4-17 09:20 发表 除了最后求互补的 都是O(N)算法啊

排序不是O(N)的，是O(Nlog(N)). 当然用Hash表理论上可以达到O(N),但是实际应用上，我觉得不会比用快速排序快