logo标签列表

高效替代方案"in"

pythonlistoptimizationmemory
4
我正在编写一个网络爬虫，最终目标是创建一个显示爬虫路径的地图。虽然我不知道其他更好的爬虫每分钟能够下载多少页面，但我的爬虫速度约为每分钟2,000页。
该爬虫使用递归回溯算法，我将其限制在15层深度。此外，为了防止爬虫无休止地重复访问页面，它会将已访问页面的URL存储在列表中，并检查该列表以获取下一个候选URL。
for href in tempUrl:
    ...
    if href not in urls:
         collect(href,parent,depth+1)

当爬取了大约30万页时，这种方法似乎会变成一个问题。此时平均每分钟爬虫的页面数量为500个。

我的问题是，有没有另一种方法可以实现相同的功能并提高效率。

我曾经想过减小每个条目的大小可能会有所帮助，因此，我附加了每个URL的前2个和最后2个字符作为字符串，而不是整个URL。然而，这并没有起到作用。

是否有一种方法可以使用集合或其他方法来完成这个任务？

感谢您的帮助。

编辑：顺便说一下，我的程序尚未多线程化。我想在学习线程之前解决这个瓶颈问题。

4个回答
15

也许你可以使用一个set来代替一个list，用于存储目前为止已经看到的URL。

+1 是一个值得尝试的东西，如果我没记错的话，在集合中检查存在应该是 O(1)，我已经看到了从列表切换到集合后检查现有速度的惊人加速。 - Davy8
2
@Pete，是的 - 在集合和字典中测试成员资格的时间复杂度为O(1)，在列表和元组中，时间复杂度为O(n)，其中n为列表/元组的长度。因此，对于长列表/元组，这将产生巨大的差异。（顺便加一分。） - senderle
@Pete 试一下，如果顺序不重要，集合是非常优化的。 - Davy8
@Pete等人，参见此答案的编辑，以获取此加速的引人注目示例。 - senderle
1
顺便说一下@Pete，如果你不知道，O(1)表示它花费的时间相同，无论集合大小如何，而对于列表，O(n)表示如果列表大10倍，则检查存在性最多可能需要花费10倍的时间（如果在列表末尾的情况下，是最坏情况）。 - Davy8
显示剩余2条评论
7
只需将您的“已爬取URL列表”替换为“已爬取URL集合”。 集合使用优化的哈希算法进行随机访问（使用与字典相同的哈希算法），速度要快得多。 列表的查找操作使用线性搜索，因此速度不是特别快。 您无需更改执行查找的实际代码。
看看这个。
In [3]: timeit.timeit("500 in t", "t = list(range(1000))")
Out[3]: 10.020853042602539

In [4]: timeit.timeit("500 in t", "t = set(range(1000))")
Out[4]: 0.1159818172454834
3
2
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接