この再帰的クロール機能を反復的にするにはどうすればよいですか？

Question

学問的にもパフォーマンス上の理由から、このクロールの再帰的なWebクローリング機能（指定されたドメイン内でのみクロールする）が繰り返し実行される最良の方法は何ですか？現在のところ、それが終了するまでに、Pythonは1GB以上のメモリを使用するようになりました。これは共有環境での実行には受け入れられません。

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

ではなく（DFS）を再帰的にクロールのBFSを使用します。http://en.wikipedia.org/wiki/Breadth_first_search

あなたはRAMを解放する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

あなただけのキューとして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 

を、これはメモリの問題を解決していません...

Answer 4

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