求算法。

神思

假设集合A和B各中有1亿个不重复url请找出A中有但B中没有的元素。

元素无序，不得用数据库。

Cola酱

纯酱油 路过
字符串HASH然后存数组排序什么的
但那个1亿也太.......

神思

其实一开始我也是想着A建立hash表，然后遍历B…求更优算法…

紫苏

Ruby 数组的差集就是散列 A 元素，遍历 B 实现的：
http://ruby-doc.org/doxygen/1.8.4/array_8c-source.html#l02638
也可以再去看看 STL 的 vector set_difference 是怎么实现的，不过估计差不多

理论上，用 Trie 结构进行搜索比散列表更高效，特别是在元素是字符串的时候。如果元素不是字符串，优势也可以找到一种以节点作为有限自动机的状态，用来唯一标识元素的表式法，比如十进制的整数可以分别把每一数位作为一个状态。一亿个元素的散列表，需要重新计算散列码的频率必然不低，而 Trie 则不需要再散列，在最坏场合下的性能就比散列表高了。在空间性能上，散列表是消耗巨大的，因为它需要一个散列索引表；而 Trie 不需要元素数据之外的额外空间，一切运算均是原地进行
http://zh.wikipedia.org/zh/Trie

orochi2k

不得用数据库的话自己写个数据库捏……

雷欧纳德

大多数要求快速查找的散列都需要在存入数据时期就进行完排列，比如可以用红黑树。。。
像脉子说的，STL的哈希结构大部分都是使用的红黑树变种

Cola酱

回复 神思 的帖子
其实HASH也不是不能做
把AB都HASH
   时间复杂度O(NK) K是HASH的复杂度 不同算法不同
  空间复杂度O(N)
然后分别排序 可以用QuickSort+随机化 或者是归并排序
  时间复杂度O(NLog2N)
   空间复杂度O(N)
接着是顺序枚举A 然后二分查找B
   时间复杂度O(NLog2N)
   没有用到额外的空间
所以 整个算法
  时间复杂度O(NK) 一般情况是的 因为NLog2N与NK完全不是一个数量级
  空间复杂度O(N) 好歹储存都要这个空间吧
  这样就能解决HASH消耗的问题
  不过中间O(1)的查找就变成了O(Log2N)的查找+O(NLog2N)的预处理
  勉强过得去吧


不过还是Trie强大
  时间复杂度O(NT) T是字符串平均长度
  空间复杂度小于O(N) 因为字符串被压缩了

貌似HASH要强过Trie就只有优化HASH函数了吧= =

紫苏

回复
其实HASH也不是不能做
把AB都HASH
   时间复杂度O(NK) K是HASH的复杂度 不同算法不同
  空间复杂度O( ...
Cola酱 发表于 2010-10-1 18:38

用排序就不要用散列表了，散列表也无法排序。如果两个集合的结构都能进行排序，排序完后按顺序比较相邻的元素， O(min(m,n)) 就能找出差集了，m,n=集合 A、B 的长度，不需要搜索。问题在于排序时键的比较，如果是字串类型的键，那比较的经费也是很高的
如果有完美的散列函数，那自然是散列表的效率高，但在实践时这几乎是不可能的

Cola酱

回复 紫苏 的帖子
我不是说散列表
而是以哈希函数值为关键字排序
散列表实质就是 哈希函数+桶排序
我是说把对数据范围有限制的桶排序
改成QuickSort
这样就可以剩下很多空间

我记得HASH是指散列算法
但MS这里默认成为了散列表
所以看到3L就很疑惑地解释
看到紫苏的就更确定这一点

这样的话应该都明白了
   

紫苏

回复 Cola酱 的帖子

原来如此，我理解错了。不过这么做也得考虑哈希碰撞的问题，除非有一个完美散列函数。
另外，散列表哪里有桶排序？桶排序是分布式排序，其思想是分布数据到各个桶，排序，最后串联，而散列表无论是用分离链接法还是开放地址法解决碰撞，一个表都只有一个桶，唯一和顺序有关的就是分离链接法里每一个桶的空位可以内部维护为有序列表（或者搜索树结构），减少搜索时间