如何仅在集合 A 中而不是在集合 B 中查找不同的 URL
有两组URL，均包含数百万个URL。现在，我如何从 A 获取 B 中没有的 URL。最好的方法是什么？
注意：您可以使用任何技术，使用任何工具，例如数据库、mapreduce、hashcode 等。我们应该考虑内存效率、时间效率。您必须考虑到每个集合（A 和 B）都有数百万个 URL。我们应该尝试使用更少的内存和更少的时间来找到特定的 URL。
There are two sets of URL, both contains millions of URLs. Now, How can I get an URL from A that is not in B. What's The best methods?
Note: you can use any technique, use any tools like database, mapreduce, hashcode, etc, . We should consider the memory efficient, time efficient. You have to consider that every set (A and B) have millions of URL. We should try to find the specific URLs using less memory and less time.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
一个不错的算法可能是：
将集合 A 的所有内容加载到哈希图中，O(a)
遍历集合 B，并且对于每个项目，从集合 A（从哈希映射）中删除相同的值（如果存在），O(b)
然后你的hashmap 有结果。这将是 O(a+b)，其中 a 是集合 A 的大小，b 是集合 B 的大小。（实际上，这将乘以哈希时间，理想情况下，对于良好的哈希来说，这大约相当于 O(1) .)
A decent algorithm might be:
load all of set A into a hashmap, O(a)
traverse set B, and for each item, delete the identical value from set A (from the hashmap) if it exists, O(b)
Then your hashmap has the result. This would be O(a+b) where a is size of set A and b is size of set B. (In practice, this would be multiplied by the hash time, which ideally corresponds to approximately O(1) for a good hash.)
可能有点幼稚的过程可能是像对
将列表 A 和 B 一起导航这样的过程：
a.当元素匹配时增加指向 A 的指针并增加指向 B 的指针
b.递增指向 B 的指针，直到该元素与
a中的下一个元素匹配，或者直到B中的记录b出现在a中的下一个元素之后>a（此规则丢弃 B 中不在 A 中的元素）c.根据这些规则递增时发现匹配，使得
B中的下一个元素b与B中的下一个元素a不匹配>A.这实际上可能是一个应用布隆过滤器的有趣地方：为集合 B 构造一个布隆过滤器，然后为集合 A 中的每个 URL 都确定它是否在集合 B 中。随着错误概率逐渐减小，您应该能够找到 A 中而不是 B 中的所有 URL。
Something perhaps a little naive might be a procedure like
Navigate list A and B together such that:
a. Increment pointer to A and pointer to B when elements match
b. Increment pointer to B until the element matches the next element in
aor until the recordbinBwould appear after the next element ina(this rule discards elements in B that are not in A)c. A match has been found when incrementing subject to these rules such that the next element
binBdoes not match the next elementainA.This might actually be an interesting place to apply Bloom filters: construct a Bloom filter for set B then for every URL in set A determine if it is in set B. With diminishingly small probability of error you should be able to find all URLs in A not in B.