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

无心人

习惯了
写汇编比写C简单啊

求补的看规模了
规模小直接比较

规模大么？
再设几个标志吧
共设如下几个标志
数据长度， 源bit数组，源bit数组的CRC32，互补bit数组，互补bit数组CRC32
哈
分别以长度，两个CRC32校验排序
再进行比较，如果CRC32相等，比较原始bit数据

无心人

回复10#
如果数据是整数
存在比快速快的算法啊

shshsh_0510

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

hash快不快，恐怕需要一些分析：
假设那30万项在1 - 2^180空间内等概率分布，我觉得更本不需要建立一个180位的bitmap索引就可以使冲突率很低
比如两项同时有n个元素，并且最大的m元素相等的概率是多少？找到一个这样的函数，使其概率<1/300000,那就和算了

shshsh_0510

CRC32?那岂不是比直接建立180位的bitmap还要慢很多？

无心人

SSE4一个指令搞定

mathe

原帖由 无心人 于 2008-4-17 09:41 发表


回复10#
如果数据是整数
存在比快速快的算法啊

这个结论从哪里来？
我不觉得有比快排快的算法，除非数据分布很特殊，比如数据完全均匀分布，其实那就是用hash的基础。
不过在数据总量不是很大的情况下，需要注意的是O(n*log(n))中,log(n)是个很小的数值，比如n=300000,log(n)才18(2为底)
而hash算法需要用到更加复杂的数据结构（内存开销更加大），通常不合算呀

无心人

分组排序啊

mathe

原帖由 无心人 于 2008-4-17 10:14 发表
分组排序啊

你是说基数排序吧，这个不会比快排快，除非数据分布很特殊。基数排序同样用于特殊数据分布。比如我们手工给扑克牌排序，经常用基数排序思想，先按花色分开，然后每个花色各自排序。

无心人

基数排序是分组排序的一种啊
分组排序很多种呢

具体见TAOCP

shshsh_0510

排序有啥好争，都nlgn了，快慢能有多少？因为以前研究过一阵最小比较排序问题，所以现在只记得个merge insert排序，在应用中，窃以为用类库就ok了。在条件不允许的情况下，如果能正确区分什么时候快排、什么时候冒泡就行了。其他趁早忘记，以免占用脑空间。

对于本问题，排序方法肯定是慢的：本题最主要的是遍历并建立索引或hash，其中遍历很耗资源，最好在一次循环完成。而排序法做不到。并且 log(n)=18虽是不大，但我想这个问题比的就是几倍的速度（就象他们那些汇编题目比的就是百分之几），所以这个如果都忽略了，那就都差不多了。