當建立一個網絡蜘蛛，你應該使用遞歸？

構建一個深度優先的網絡蜘蛛，意味着它將訪問第一頁上的所有鏈接，並轉到每個鏈接，並訪問所有第二頁上的鏈接...當建立一個網絡蜘蛛，你應該使用遞歸？

您應該使用遞歸嗎？我覺得這是cpu密集型的。

def recursion() 

linkz_on_first_page.each do |link| 

recursion(link) 

end 
end 
recursion(firstpage)

來源

2009-11-25 pgh

這並不是說CPU的遞歸密度太高（不是真的），但更重要的是，在幾千次遞歸調用之後，你會炸掉你的調用堆棧 - 你會輕易地編寫一個在開放時運行的web蜘蛛互聯網。

示例：這對我的MacBook Pro

def blow_stack(level=0) 
    puts "at level #{level}" 
    blow_stack(level+1) 
end

輸出：

irb(main):009:0> blow_stack 
at level 0 
at level 1 
... (skip a bunch of output) 
at level 6295 
at level 6296 
SystemStackError: stack level too deep 
     from (irb):7:in `blow_stack' 
     from (irb):7:in `blow_stack' 
     from (irb):9 
     from :0

來源

2009-11-25 21:13:57 madlep

如果我調用堆棧，它們會被適當關閉。 – pgh 2009-11-26 08:24:25

不知道我是否遵循這個問題pgh。當我說「調用堆棧」時，我指的是大多數語言（包括Ruby）用來跟蹤調用了哪些函數以及返回的位置的函數調用堆棧。這個堆棧的大小是有限的（通常可以容納幾千個方法調用層），所以如果你進行深度遞歸，你將用完堆棧空間。這與通過常規非遞歸函數訪問的常規「堆棧」不同。這將工作正常。 – madlep 2009-11-26 22:09:04

絕對不會，因爲萬維網的實際性質，您將很快遇到問題。第二個你打了一個主導航部分的網站，每個頁面鏈接到另一個頁面，你已經進入了一個無限循環。

你可以跟蹤你已經處理了哪些鏈接，但即使如此，遞歸循環並不真正適合萬維網的本質（儘管起初認爲網絡更像是一個實際的「網」比樹）。你最好找到當前頁面上的所有鏈接，並將這些鏈接（如果它們不存在的話）添加到中央隊列中，然後迭代地處理每個鏈接的隊列處理過程（記住跟蹤你已經完成處理的鏈接，或者你將它們再次添加到隊尾）

來源

2009-11-25 11:27:43 LorenVS

我馬上想到還「排隊」。隨着可能增加一點去重複智能，我預計它還將爲非常強大的縮放功能提供基礎。 – 2009-11-25 11:33:45

我如何創建隊列？你的意思是創建一個包含所有鏈接的大數組，並且在導航到每個鏈接之前，檢查之前沒有訪問過嗎？ – pgh 2009-11-25 11:35:06

從理論上講，陣列就足夠了，實際上你會遇到性能/可分性問題，因爲你的中央隊列將成爲瓶頸。你可能會進入哈希或某些東西來減少查找時間。 – sebastiangeiger 2009-11-25 11:37:42

遞歸似乎是合適的 - 直到你想到更多關於它。如果你有一個包含頁面B和頁面B的鏈接的頁面A包含頁面A的鏈接，你就陷入了一個無限循環。

遞歸沒有比以「正常」方式進行更多的CPU密集型操作。你必須問自己，你是否需要所有的鏈接，或者只需要抓取鏈接到一定水平就足夠了。在後一種情況下，這也解決了無限循環問題。

如果您需要所有鏈接，我寧願使用鏈接列表，每個鏈接都是唯一的。你的程序從列表和蜘蛛鏈接這個鏈接。一旦發現新鏈接，就嘗試將其插入此列表中，等等。

來源

2009-11-25 11:31:56 sebastiangeiger

該死的...太慢。 – sebastiangeiger 2009-11-25 11:32:38

當建立一個網絡蜘蛛，你應該使用遞歸？

回答

相關問題