最初のページのすべてのリンクを訪問し、各リンクにアクセスし、すべての2番目のページのリンクを訪問することを意味する深さの最初のWebスパイダーを構築する...ウェブスパイダーを構築するときに、再帰を使用する必要がありますか？
再帰を使用する必要がありますか？私はこれがCPU集約的であることがわかります。
def recursion()
linkz_on_first_page.each do |link|
recursion(link)
end
end
recursion(firstpage)
再帰はCPU集約的ではありませんが（実際はそうではありませんが）、数千回の再帰呼び出しの後にコールスタックを爆破します。開いた状態で実行しているWebスパイダーインターネット。
例：
def blow_stack(level=0)
puts "at level #{level}"
blow_stack(level+1)
end
私のMacBook Proの上でこのの出力：
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
実際には、ワールドワイドウェブの実際の性質のため、非常に迅速に問題に遭遇します。もう1つはメインのナビゲーションセクションでサイトにアクセスし、各ページがリンクしている間に無限ループに入りました。
あなたが扱ったリンクを追跡することはできますが、それでも再帰的なループは実際にはワールドワイドウェブの性質に適合しません（ただし、当初考えられたように、ウェブは実際の「ウェブ」はツリーよりも）。現在のページ上のすべてのリンクを見つけて、それらが存在しない場合は中央のキューに追加することをお勧めします。また、すべてのリンクを処理するキューを反復して処理してください。処理を完了したリンク、またはキューの最後にもう一度追加してください）
私の即時の思考はまた、 "キュー" でした。ちょっと重複しないインテリジェンスが追加される可能性があるので、私はそれが非常に堅牢なスケーリング機能の基礎を提供することも期待しています。 –
キューを作成するにはどうすればよいですか？すべてのリンクを含む大きな配列を作成し、各リンクに移動する前にこれが以前に訪問されていないことを確認することを意味しますか？ – pgh
理論的には配列で十分ですが、実際には中央キューがボトルネックになるため、パフォーマンス/スケーラビリティの問題が発生します。ルックアップ時間を短縮するために、ハッシングや何かに陥る可能性があります。 – sebastiangeiger
再帰が適切と思われるまで、もう少し考えてみてください。 ページAにページBへのリンクがあり、ページBにページAへのリンクが含まれている場合、あなたは無限のサイクルで立ち往生しています。
再帰は、通常の方法で行うよりも、それ以上のCPU集約はありません。あなたはすべてのリンクが必要かどうか、または特定のレベルまでリンクをつかむだけで十分であるかどうかを自問する必要があります。後者の場合、これはまたあなたの無限のサイクル問題を解決します。
すべてのリンクが必要な場合は、むしろ各リンクが一意であるリンクのリストを使用します。プログラムはリストからリンクを取り、このリンクをスパイダーします。新しいリンクが発見されると、それをこのリストに挿入しようとします。
あまりにも遅い。 – sebastiangeiger
スタックを呼び出すと、それらは適切に閉じられます。 – pgh
私はその質問に従うかどうか分からない。 私が "コールスタック"と言うとき、私は関数呼び出しスタックを参照しています。これは、ほとんどの言語（Rubyを含む）がどの関数が呼び出されたかを追跡するために使用します。このスタックは有限のサイズ（通常は数千のメソッド呼び出しレイヤーのための空間）です。したがって、深い再帰を行っていると、スタック領域が不足します。 これは、通常の非再帰関数によってアクセスされる通常の「スタック」とは異なります。それはうまくいくでしょう。 – madlep