亲宝软件园·资讯

展开

工程中的算法应用 - 简单的三个例子

Licsber 人气:0
[TOC] ## 前言 其实这篇文章早就想写了,因为自己太懒,到现在才更新。虽然这三个例子都是最简单的算法,但是不得不说,相比较暴力的做法,确实提升了效率,也节省了程序员的时间。三个例子中用到的分别是二分查找、二维平均卷积、异步改同步。 ## 二分查找 ### 应用背景 给定一个URL资源接口,如XXX_001.mp4代表视频的第一秒、XXX_002.mp4代表视频的第二秒,以此类推;如何写一个多线程爬虫,把整个视频资源快速爬下来? ### 对照算法 容易想到的就是顺序爬取,直接假设资源具有999个,将URL生成好存在队列里,开50个线程依次获取,当有线程返回404时,通知队列清空,其他排在之后的线程也停止工作,等待未下载完毕的线程处理,之后程序退出。 ### 存在的问题 1. 假设资源只有20个,50个线程很明显一瞬间打出来30个404,这对网站也是一种攻击行为,很容易被反爬策略限制。 1. 各个线程之间的调度需要有效处理,假设2号线程返回404,在它之后从队列里拿取URL的所有线程都需要被停止,虽然Python的队列是线程安全的,但是需要操作已经运行的其他线程仍存在一定的问题。 1. 因为网络io的不稳定问题,很可能接口返回异常值如500,这时候需要处理重试,同时还需要及时确定资源是否已爬取完毕。 ### 解决方案 假设我们一开始就可以知道资源的总数,那么很容易得到队列里应有的URL,组织多线程爬取也就变得简单,只需要超时重试这一个操作即可。 这里可以对URL做一个抽象,我们进行二分查找的对象可以视为一个前半部分为1(200),后半部分为0(404)的数组:{1, 1, 1, 1, 0, 0, 0},于是问题变为,用最小的数组访问次数,找出来最右边的一个1。 ### 代码方案 这里是完整的代码实现: ```python queue = [] max_num = 1000 for i in range(max_num): ts = url.replace('{2}', '%03d' % i) save = save_dir + '/%03d.ts' % i queue.append((ts, save)) left = 0 right = max_num - 1 mid = 0 r = requests.get(queue[mid][0]) if r.status_code != 200: print(str(video) + ' total: %d' % mid) os.removedirs(save_dir) return while left <= right: mid = (left + right) // 2 q = queue[mid] u = q[0] r = requests.get(u) if r.status_code == 200: left = mid + 1 with open(q[1], 'wb') as f: f.write(r.content) else: right = mid - 1 r = requests.get(queue[mid][0]) if r.status_code == 200: if not spider.file_exists_or_has_content(queue[mid][1]): with open(queue[mid][1], 'wb') as f: f.write(r.content) mid += 1 queue = queue[:mid] print(str(video) + ' total: %d' % mid) ``` 可以看出,主要代码部分就是下面的二分查找,使用这样的临界处理,可以找出最右边的元素,以最小的访问次数获取URL资源总数,处理完毕后queue里就是所有的资源了,其中在中间阶段已经将爬取的部分视频保存,方便后面的线程不重复发起网络请求。这样我们就可以愉快的爬小黄网了(误 ## 二维平均卷积 ### 应用背景 给定一个原图像,一个输出框和一个代表原图像显著性分布的显著性图像(即画面主体的灰度图、越显著灰度值越高),如何调整输出框的位置,使得框住的图像显著性最高(即裁剪问题)? ### 对照算法 暴力解决的话很容易想到dp的方法,将输出框左上角从(0, 0)开始位移,第一次计算所有像素灰度的sum,每次移动都加上新覆盖的一行(列)的灰度并减去取消覆盖的一行(列)的灰度。 ### 存在的问题 1. 耗时,是非常耗时,这种密集的cpu操作,io极短,相当于一直在让cpu做加法、减法。 1. 假设我们需要对N对图片都进行这样的处理,即对视频的每一帧处理,算法的执行时间会成为严重性能瓶颈。 ### 解决方案 有一种加速类似运算的操作叫做卷积,一般我们选择的卷积核是为了提取图像关键部分、或为了图像增强,但是在这里,可以有效的利用卷机的硬件加速效果实现我们的算法加速;同时采用平均卷积避免加和出来的结果过大导致计算放慢。 ### 代码方案 这里是完整的代码实现: ```python def crop_fix(sframe, sheight, swidth): skenerl = np.ones((sheight, swidth)) / (sheight * swidth) s = signal.convolve2d(sframe, skenerl, mode='valid') m = np.argmax(s) r, c = divmod(m, s.shape[1]) return r, c ``` 简洁易懂,这大概我2020上半年写的最优雅的代码了吧,有效利用硬件加速效果,全部使用库里优化过的函数。于是就可以愉快的省下时间划水啦(误 ## 异步改同步 这个理论上不算算法的解决方案,但是也属于代码的小trick,一并介绍了。 ### 应用背景 假如你有一个JTree(Java Swing知识、未获取前置知识点的同学请看书),即一个树形菜单,其中每个节点的展开都会触发Expand事件(委托事件模型、Swing的nb之处),其会启动一个线程用以发起网络请求,动态加载树的子节点;现在新增了一个需求,需要完全展开这个树,同时保证请求数不至于爆炸,怎么实现? ### 对照算法 正常来说展开这个树,我们会使用递归算法,展开一个节点,遍历其子节点依次调用这个算法,当这个节点是子节点时停止。 ### 存在的问题 1. 由于节点的展开与节点内容的获取时异步的,递归算法不知道需要等待多长时间再开始遍历其子节点,导致树的展开不彻底。 1. 由于算法使用递归,很难控制一个有效的延迟时间,使得每秒请求数不至于过高。 ### 解决方案 将源代码中异步的方法尝试改为同步,但又不影响原来的代码逻辑;这里想到了Java的synchronized和ReentrantLock,这里选用前者实现,因为后者还需要在类中维护一个变量,较为麻烦。 ### 代码方案 首先我们在异步方法里加上这一句: ```java synchronized (ChxGUI.this) { ChxGUI.this.notify(); } ``` 这样既不会影响原来代码的逻辑,又方便了我们获取进程执行结束的信息。之后实现我们需要的业务代码即可: ```java allButton.addActionListener(e -> new Thread(() -> { ChxGUI gui = ChxGUI.this; gui.label.setText("请不要操作 稍等一会"); gui.tree.setEnabled(false); synchronized (ChxGUI.this) { try { gui.tree.expandRow(0); Thread.sleep((int) (1000 * Math.random())); ChxGUI.this.wait(); } catch (InterruptedException ex) { ex.printStackTrace(); } } TreeNode root = (TreeNode) gui.treeModel.getRoot(); for (int i = root.getChildCount() - 1; i >= 0; i--) { TreeNode course = root.getChildAt(i); synchronized (ChxGUI.this) { try { gui.tree.expandPath(ChxUtility.getPath(course)); Thread.sleep((int) (1000 * Math.random())); ChxGUI.this.wait(); } catch (InterruptedException ex) { ex.printStackTrace(); } } for (int j = course.getChildCount() - 1; j >= 0; j--) { TreeNode lesson = course.getChildAt(j); synchronized (ChxGUI.this) { try { gui.tree.expandPath(ChxUtility.getPath(lesson)); Thread.sleep((int) (2000 * Math.random())); ChxGUI.this.wait(); } catch (InterruptedException ex) { ex.printStackTrace(); } } } } gui.tree.setEnabled(true); gui.label.setText("就绪。"); }).start() ); ``` 这里的重点就是使用同一个同步量进行两者的同步,这样可以把代码从异步执行改为同步执行,请求API的次数也就变得安全可控。于是就可以愉快的刷[网课](https://github.com/MikeWang000000/ChxUtility)啦(误 ## 后记 这些应该是些常见的优化思路,写在这里是因为我确实运用这些解决了实际问题,也取得了不错的效果,coding改变世界,我坚信这一点,也希望分享这段经历给更多的人,学而不已、阖棺乃止,今天是国家公祭日,愿逝者安息,愿生者奋发,愿祖国昌盛,致敬英雄!

加载全部内容

相关教程
猜你喜欢
用户评论