无心人
发表于 2008-4-17 09:40:04
:)
习惯了
写汇编比写C简单啊
求补的看规模了
规模小直接比较
规模大么?
再设几个标志吧
共设如下几个标志
数据长度, 源bit数组,源bit数组的CRC32,互补bit数组,互补bit数组CRC32
哈
分别以长度,两个CRC32校验排序
再进行比较,如果CRC32相等,比较原始bit数据
无心人
发表于 2008-4-17 09:41:39
:)
回复10#
如果数据是整数
存在比快速快的算法啊
shshsh_0510
发表于 2008-4-17 09:46:40
排序不是O(N)的,是O(Nlog(N)).
当然用Hash表理论上可以达到O(N),但是实际应用上,我觉得不会比用快速排序快
hash快不快,恐怕需要一些分析:
假设那30万项在1 - 2^180空间内等概率分布,我觉得更本不需要建立一个180位的bitmap索引就可以使冲突率很低
比如两项同时有n个元素,并且最大的m元素相等的概率是多少?找到一个这样的函数,使其概率<1/300000,那就和算了
shshsh_0510
发表于 2008-4-17 09:50:21
CRC32?那岂不是比直接建立180位的bitmap还要慢很多?
无心人
发表于 2008-4-17 09:52:47
SSE4一个指令搞定
mathe
发表于 2008-4-17 10:08:48
原帖由 无心人 于 2008-4-17 09:41 发表 http://images.5d6d.net/dz60/common/back.gif
:)
回复10#
如果数据是整数
存在比快速快的算法啊
这个结论从哪里来?
我不觉得有比快排快的算法,除非数据分布很特殊,比如数据完全均匀分布,其实那就是用hash的基础。
不过在数据总量不是很大的情况下,需要注意的是O(n*log(n))中,log(n)是个很小的数值,比如n=300000,log(n)才18(2为底)
而hash算法需要用到更加复杂的数据结构(内存开销更加大),通常不合算呀
无心人
发表于 2008-4-17 10:14:01
分组排序啊
mathe
发表于 2008-4-17 10:18:37
原帖由 无心人 于 2008-4-17 10:14 发表 http://images.5d6d.net/dz60/common/back.gif
分组排序啊
你是说基数排序吧,这个不会比快排快,除非数据分布很特殊。基数排序同样用于特殊数据分布。比如我们手工给扑克牌排序,经常用基数排序思想,先按花色分开,然后每个花色各自排序。
无心人
发表于 2008-4-17 10:22:42
基数排序是分组排序的一种啊
分组排序很多种呢
具体见TAOCP
shshsh_0510
发表于 2008-4-17 11:06:29
排序有啥好争,都nlgn了,快慢能有多少?因为以前研究过一阵最小比较排序问题,所以现在只记得个merge insert排序,在应用中,窃以为用类库就ok了。在条件不允许的情况下,如果能正确区分什么时候快排、什么时候冒泡就行了。其他趁早忘记,以免占用脑空间。
对于本问题,排序方法肯定是慢的:本题最主要的是遍历并建立索引或hash,其中遍历很耗资源,最好在一次循环完成。而排序法做不到。并且 log(n)=18虽是不大,但我想这个问题比的就是几倍的速度(就象他们那些汇编题目比的就是百分之几),所以这个如果都忽略了,那就都差不多了。