聊聊那些专为算法设计的模式

作者简介:

罗伟富(Spencer.Luo),某知名在线教育公司技术专家。3 年 SDK 开发,2 年客户端开发,现从事后端基础技术研究,从底层到应用层,从前端到后端积累了丰富的开发经验,熟悉 C++、Java、Python、PHP 等多种不同开发语言。热爱生活、喜欢技术、善于用生活的场景解读难懂的技术!

AI 越来越火热,人工智能已然成风!而人工智能最重要的是各种算法,因此机器学习越来越受到追捧,算法越来越被重视。

作为一个算法的研究者,写出一手高级算法当然是令人兴奋的一件事!但你是否有时会有这种感觉:

写的算法很难通用于所有的数据类型!每来一个新类型的数据,又得改一下算法,或新加一个方法来支持这种类型。

有时候多个算法需要灵活组合,甚至每个算法的顺序不一样都会产生不一样的效果;每一种组合都要为其构建一个新算法,既累又麻烦。

算法越来越多,自建的算法库也越来越庞大而难于管理。

这个时候,让你的算法具有更好通用性、拓展性就显得极为重要了!因此,你必须要掌握几个重要的设计模式优化你的代码来解决这些问题。

今天就来聊聊那些专为算法设计的模式:策略模式、模板方法模式、访问模式。

1. 策略模式

定义一系列算法,将每个算法都封装起来,并且使他们之间可以相互替换,策略模式使算法可以独立于使用它的用户而变化。

策略模式当属在算法领域中应用最广泛的一种设计模式,它是对算法、规则的一种封装,具有以下的优点:

算法(规则)可自由地切换。

避免使用多重条件判断。

方便拓展和增加新的算法(规则)。

应用案例

假设有这样一个应用场景:

有一 Person 类,有年龄(age)、体重(weight)、身高(height)三个属性,现要对 Person 的一组对象进行排序,但并没有确定根据什么规则来排序,有时需要根据年龄进行排序,有时需要根据身高进行排序,有时可能是根据身高和体重的综合情况来排序,还有可能……

通过对这个应用场景进行分析,我们会发现,这里需要有多种排序算法,而且需要动态地在这几种算法中进行选择,在未来可能还会添加一新的排序规则……

怎样让我们的排序算法更加的灵活,以适应各种各样的排序规则呢?这里我们就要用到策略模式。来,一起看一下具体的代码实现吧。

源码示例:

测试代码:

输出结果:

根据年龄进行排序后的结果:

Tony 2 years old, 54.5kg, 0.82m.

Helen 16 years old, 45.7kg, 1.6m.

Eric 23 years old, 62.0kg, 1.78m.

Jack 31 years old, 74.5kg, 1.8m.

Nick 54 years old, 44.5kg, 1.59m.

根据身高进行排序后的结果:

Tony 2 years old, 54.5kg, 0.82m.

Nick 54 years old, 44.5kg, 1.59m.

Helen 16 years old, 45.7kg, 1.6m.

Eric 23 years old, 62.0kg, 1.78m.

Jack 31 years old, 74.5kg, 1.8m.

看到这,一些熟悉 Python 的读者肯定要吐槽了!Python 是一个简洁明了的语言,使用 2 行代码就能解决的问题(如下面代码),为什么要写上面这一大堆的东西。

能提出这个问题,说明你一定是带着思考在阅读!之所以还要这么写,出于以下几个原因:

设计模式是一种编译思想,它和语言没有强关联,应当适用于所有面向对象的语言。

Python 因为语言本身的灵活性和良好的封装性,使得其自带了很多的功能,而其他语言并没有这样的功能,也许你的算法就是用 C++ 或者 Java 来写的呢!为了让熟悉其他语言的人也能看懂,这里使用了最接近面向对象思维的方式进行实现。

使用 Python 语言本身的特性,还是难以实现一些特殊的需求,如要根据身高和体重的综合情况来排序(身高和体重的权重分别是 0.6 和 0.4)。

用策略模式就可以很方便地实现,只需要增加一个 CompareByHeightAndWeight 的策略类就可以,如下面代码:

2. 模板方法模式

Define the skeleton of an algorithm in an operation, deferring some steps to client subclasses. Template Method lets subclasses redefine certain steps of an algorithm without changing the algorithm's structure.

定义一个操作中的算法的框(骨)架,而将算法中用到的某些具体的步骤放到子类中去实现,使得子类可以在不改变算法结构的情况下重新定义该算法的某些特定步骤,这个定义算法骨架的方法就叫模板方法。

对一些复杂的算法进行分割,将其算法中固定不变的部分设计为模板方法和父类具体方法,而一些可以改变的细节由其子类来实现,即一次性实现一个算法的不变部分,并将可变的行为留给子类来实现。

应用案例

模板方法模式非常简单,以至于我都不觉得它是一个模式,因为只要是在使用面向对象的语言进行开发,你就有意无意之中已经在使用它了,举一个例子。

在图形图像的处理中,对图像像素进行微分求导,进行图像的锐化处理,是一个非常基础而又重要的算法。在对图像的一阶微分求导算法中,有两个非常重要的算法:水平微分算子和垂直微分算子,另一个非常著名的算法 Sobel 微分算子,也是基于这两个算法来实现的。

水平微分算子

定义

Gx=f(x-1,y-1) + 2f(x-1,y) + f(x-1,y+1) - f(x+1,y-1) - 2f(x+1,y) - f(x+1, y+1)

算法核模板

垂直微分算子

定义

Gy=f(x-1,y-1) + 2f(x,y-1) + f(x+1,y-1) - f(x-1,y+1) - 2f(x,y+1) - f(x+1,y+1)

算法核模板

Sobel 微分算子

定义

Gx=f(x-1,y-1) + 2f(x-1,y) + f(x-1,y+1) - f(x+1,y-1) - 2f(x+1,y) - f(x+1, y+1)Gy=f(x-1,y-1) + 2f(x,y-1) + f(x+1,y-1) - f(x-1,y+1) - 2f(x,y+1) - f(x+1,y+1)G=sqrt(Gx^2 + Gy^2)

也就是对水平微分和垂直微分的两个计算结果,再进行算术平方计算。

自己实现这个算法

虽然像 OpenCV 等这些成熟的图形图像算法库都提供了这一基础的算法,但作为一个图形图像算法的研究者,你有没有想过自己去实现一下这个简单的算法!我是有的,你呢?

水平微分算子和垂直微分算子这两个算法非常的相似,不同之处在于:一个是在水平方向上处理,一个是在垂直方向上处理。

这两个算法既然如此的相似,那肯定会有一些共同的部分,如像素的遍历:也有不同的部分,如算法的核模板不同。

这个时候,我们就可以考虑使用模板方法的设计了。来看一下我们实现(下面这段代码应用到的拓展库:opencv-3.4.1,numpy-1.14.5):

算法实现:

测试代码:

实现的效果与 OpenCV 的效果一模一样,我们一起来看一下。

原图:

水平微分求导后:

垂直微分求导后:

Sobel 微分计算后:

3. 访问模式

封装一些作用于某种数据结构中各元素的操作,它可以在不改变数据结构的前提下定义作用于这些元素的新的操作。

访问模式的核心思想在于:可以在不改变数据结构的前提下定义作用于这些元素的新操作。将数据结构和具体算法进行解耦,而且能更方便地拓展新的操作。

访问模式的代码框架

这里 Visitor 的访问方法只有一个 visit(),是因为 Python 不支持方法的重载。在一些强类型的语言(如 Java、C++)中,应该有多个方法,针对每一个 DataNode 子类定义一个重载方法。

访问模式的类图结构:

DataNode 是数据结点,可接受(accept)访问者的访问,DataNodeA 和 DataNodeB 是它的具体实现类。Visitor 是访问者类,可访问(visit)具体的对象。ObjectStructure 是数据结构的管理类,也是数据对象的一个容器,可遍历容器内的所有元素。

应用案例

在宠物界中,猫和狗历来就是一对欢喜冤家!假设宠物店中有 N 只猫和 M 只狗,我们要进行下面这3个操作:

在这些宠物中雌猫、雄猫、雌狗、雄狗的数量分别是多少。

猫的平均体重和狗的平均体重分别是多少。

年龄最大的猫和狗。

这个时候,如果要在猫和狗的对象上添加这些操作,将会增加非常多的方法而污染原有的对象;而且这些操作的拓展性也将非常差。这时访问模式是解决这个问题的最好方法,我们一起看一下具体的实现如下:

源码示例:

测试代码:

输出结果:

1只雄猫,1只雌猫,1只雄狗,2只雌狗。

猫的平均体重是:4.70kg, 狗的平均体重是:18.00kg

访问模式将“数据”和“操作算法”分离,降低了耦合度。将相关元素对象的访问行为集中到一个访问者对象中,而不是分散在一个个的元素类中,类的职责更加清晰;操作算法更易拓展。

访问模式特别适合应用于以下场景:对象结构中包含的对象类型比较少,而且这些类需要比较固定,很少改变,但经常需要在此对象结构上定义新的操作。

Get 到这些技能点了吗?

《从生活中领悟设计模式(Python)》适合具有一定编程基础又渴望提升自己编程技能的人,此课程如果武功秘籍一般力求用最通俗的语言阐述最难懂的概念;用最简单的语法实现最复杂的逻辑;用最短小的代码写出最强悍的程序!

从生活中领悟设计模式

原价 39.99

限时特价:24.99

试读

订购本课程可获得专属海报,分享专属海报每成功邀请一位好友购买,即可获得 25% 的返现奖励,多邀多得,上不封顶,立即提现。

此课程分三卷内容:

第一卷:基础篇(第01~21课),19 种常用设计模式单独章节讲解 + 剩余 4 种模式合集(会有1~2篇的篇幅);

第二卷:进阶篇(第22~24课),是基础设计模式的衍生,也是各大编程语言中非常重要而常见的种编程机制;

第三卷:经验篇(第25~27课),将会分享我对设计原则、设计模式、项目重构的经验和看法。

—— END ——

分享决定技术高度

学习拉开技术差距

>>GitChat

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180906B1ZCB800?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券