Project1

标题: 求算法。 [打印本页]

作者: 神思 时间: 2010-10-1 11:01
标题: 求算法。
假设集合A和B各中有1亿个不重复url请找出A中有但B中没有的元素。

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

作者: Cola酱 时间: 2010-10-1 11:13
纯酱油路过
字符串HASH然后存数组排序什么的
但那个1亿也太.......

作者: 神思 时间: 2010-10-1 11:20
其实一开始我也是想着A建立hash表，然后遍历B…求更优算法…

作者: 紫苏 时间: 2010-10-1 12:00
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 时间: 2010-10-1 12:24

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

作者: 雷欧纳德 时间: 2010-10-1 12:44
大多数要求快速查找的散列都需要在存入数据时期就进行完排列，比如可以用红黑树。。。
像脉子说的，STL的哈希结构大部分都是使用的红黑树变种

作者: Cola酱 时间: 2010-10-1 18:38
回复神思的帖子
其实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函数了吧= =

作者: 紫苏 时间: 2010-10-1 20:58

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

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

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

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

这样的话应该都明白了

作者: 紫苏 时间: 2010-10-2 10:07
回复 Cola酱 的帖子

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

作者: rmg_mage 时间: 2010-10-2 10:36
题外话：你们为什么不去向NOI提出加入RUBY编程计划？

作者: Cola酱 时间: 2010-10-2 18:26
回复紫苏的帖子
关于桶排：
桶排序要把同一个桶里面的东西链在一起
比如说在"1"桶里面是1：1.1->1.4->1.7
不过如果数字都是整数的话
那么就变成了1: 1->1->1
这样就是HASH表的原形
但是因为Hash(X)=Hash(Y)不可推出X=Y
所以才要有解决冲突
这就是完整的HASH表
至少我就是这么认为的

关于哈希碰撞：
首先Hash(X)=Hash(Y)不可推出X=Y
但是Hash(X)!=Hash(Y)可推出X!=Y
所以对于字符串数组A的所有哈希值
只要通过二分查找找到对应哈希值在B中的起始位置
就可以判定有没有同样字符串在B中出现
大概就是这样

不知道紫苏你是学什么语言的呢
我是PASCAL的略懂一点C

作者: 紫苏 时间: 2010-10-3 02:37
本帖最后由紫苏于 2010-10-3 02:42 编辑

回复 Cola酱 的帖子

桶排序使用的桶都是长度固定的数组吧，至少我还没见过用链表实现桶的。散列表有一个装载因子，就是元素个数/桶数组大小的比率，这里也是使用的固定大小的一个桶，因为只有顺序结构才能用 O(1) 时间访问。我觉得你说的是每个桶的空位，如果使用分离链接法，那这些空位确实是要指向一个链式结果，所有碰撞了的键的值都被链在这里。如果这里用二叉搜索树，就同时保证了节点顺序，散列表就可以在 O(log n) 内完成查找，但这并非桶排序。

首先Hash(X)=Hash(Y)不可推出X=Y
但是Hash(X)!=Hash(Y)可推出X!=Y
所以对于字符串数组A的所有哈希值
只要通过二分查找找到对应哈希值在B中的起始位置
就可以判定有没有同样字符串在B中出现

嗯，那要带着键和值一起排序，才能在冲突的时候判断是否值相等。不过当你排好两个数组 C、D 的顺序后，做一个从左到右判断就够了——假设 i 是循环变量，我们要进行 C - D 这个有方向差集运算，因为已经排好序，所以可以在迭代时判断 D[ｉ] 是否在 C[ｉ] 和 C[i+1] 之间（不含临界点），如果是，则说明 D[ｉ] 这个元素不在 C 中，以此类推，所以才有前面提到的 O(min(m,n))。冲突的情况，也是只能通过相邻键相同的值挨个比较，毕竟值没有顺序。

不知道紫苏你是学什么语言的呢
我是PASCAL的略懂一点C

厉害，现在学 Pascal 的年轻人还真少见，我年轻的时候就完全没接触过 Pascal。我以前主要是搞 Java，后来注意力集中到了 C/C++。至于 Ruby，我从开始接触程序以后就一直在学，但到现在仍然是个半吊子，每天都需要灌输新的东西（这小妮子成长太快了！）。

作者: moy 时间: 2010-10-3 03:13
膜拜各位大神{:nm_3:}

作者: Cola酱 时间: 2010-10-3 10:29
本帖最后由 Cola酱于 2010-10-3 10:30 编辑

回复紫苏的帖子

对哦
排序后都有单调性的
而且A与B求交集就是B与A的交集诶
话说我因为最近做的题目二分答案的太多了
心里有阴影了= =
一看到题目就想二分= =

那这样我就完全明白了
谢谢紫苏哈

欢迎光临 Project1 (https://rpg.blue/)