冒号和他的学生们(连载9)——泛型范式

冒号和他的学生们

——程序员提高班纪事

  1. 泛型范式

算法是脊,数据是肉思想是鸡,结论是蛋                                      ——题记


冒号重新开讲:“你们会不会经常遇到这种情景:一遍又一遍地写着相似的代码,有心将其归并,却因种种原因无法践行。”

逗号心有戚戚焉道:“是啊,有时明明两个函数的实现几乎一模一样的,就因为某些参数不匹配,无法合而为一。”

“有一种编程范式可以解决这个问题,它打破了不同数据结构之间的壁垒,让你的代码不再臃肿,这——就是泛型编程。”冒号的语调和说辞不免令人联想到电视上的减肥广告,“Generic Programming,简称GP,其基本思想是:将算法与其作用的数据结构分离,并将后者尽可能泛化,最大限度地实现算法重用。这种泛化是基于模板的参数多态(parametric polymorphism),相比OOP基于继承的子类型多态(subtype polymorphism),不仅普适性更强,而且效率也更高。这不能不说是一种异数——我们知道,普适性往往是以效率为代价的。GP最著名的代表是C++中的STL,其后亦为JavaC#等所吸纳。此外,一些函数式语言如OcamlStandard MLGeneric Haskell等也支持GP。”

冒号写下两段代码——

C++(泛型编程):

template <typename T>

T max(T a, T b)       // 求出两个数中的较大者

{

      return  (a > b) ? a : b;

}

C(宏定义):

#define max(a,b) ((a) > (b) ? (a) : (b))

“求两个数中的较大值是经常遇到的问题。”冒号解说着,“对于静态类型语言来说,若参数类型不同,即使函数体相同也不能合为一体。如果语言不支持重载(overload),还可能出现maxIntmaxLongmaxFloat maxDouble之类的函数名,冗赘而丑陋。尽管在C中可用宏定义来实现,但无法保证类型安全,而C++模板则兼顾类型安全和代码重用,并且由于是在编译期间展开的,效率上也不损失。不止于此,C++支持运算符重载,除数值类型外,一切定义了‘> 运算的数据类型均可调用max函数,真是一举N得,N趋向无穷大啊!”

冒号边说边比划,夸张的语气和手势逗得大家都笑了。

引号提出疑问:“Java的一切对象都是Object,将所有参数都换成Object类型,岂不也是一种泛化?”

冒号答道:“首先,基本类型如intfloat等不是Object的子类,虽然Java 新增了自动装拆箱(autoboxing/unboxing)的功能,但要付出性能的代价。更重要的是,这将不可避免地需要类型强制转换,丧失了静态类型语言的优势,为Bug大开方便之门。这也是Java最终引入模板的原因,虽然有些姗姗来迟。类似地,C/C++中的通用指针void *也有类型安全问题。”

句号发表他的看法:“泛型虽好,似乎只是某些局部才用到的技术,不具有前面几种范式的渗透性。”

冒号听罢不语,返身在黑板上写下几道题——

1.从一个整数数组中随机抽取十个数,对其中的素数求和

2.将一个无序整数集中所有的完全平方数换成其平方根

3.从学生成绩表中,列出门门都及格且平均分在70分以上的学生名单

4.在一个着色二元树中,将所有的红色结点涂成蓝色

5.将一个字符串从倒数第三个字符开始反向拷贝到另一个字符串中

6.每从标准输入读取一个非数字的字符,于标准输出打印‘请输入数字’

 

句号暗忖,不过是些常规题嘛。不料冒号的问题却出人意表:“请问它们之间有何共同之处?能否共享一段代码?”

见众人缄默已久,冒号接着投影出一段代码——

template <class Iterator, class Act, class Test>

void process(Iterator begin, Iterator end, Act act, Test test)

// 对容器中在给定范围内(即起于begin止于end)所有满足给定条件的元

//素(即test(元素)==true)进行处理(即act(元素))

{

    for ( ; begin != end; ++begin)    // 从头至尾遍历容器内元素

        if (test(*begin)) act(*begin); // 若当前元素满足条件,则对其采取行动

}

STL有三要素:算法(algorithm)、容器(container)和迭代器(iterator)。容器是数据的集合,可理解为抽象的数组;迭代器是算法与容器之间的接口,可理解为抽象的指针或者游标。”冒号讲述道,“算法串联数据,如脊贯肉;数据实化算法,如肉附脊。只有抽象出表面的数据,算法的脊梁才能显现。以上几题看似风马牛不相及,若运用泛型思维,便可发现它们的共性:对指定集合中满足指定条件的元素进行指定处理。用模板语言,寥寥数行即勾勒完毕。”

问号诧异道:“相比前面的max模板,这里连元素的数据类型T都不见了?”

冒号回答:“元素被容器封装了。”

问号追问:“可这里连容器也看不到啊?”

冒号料有此问:“容器通过它的迭代器参与算法。”

句号豁然开朗:“通过模板,泛化了容器——可以是数组、列表、集合、映射、队列、栈、字符串等等;泛化了元素——可以是任何数据类型;泛化了处理方法和限定条件——可以是任何函数。”

冒号提醒道:“补充两点:处理方法和限定条件不限于函数,还可以是函子Functor)——自带状态的函数对象;另外还有一个隐蔽的泛化:迭代器——可以从前往后移动,可以从后往前移动,可以随机移动,也可以按任意预先定义的规律移动。”

叹号由衷感叹:“果然强悍啊!”

逗号倒也心细:“最后一题中标准输入也算容器吗?”

“为什么不呢?只要一个对象配备了迭代器,它就算容器。I/O流上就有现成的迭代器,当然你也可以自行定制。”冒号目光转向句号,“现在还有人说泛型编程渗透性不强吗?”

句号腆然一笑。

“这只是泛型编程的冰山一角。重要的是,我们不是在玩弄花哨的技巧,而是在用一种新的视角去审视问题。”冒号总结道,“泛型编程是算法导向Algorithm-Oriented)的,即以算法为起点和中心点,逐渐将其所涉及的数据结构内涵模糊化、外延扩大化,从而扩展算法的适用范围。这非常类似数学思维——当数学家证明完一个定理后,总会试图在保持核心思想的前提下,尽可能地放宽题设,增强结论,从而推广定理。外行人以为数学定理最重要,其实数学思想才是数学的精髓,在数学家眼里,思想是鸡,结论是蛋。这也无怪乎STL会出自一位学数学的人之手了。”


新版请见冒号课堂§3.1:泛型范式

posted on 2008-05-09 00:09 郑晖 阅读(4674) 评论(4)  编辑  收藏 所属分类: 冒号和他的学生们

评论

# re: 冒号和他的学生们(连载9)——泛型范式 2008-05-09 08:45 yanhuaking

写得很好,拜读了!感谢!  回复  更多评论   

# re: 冒号和他的学生们(连载9)——泛型范式 2008-05-09 09:44 herowzz

继续支持~~~  回复  更多评论   

# re: 冒号和他的学生们(连载9)——泛型范式 2008-05-13 15:33 支持支持!

例子可以再多些,简明是好,我也贪心多学一些,哈哈!!1  回复  更多评论   

# re: 冒号和他的学生们(连载9)——泛型范式 2008-12-24 19:38 杜飞

泛化。。。好  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 

导航

统计

公告

博客搬家:http://blog.zhenghui.org
《冒号课堂》一书于2009年10月上市,详情请见
冒号课堂

留言簿(17)

随笔分类(61)

随笔档案(61)

文章分类(1)

文章档案(1)

最新随笔

积分与排名

最新评论

阅读排行榜

评论排行榜