LeetCode 1236/1242 设计一个(多线程)爬虫解法
2023-06-13 09:15:31 时间
LeetCode 最近除了算法题之外还增加了几道稍微实战一点的题目和并发题目。这两道题大概就是做一个简单的网页爬虫,然后已经给定了 htmlParser.getUrls 方法可以获取对应页面的链接。
单线程题目 LeetCode-1236
具体题目就不说了,直接去 LeetCode 上看就好了。1236 要求使用单线程即可,考察的主要是图的遍历。只要注意到对于新发现的节点需要考虑是否已经访问过就好了。在实际生产中,肯定也是要用广度优先,深度优先基本就会陷进一个网站出不来了。
from urllib.parse import urlsplit
class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
domain = urlsplit(startUrl).netloc
q = [startUrl]
visited = set([startUrl])
while q:
newUrls = []
for url in q:
urls = htmlParser.getUrls(url)
for newUrl in urls:
u = urlsplit(newUrl)
if u.netloc != domain:
continue
if newUrl in visited:
continue
visited.add(newUrl)
newUrls.append(newUrl)
q = newUrls
return list(visited)
多线程题目 LeetCode-1242
1242 题要求使用多线程来实现。在现实生活中,爬虫作为一个 IO 密集型的任务,使用多线程是一项必须的优化。
在上述的单线程版本中,我们使用了 visited 这个数组来存放已经访问过的节点,如果我们采用多线程的话,并且在每个线程中并发判断某个 URL 是否被访问过,那么势必需要给这个变量加一个锁。而我们知道,在多线程程序中,加锁往往造成性能损失最大,最容易引起潜在的 bug。那么有没有一种办法可以不用显式加锁呢?
其实也很简单,我们只要把需要把并发访问的部分放到一个线程里就好了。这个想法是最近阅读 The Go Programming Language 得到的启发。全部代码如下:
import threading
import queue
from urllib.parse import urlsplit
class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
domain = urlsplit(startUrl).netloc
requestQueue = queue.Queue()
resultQueue = queue.Queue()
requestQueue.put(startUrl)
for _ in range(5):
t = threading.Thread(target=self._crawl,
args=(domain, htmlParser, requestQueue, resultQueue))
t.daemon = True
t.start()
running = 1
visited = set([startUrl])
while running > 0:
urls = resultQueue.get()
for url in urls:
if url in visited:
continue
visited.add(url)
requestQueue.put(url)
running += 1
running -= 1
return list(visited)
def _crawl(self, domain, htmlParser, requestQueue, resultQueue):
while True:
url = requestQueue.get()
urls = htmlParser.getUrls(url)
newUrls = []
for url in urls:
u = urlsplit(url)
if u.netloc == domain:
newUrls.append(url)
resultQueue.put(newUrls)
在上面的代码中,我们开启了 5 个线程并发请求,每个 worker 线程都做同样的事情:
- 从 requestQueue 中读取一个待访问的 url;
- 执行一个很耗时的网络请求:
htmlParser.getUrls
; - 然后把获取到的新的 url 处理后放到 resultQueue 中。
而在主线程中:
- 从 resultQueue 中读取一个访问的结果
- 判断每个 URL 是否已经被访问过
- 并分发到 requestQueue 中。
我们可以看到在上述的过程中并没有显式使用锁(当然 queue 本身是带锁的)。原因就在于,我们把对于需要并发访问的结构限制在了一个线程中。
相关文章
- 有效的括号(leetcode 20)
- Leetcode 差分数组的应用「建议收藏」
- LeetCode周赛298,阳光普照,参加就能简历免筛
- LeetCode周赛286场,高质量题目,不容错过
- LeetCode 刷题笔记——day 1
- LeetCode 905. 按奇偶排序数组
- LeetCode笔记:Biweekly Contest 89
- leetcode刷题(122)——62. 不同路径
- 【day03】LeetCode(力扣)每日一刷[239. 滑动窗口最大值 ][1422. 分割字符串的最大得分][1046. 最后一块石头的重量 ]
- 【day09】LeetCode(力扣)每日一刷[1640. 能否连接形成数组 ][102. 二叉树的层序遍历 ][704. 二分查找 ]
- LeetCode - #73 矩阵置零
- 前端工程师leetcode算法面试必备-二叉树深度广度遍历1
- JavaScript刷LeetCode拿offer-二叉树层序遍历篇5
- Leetcode LRU 缓存机制