algorithm - 需要想法使用优先级队列在数据结构中自定义算法

Question

我正在使用优先级队列开发网络抓取算法。我有一个种子 URL，我根据算法解析了它的所有链接。然后我根据他们从算法中获得的分数将所有解析的 URL 放入优先级队列中。该算法开始根据链接分数从优先队列中选择新的种子 URL。当一个链接被选为种子 URL 时，它会从优先队列中出队，依此类推。程序运行没有任何问题。但问题是:

• 由于 enqueue Links 操作数越来越多于 dequeue Links 操作数，Priority Queue 的大小也越来越大。我怎样才能控制它？优先队列的大小是否会影响我的爬虫的性能？

• 当我尝试获取每分钟抓取的 URL 数量时，我得到的结果很低。例如:运行该程序 1 小时后，爬网页面的平均值比我运行该程序 15 分钟并获得爬网页面的平均值要低。发生这种情况是因为 Priority Queue size 吗？如何解决这个问题？

我有这两个问题，需要你的帮助和你的想法来解决我的抓取算法中的这个问题。

Answer 1

正如 rafalio 指出的那样，您的队列大小会不断增加，因为平均网页包含超过 1 个出站链接，并且您不会在整个互联网上达到关闭 :-)

但是，与其像 rafalio 建议的那样搜索每个页面的前 N ​​个链接，不如建议您为优先级队列设置一个全局最大上限(例如 30,000)。这样，当它开始增长时，您遍历的每个新链接(队列中下一个优先级最高的链接)将积累越来越多的相对于迄今为止遇到的其他所有链接的优先级。您几乎可以肯定，当队列达到上限时，其中优先级最高的项目将比当前页面(或您接下来可能访问的任何任意页面)上的前 N ​​个链接更重要。

请记住，如果您的优先级队列是支持数组的，则插入和删除操作将为 O(n)。排序的链表也将有 O(n) 插入时间。二进制堆支持的优先级队列应该为大 n 提供最佳的整体性能，在插入和删除时不低于 O(log n) 和 O(1) 最小/最大项目查找。