|
精华帖 (0) :: 良好帖 (2) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-09-29
xiangkun 写道 放数据库,最快的!
要计算放到 数据库中成本，，如果能很方便整理成 sqlload ，或者 insert ，这些数据对于性能好点的的 oracle 来说，不算 什么，， 但 我看这道题的本意应该不是这个，，是考察数据结构的熟练程度，，， 但是实际的项目中，我肯定会用成本最低的和 最方便的，而不是搞一个牛逼无比的算法出来，，， |
| 返回顶楼 | |
|
发表时间：2010-09-29
最后修改：2010-09-29
按照4G内存的大小，是有320亿个Bit位的，因此可以考虑把A的URI用一个Hash函数映射到对应的Bit位，然后遍历B的URI，用同样的Hash函数得到hash值，然后判断该位上的值是否为1，如果为1，说明B中的URL也在A中出现过。 |
| 返回顶楼 | |
|
发表时间：2010-09-29
最后修改：2010-09-30
[quote="aws"]先把A的记录压入一个trie树 然后用B的记录来做命中 没有命中的URL就是不重复的 [/quote] Trie树的构建是相当耗时的。。。 而且Trie数的空间复杂度要高一些，因此这个题的最好的数据结构还是Bit-Map或者是BloomFilter。BitMap的空间消耗要别BloomFilter小3-8倍。 http://blog.redfox66.com/post/mass-data-4-bitmap.aspx http://blog.redfox66.com/post/mass-data-topic-2-bloom-filter.aspx |
| 返回顶楼 | |
|
发表时间：2010-09-29
有个想法，使用全文检索！只是建立索引的过程耗费时间，但是之后查找会很快！
|
| 返回顶楼 | |
|
发表时间：2010-09-29
ling凌yue月 写道 olylakers 写道 刚和一个朋友聊了下，觉得还有一个思路
把B的URL存成3层N叉树，然后依次遍历A中URL，将其到存放B的URL的3层N叉树种去查找，如果存在的话，最多三次就可以找到。 不明白为什么是3层？求解答 不一定是要3层的。。。 |
| 返回顶楼 | |
|
发表时间：2010-09-29
西门吹牛 写道 不是说可以是存在数据库中吗?如果是oracle我会这么做
select url from a minus select url from b 这个不错。 |
| 返回顶楼 | |
|
发表时间：2010-09-29
maincoolbo 写道 xiangkun 写道 放数据库,最快的!
要计算放到 数据库中成本，，如果能很方便整理成 sqlload ，或者 insert ，这些数据对于性能好点的的 oracle 来说，不算 什么，， 但 我看这道题的本意应该不是这个，，是考察数据结构的熟练程度，，， 但是实际的项目中，我肯定会用成本最低的和 最方便的，而不是搞一个牛逼无比的算法出来，，， 原来如此 |
| 返回顶楼 | |
|
发表时间：2010-09-29
可以考虑使用java中的map~~~
|
| 返回顶楼 | |
|
发表时间：2010-09-29
如何找出A中有而B中没有的URL。
标准sql: select A.* from A where not exists (select 1 from B where B.url = A.url) |
| 返回顶楼 | |
|
发表时间：2010-09-29
用数据库就悲剧了。
|
| 返回顶楼 | |
