Comment rendre cette fonction d'exploration récursive itérative?

Question

Pour des raisons académiques et de performance, compte tenu de cette fonction d'exploration Web récursive (qui explore uniquement dans le domaine donné), quelle serait la meilleure approche pour la faire fonctionner de manière itérative? Actuellement, quand il s'exécute, au moment où il se termine python a grimpé à l'aide de plus de 1 Go de mémoire qui n'est pas acceptable pour s'exécuter dans un environnement partagé.

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

Utiliser un BFS à la place de l'exploration récursive (DFS): http://en.wikipedia.org/wiki/Breadth_first_search

Vous pouvez utiliser une solution de stockage externe (par exemple une base de données) pour la file d'attente BFS pour libérer de la mémoire vive.

L'algorithme est:

//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

Au lieu de récursion, vous pouvez mettre les nouvelles URL à explorer dans une file d'attente. Ensuite, exécutez jusqu'à ce que la file d'attente soit vide sans être récursif. Si vous placez la file d'attente dans un fichier, cela n'utilise pratiquement aucune mémoire.

Answer 3

Vous pouvez le faire assez facilement en utilisant simplement links comme une file d'attente:

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 

Bien sûr, cela ne résout pas le problème de la mémoire ...

Answer 4

@Mehrdad - Merci pour votre répondre, l'exemple que vous avez fourni était concis et facile à comprendre.

La solution:

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])