赞
踩
[TOC]
前言
其实这篇文章早就想写了,因为自己太懒,到现在才更新。虽然这三个例子都是最简单的算法,但是不得不说,相比较暴力的做法,确实提升了效率,也节省了程序员的时间。三个例子中用到的分别是二分查找、二维平均卷积、异步改同步。
二分查找
应用背景
给定一个URL资源接口,如XXX_001.mp4代表视频的第一秒、XXX_002.mp4代表视频的第二秒,以此类推;如何写一个多线程爬虫,把整个视频资源快速爬下来?
对照算法
容易想到的就是顺序爬取,直接假设资源具有999个,将URL生成好存在队列里,开50个线程依次获取,当有线程返回404时,通知队列清空,其他排在之后的线程也停止工作,等待未下载完毕的线程处理,之后程序退出。
存在的问题
假设资源只有20个,50个线程很明显一瞬间打出来30个404,这对网站也是一种攻击行为,很容易被反爬策略限制。
各个线程之间的调度需要有效处理,假设2号线程返回404,在它之后从队列里拿取URL的所有线程都需要被停止,虽然Python的队列是线程安全的,但是需要操作已经运行的其他线程仍存在一定的问题。
因为网络io的不稳定问题,很可能接口返回异常值如500,这时候需要处理重试,同时还需要及时确定资源是否已爬取完毕。
解决方案
假设我们一开始就可以知道资源的总数,那么很容易得到队列里应有的URL,组织多线程爬取也就变得简单,只需要超时重试这一个操作即可。
这里可以对URL做一个抽象,我们进行二分查找的对象可以视为一个前半部分为1(200),后半部分为0(404)的数组:{1, 1, 1, 1, 0, 0, 0},于是问题变为,用最小的数组访问次数,找出来最右边的一个1。
代码方案
这里是完整的代码实现:
queue = []
max_num = 1000
for i in range(max_num):
ts = url.replace('{2}', '%03d' % i)
save = save_dir + '/%03d.
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。