0

现在我面临这样的问题：

假设我有一个网址列表，例如

['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

此答案假设您的 URL当前以有意义的方式排序，并且所有达到某个值的 URLn都将可用，并且之后n的所有 URL 将导致 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 回答
1

我看不出二进制搜索如何比直接迭代更快，而且在大多数情况下，它最终会变慢。给定n的是列表的长度，如果您正在搜索第一个好批次的最后一个好 url，那么只有在urls[n/2]-1您的目标是与暴力迭代相同的搜索次数的情况下；所有其他人都需要更多。如果您正在寻找整个列表中最后一个好的 url，那么与倒序迭代相比，唯一会进行相同数量搜索的搜索目标将是urls[n/2]-1. 只有在对数据集进行排序时，二进制搜索才会更快。对于无序数据集，在集合的中间进行采样并不能告诉您能够将值排除到它的任一侧，因此您仍然必须处理整个序列才能说出任何内容。

我怀疑您在这里可能真正想要的是一种每隔一段时间对数据集进行采样的方法，这样您就可以在找到目标之前运行更少的请求，这与二进制搜索不太一样。二进制搜索依赖于这样一个事实，即对序列中的一个点进行采样提供了有关能够从基于二进制条件的后续搜索中排除序列的一侧或另一侧的信息。你所拥有的是一个系统，如果一个样本没有通过测试，你可以排除一侧，但如果它通过了测试，它不会告诉你关于列表中任何其他值的假设。这对于二进制搜索实际上并不适用。

于 2012-12-21T16:44:34.423 回答