Как я могу сделать эту рекурсивную функцию сканирования итеративной?

Question

Для академичности и производительности, учитывая эту рекурсивную функцию сканирования в Интернете (которая сканирует только в пределах данного домена), какой будет лучший подход, чтобы сделать его итеративным? В настоящее время, когда он работает, к моменту его завершения Python использует более 1 ГБ памяти, что неприемлемо для работы в общей среде.

   def crawl(self, url):
    "Get all URLS from which to scrape categories."
    try:
      links = BeautifulSoup(urllib2.urlopen(url)).findAll(Crawler._match_tag)
    except urllib2.HTTPError:
      return
    for link in links:
      for attr in link.attrs:
        if Crawler._match_attr(attr):
          if Crawler._is_category(attr):
            pass
          elif attr[1] not in self._crawled:
            self._crawled.append(attr[1])
            self.crawl(attr[1])

Answer 1

Используйте BFS вместо рекурсивного сканирования (DFS): http://en.wikipedia.org/wiki/Breadth_first_search

Вы можете использовать внешнее хранилище (например, базу данных) для очереди BFS, чтобы освободить ОЗУ.

Алгоритм:

//pseudocode:
var urlsToVisit = new Queue(); // Could be a queue (BFS) or stack(DFS). (probably with a database backing or something).
var visitedUrls = new Set(); // List of visited URLs.

// initialization:
urlsToVisit.Add( rootUrl );

while(urlsToVisit.Count > 0) {
  var nextUrl = urlsToVisit.FetchAndRemoveNextUrl();
  var page = FetchPage(nextUrl);
  ProcessPage(page);
  visitedUrls.Add(nextUrl);
  var links = ParseLinks(page);
  foreach (var link in links)
     if (!visitedUrls.Contains(link))
        urlsToVisit.Add(link); 
}

Answer 2

Вместо повторения вы можете поместить новые URL-адреса для сканирования в очередь. Затем запустить до тех пор, пока очередь не станет пустой без повторения. Если вы помещаете очередь в файл, это почти не использует память.

Answer 3

@ Mehrdad - Спасибо за ваш ответ, пример, который вы привели, был кратким и простым для понимания.

Решение:

  def crawl(self, url):
    urls = Queue(-1)
    _crawled = []

    urls.put(url)

    while not urls.empty():
      url = urls.get()
      try:
        links = BeautifulSoup(urllib2.urlopen(url)).findAll(Crawler._match_tag)
      except urllib2.HTTPError:
        continue
      for link in links:
        for attr in link.attrs:
          if Crawler._match_attr(attr):
            if Crawler._is_category(attr):
              continue
            else:
              Crawler._visit(attr[1])
              if attr[1] not in _crawled:
                urls.put(attr[1])

Answer 4

Вы можете сделать это довольно легко, просто используя links в качестве очереди:

def get_links(url):
    "Extract all matching links from a url"
    try:
        links = BeautifulSoup(urllib2.urlopen(url)).findAll(Crawler._match_tag)
    except urllib2.HTTPError:
        return []

def crawl(self, url):
    "Get all URLS from which to scrape categories."
    links = get_links(url)
    while len(links) > 0:
        link = links.pop()
        for attr in link.attrs:
            if Crawler._match_attr(attr):
                if Crawler._is_category(attr):
                    pass
            elif attr[1] not in self._crawled:
                self._crawled.append(attr[1])
                # prepend the new links to the queue
                links = get_links(attr[1]) + links

Конечно, это не решает проблему с памятью ...