0

今、私はこのような問題に直面しています：

たとえば、URLのリストがあるとします。

['http://example.com/1', 
 'http://example.com/2', 
 'http://example.com/3',
 'http://example.com/4', 
 ..., 
 'http://example.com/100']

そして、それらのいくつかは利用できないURLであり、それらのURLを要求すると、302リダイレクトステータスコードになります。例：..​​. / 1-... / 50は利用可能なURLですが、... / 51は302を引き起こします。次に、.../50が必要なURLです。

どのURLが最後に利用可能なURL（302コードを返さない）であるかを知りたいのですが、バイナリ検索でうまくいくと思いますが、より効率的に実装するにはどうすればよいでしょうか。私はPythonのurllib2を使用して302ステータスコードを検出します。

pseg ... / 1-... / 50は利用可能なURLですが、... / 51は302を引き起こします。次に、.../50が必要なURLです。

4

3 に答える 3

1

ロット全体をチェックするだけですが、代わりrequestsに使用して、帯域幅を抑えるurllib2ように要求するだけにしてください（とにかく、これが最大のボトルネックになる可能性があります）。HEAD

import requests

urls = [...]
results = [(url, requests.head(url).status_code) for url in urls]

それからそこから行きます...

于 2012-12-21T16:29:33.197 に答える
1

二分探索が順序反復よりも速くなる方法がわかりません。ほとんどの場合、最終的には遅くなります。リストnの長さを指定すると、最初の適切なバッチの最後の適切な URL を検索している場合、urls[n/2]-1ターゲットがブルート フォース イテレーションと同じ数の検索を行う場合のみです。他のすべてはもっとかかります。リスト全体で最後の適切な URL を探している場合、逆順の反復と比較して同じ数の検索を行う唯一の検索ターゲットは次のようになります。urls[n/2]-1. 二分探索は、データセットが順序付けられている場合にのみ高速になります。順序付けられていないデータセットの場合、セットの中央をサンプリングしても、その両側の値を除外できることについては何もわかりません。そのため、何かを知る前にシーケンス全体を処理する必要があります。

ここであなたが本当に望んでいるのは、ターゲットを見つける前に実行するリクエストを少なくできるように、データセットを間隔を置いてサンプリングする方法であると思いますが、これは二分探索とはまったく同じではありません。バイナリ検索は、シーケンス内のポイントをサンプリングすると、バイナリ条件に基づいて後続の検索からシーケンスの一方または他方を除外できるという情報が得られるという事実に依存しています。あなたが持っているのは、サンプルがテストに失敗した場合、一方を除外できるシステムですが、テストに合格した場合、リスト内の他の値について何を想定できるかについて何も教えてくれません. これは、バイナリ検索では実際には機能しません。

于 2012-12-21T16:44:34.423 に答える
1

この回答は、URLが現在意味のある順序で並べられており、ある値までのすべての URLnが利用可能で、それ以降のすべての URLnが 302 になることを前提としています。

この場合、このバイナリ検索の回答をニーズに合わせて調整できます。

import requests

def binary_search_urls(urls, lo=0, hi=None):
    if hi is None:
        hi = len(urls)
    while lo < hi:
        mid = (lo+hi)//2
        status = requests.head(urls[mid]).status_code
        if status != 302:
            lo = mid+1
        else: 
            hi = mid
    return lo - 1

これにより、最後の適切な URL のインデックスが-1表示されます。適切な URL がない場合も同様です。

于 2012-12-21T16:42:35.300 に答える