Problem 621660 · medium · Level 06 Heuristics & Optimization

A Crawler That Keeps Only a Few Downloads Running

py-async · coroutines · worker pool · concurrency limit · deduplication

A crawler copies pages from a small website. Downloading them one at a time is slow, but starting every download at once would overload the site, which asks for at most limit downloads at the same time.

Write a coroutine function crawl(urls, limit) that returns a list with, for each URL in urls, the size returned by await download(url), or None if that download raised TimeoutError. The same URL may appear several times in urls; download it only once and use its result for every occurrence.

Downloads must be scheduled like this: start them in the order of the list (a repeated URL takes no new download); never have more than limit in progress; and whenever a download finishes while URLs are still waiting, the next one starts at that same tick. So the crawl is as fast as limit parallel lanes allow.

As in the other coroutine problems on this site, the tests run your coroutines on a loop with a virtual clock. The setup gives you download(url), gather(*coroutines), spawn(coroutine), pause(ticks) and now(), which work like their asyncio counterparts. mirror(crawl, pages, urls, limit) sets up a site from a list of (url, delay, size) pages and returns (your result, the finishing tick, the most downloads that ran at once, the start tick of every download in the order they started, the number of downloads). site(n, seed) and visits(pages, k, seed) generate a site and a list of requests.

Examples

Input:  mirror(crawl, [("/a", 4, 100), ("/b", 2, 200), ("/c", 3, None), ("/d", 1, 400)], ["/a", "/b", "/c", "/b", "/d"], 2)
Output: ([100, 200, None, 200, 400], 5, 2, [0, 0, 2, 4], 4)
Explanation: /a and /b start at 0; /b ends at 2 and /c starts; /a ends at 4 and /d starts; /c fails at 5 and /d ends at 5.

Input:  mirror(crawl, [("/x", 3, 9)], [], 4)
Output: ([], 0, 0, [], 0)

Constraints

  • 1 <= limit <= 50; up to 3,000 requested URLs and 1,000 pages.
  • Do not call asyncio.run or asyncio.sleep, and do not wait by looping over pause(0).

Goals

  • Run many waits concurrently while never having more than a fixed number in progress
  • Build a pool of worker coroutines that share one iterator of jobs
  • Collect results from concurrent workers into the order of the input
Starting Python…