有效地搜索大量URL列表
我正在建立一个网络爬虫，它必须爬行数百个网站。我的爬虫保存了一个已经爬行的urls列表。每当爬虫要爬行一个新页面时，它首先搜索已经爬行的url列表，如果已经列出了，则爬虫跳到下一个url，以此类推。一旦url被爬行，它就会被添加到列表中。
目前，我正在使用二进制搜索来搜索url列表，但是问题是，一旦列表变大，搜索就会变得非常慢。因此，我的问题是，我可以使用什么样的算法来搜索一个urls列表(列表的大小每天增长到20到100 k)。
爬虫目前是用Python编写的。但我将把它移植到C++或其他更好的语言中。
回答 2
Stack Overflow用户
发布于 2016-06-23 17:30:36
你必须在某个时候决定你想让你的爬行列表变得多大。最多数以千万计的项目，您可能只需将URL存储在哈希映射或字典中，这将为您提供O(1)查找。
无论如何，平均URL长度约为80个字符(这是五年前我运行分布式爬虫时的经验)，每千兆字节只能获得大约1000万个URL。所以你必须开始考虑压缩数据或者在一段时间后允许重新爬行。如果你每天只添加10万个URL，那么你需要100天才能爬上1000万个URL。可能有足够的时间再爬一次。
如果这些是您的限制，那么我会建议一个简单的字典或哈希映射，它是由URL键决定的。该值应包含最后一次爬行日期和任何其他您认为相关的信息。将该数据结构限制为1000万URL。它可能会消耗近2GB的空间，这与字典的开销类似。
你必须定期修剪它。我的建议是有一个计时器，每天运行一次，清除超过X天前爬行的任何URL。在这种情况下，您可能会将X设置为100。这意味着每天有100,000个URL。
如果你开始谈论高容量的爬虫，每天要做数百万的URL，那么你就进入了更复杂的数据结构和创造性的方法来管理复杂性。但从你问题的语气来看，这不是你感兴趣的。
Stack Overflow用户
发布于 2016-06-23 17:33:48
我认为在将值放入二进制搜索列表之前先对它们进行散列--这将消除字符串比较的可能瓶颈，将其转换为int等式检查。它还保留了O(log2(n))二进制搜索时间--如果在运行期间使用python的内置hash()，则可能不会得到一致的结果--但是，它是特定于实现的。在运行过程中，它将是一致的。始终有实现您自己的散列的选项，这在会话之间也是一致的。
https://stackoverflow.com/questions/37998013
复制相似问题
腾讯云开发者
