LeetCode 1242. 多线程网页爬虫

Categories:

题目描述
思路分析
1. 解法一：并发 BFS（推荐）
相似题目

题目描述

✅ 1242. 多线程网页爬虫

思路分析

解法一：并发 BFS（推荐）

核心思路：

提取起始 URL 的主机名，只抓取相同主机名的链接。

使用线程安全集合去重，发现新 URL 后再提交任务并行抓取。

以并发 BFS 的方式扩展网页集合，直到没有新链接。

复杂度分析：

时间复杂度：O(n + e)，其中 n 为可访问页面数，e 为链接数。

空间复杂度：O(n)，存储访问集合与任务队列。

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

class Solution {
    public List<String> crawl(String startUrl, HtmlParser htmlParser) {
        String host = getHost(startUrl);
        Set<String> visited = ConcurrentHashMap.newKeySet();
        visited.add(startUrl);

        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new CrawlTask(startUrl, host, htmlParser, visited));

        return new ArrayList<>(visited);
    }

    private static class CrawlTask extends RecursiveAction {
        private final String url;
        private final String host;
        private final HtmlParser parser;
        private final Set<String> visited;

        CrawlTask(String url, String host, HtmlParser parser, Set<String> visited) {
            this.url = url;
            this.host = host;
            this.parser = parser;
            this.visited = visited;
        }

        @Override
        protected void compute() {
            List<CrawlTask> tasks = new ArrayList<>();
            for (String next : parser.getUrls(url)) {
                if (!host.equals(getHost(next))) {
                    continue;
                }
                if (visited.add(next)) {
                    tasks.add(new CrawlTask(next, host, parser, visited));
                }
            }
            invokeAll(tasks);
        }
    }

    private static String getHost(String url) {
        int idx = url.indexOf("://");
        int start = idx >= 0 ? idx + 3 : 0;
        int slash = url.indexOf('/', start);
        if (slash == -1) {
            return url.substring(start);
        }
        return url.substring(start, slash);
    }
}

import (
    "strings"
    "sync"
)

func crawl(startUrl string, htmlParser HtmlParser) []string {
    host := getHost(startUrl)

    visited := make(map[string]struct{})
    var mu sync.Mutex

    queue := make(chan string, 128)
    var wg sync.WaitGroup
    var workerWg sync.WaitGroup

    addURL := func(u string) {
        mu.Lock()
        if _, ok := visited[u]; ok {
            mu.Unlock()
            return
        }
        visited[u] = struct{}{}
        mu.Unlock()

        wg.Add(1)
        queue <- u
    }

    addURL(startUrl)

    worker := func() {
        defer workerWg.Done()
        for u := range queue {
            for _, next := range htmlParser.GetUrls(u) {
                if getHost(next) != host {
                    continue
                }
                addURL(next)
            }
            wg.Done()
        }
    }

    for i := 0; i < 8; i++ {
        workerWg.Add(1)
        go worker()
    }

    wg.Wait()
    close(queue)
    workerWg.Wait()

    res := make([]string, 0)
    for u := range visited {
        res = append(res, u)
    }
    return res
}

func getHost(url string) string {
    start := 0
    if idx := strings.Index(url, "://"); idx >= 0 {
        start = idx + 3
    }
    if slash := strings.Index(url[start:], "/"); slash >= 0 {
        return url[start : start+slash]
    }
    return url[start:]
}

相似题目

题目	难度	考察点
1236. 网络爬虫	中等	BFS
200. 岛屿数量	中等	BFS/DFS
733. 图像渲染	简单	BFS/DFS
417. 太平洋大西洋水流问题	中等	图遍历
847. 访问所有节点的最短路径	困难	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/80513569