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

04/04 18:20
阅读数 7

[TOC]

前言

其实这篇文章早就想写了,因为自己太懒,到现在才更新。虽然这三个例子都是最简单的算法,但是不得不说,相比较暴力的做法,确实提升了效率,也节省了程序员的时间。三个例子中用到的分别是二分查找、二维平均卷积、异步改同步。

二分查找

应用背景

给定一个URL资源接口,如XXX_001.mp4代表视频的第一秒、XXX_002.mp4代表视频的第二秒,以此类推;如何写一个多线程爬虫,把整个视频资源快速爬下来?

对照算法

容易想到的就是顺序爬取,直接假设资源具有999个,将URL生成好存在队列里,开50个线程依次获取,当有线程返回404时,通知队列清空,其他排在之后的线程也停止工作,等待未下载完毕的线程处理,之后程序退出。

存在的问题

  1. 假设资源只有20个,50个线程很明显一瞬间打出来30个404,这对网站也是一种攻击行为,很容易被反爬策略限制。
  2. 各个线程之间的调度需要有效处理,假设2号线程返回404,在它之后从队列里拿取URL的所有线程都需要被停止,虽然Python的队列是线程安全的,但是需要操作已经运行的其他线程仍存在一定的问题。
  3. 因为网络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.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做加法、减法。
  2. 假设我们需要对N对图片都进行这样的处理,即对视频的每一帧处理,算法的执行时间会成为严重性能瓶颈。

解决方案

有一种加速类似运算的操作叫做卷积,一般我们选择的卷积核是为了提取图像关键部分、或为了图像增强,但是在这里,可以有效的利用卷机的硬件加速效果实现我们的算法加速;同时采用平均卷积避免加和出来的结果过大导致计算放慢。

代码方案

这里是完整的代码实现:

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. 由于节点的展开与节点内容的获取时异步的,递归算法不知道需要等待多长时间再开始遍历其子节点,导致树的展开不彻底。
  2. 由于算法使用递归,很难控制一个有效的延迟时间,使得每秒请求数不至于过高。

解决方案

将源代码中异步的方法尝试改为同步,但又不影响原来的代码逻辑;这里想到了Java的synchronized和ReentrantLock,这里选用前者实现,因为后者还需要在类中维护一个变量,较为麻烦。

代码方案

首先我们在异步方法里加上这一句:

 synchronized (ChxGUI.this) {
     ChxGUI.this.notify();
 }

这样既不会影响原来代码的逻辑,又方便了我们获取进程执行结束的信息。之后实现我们需要的业务代码即可:

    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的次数也就变得安全可控。于是就可以愉快的刷网课啦(误

后记

这些应该是些常见的优化思路,写在这里是因为我确实运用这些解决了实际问题,也取得了不错的效果,coding改变世界,我坚信这一点,也希望分享这段经历给更多的人,学而不已、阖棺乃止,今天是国家公祭日,愿逝者安息,愿生者奋发,愿祖国昌盛,致敬英雄!

原文出处:https://www.cnblogs.com/licsber/p/engineering-algo.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部