软件开发>杂文>8

共享软件开发的点滴心得

[中文][English][日本語

[机器人制作] [软件开发] [豆知识] [Squeak] [关于]

C++ template algorithms

授人以鱼

刘新宇

20067

 

最近在翻译一篇英文文章时,看到这样的话:“There is a school of thought that says that students should be taught the abstractions necessary for proper execution in a domain before they are taught the actual execution.[1]”这段话看起来明白,但是译起来却倍感吃力。总觉得似乎中文里有什么俗语格言能够一言以蔽之。结果发现最近一些教师在反思教学的过程中,常用这么一句话:“授人与鱼不若授人与渔”,颇有一些神似。理论先于实践;构思先于动手;这就是基础教育中,数学和物理的意义。

在养家糊口的生活压力下,很少有人在一生中会感觉到直接使用数学或物理知识。如果不亲自乘坐飞机,调整时差,有谁会直接感到脚下的大地是球形的呢?其实地球这个常识也是拜数学所赐。大约公元前240年,某一个621日的中午,太阳直射进入了阿斯旺的一口井里。而住在北方亚历山大城的埃拉托斯特尼(Eratosthenes)发现太阳却不在头顶,立在地上的竿子会有一段影子,他测量了太阳的高度为7度,于是他推断出地球是球形的,并且根据两地的距离计算出了地球的周长[2]

计算机科学也是建立在数学之上的一门科学。所以算法先于编程,授人与代码不若授人与算法。Eratosthenes不仅留下了测量大地的故事,还留下了筛法来检定素数[3]。作为本文的开篇,这里试图利用C++template推导来实现这个古老的筛法。

Eratosthenes筛法

 

首先考虑素数的定义,素数又称质数,是只有两个正因数(1和自己)的自然数。目前已知最小的素数是2,而最大的素数不存在。Eratosthenes筛法的首先从以2开头的自然数序列开始,经过一系列筛选,最终得到N以内的素数序列。写成算法合约[4]为:

// N --> listof (Prime Numbers)

// Input N, output a list of Prime Numbers.

例如,用户输入10,该算法输出2, 3, 5, 7;用户输入20,则该算法输出2, 3, 5, 7, 11, 13, 17, 19

Eratosthenes筛法的思路非常朴素简单,如果一个数不是素数,那么他必然是某个素数的整数倍,所以从最小的素数2开始,先筛掉所有2的倍数,这时剩下的最小的数就是2之后的第二个素数,然后再筛掉所有第二个素数的所有倍数,重复这个筛除过程,最后得到的就是一个素数序列。例如,假设要找出20以内的所有素数,那么首先得到的起始序列为:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

然后筛掉第一个素数2的倍数:

2, 3, 5, 7, 9, 11, 13, 15, 17, 19

这样得到了2后面的素数3,然后筛掉所有3的倍数:

2, 3, 5, 7, 11, 13, 17, 19

重复上面的步骤,最后就会得到20以内的素数序列。通过上面的简介和简单示例,就可以尝试给出这个筛法的较正式描述:

  1. 生成以2开头,依次递增到N的自然数序列;
  2. 取出序列中的第一个数P,放到结果素数序列中;
  3. 在剩下的序列中,筛掉所有P的倍数;
  4. 重复2,直到序列变空。

依照这个设计, 就可以逐步实现这个算法,一般有自顶至下的实现方法和自底至顶的实现方法。然而在大量的实践中,绝对化的采用某种方法并不总能有效。本文采用“关键问题” 方法,这种方法是人类在解决工程问题时采用的一种朴素方法。一般来说在解决某一问题时,人们并不是一开始就束手无策。而往往是有一个大致规划,把复杂问题 分解为若干小问题,这些小问题中,有些非常简单,可以轻易解决,也有些非常困难,但是却制约成败。这些问题被称为“关键问题”。关键问题的依次解决可以极 大地提高人们攻克整个问题的信心。它意味着整体复杂问题的解决方案可以全部被掌握。

比如《三国演 义》里面的赤壁之战,孙权刘备联军需要解决的问题的击败数量上占优势的曹操军队。整个解决方案的思路并不复杂——联军准备采用“火攻”的方法。整个火攻的 方案中有一些问题非常容易解决,比如除掉对方的水军将领,安插卧底的奸细;有些问题就比较困难,比如引诱对方把船只用铁索连起来;还有些问题看似很小,但 却是关乎成败的关键问题,比如要保证发动攻击时的风向。随着这些“关键问题”的依次解决,终于“樯橹灰飞烟灭”——联军取得了赤壁之战的胜利。

关键问题,并不是一开始就能够被全部发现,随着人们着手解决,有些问题会逐渐暴露出来。针对筛法这个大问题,目前存在哪些“关键问题”呢?初步估计大致如下:

  1. 采用何种数据结构表示序列?(在仅仅使用C++ Template静态算法的情况下)
  2. 如何生成算法步骤1中的序列?
  3. 如何实现算法步骤3中的筛除功能?

首先是关键问题一,采用6月份文章中提到的递归List,是很自然的一个数据结构,这一结构定义如下:

template<int n, class T>

struct List{

     static const int First = n;

     typedef T Rest;

};

采用这一数据结构后,序列2, 3, 4, ..., N-1, N可以表示如下:

List<2, List<3, List<4, ..., List<N-1, List<N, Empty>>...>>>

其次是关键问题二,如何给定一个自然数N后,生成上面的序列。如果解决这个问题的程序名叫BuildList<N>,那么这个问题有两种情况:

  • 其一是平凡解,如果N=2的话那么BuildList<2>的结果是List<2, Empty>
  • 其二是一般情况,假设N-1时,可以获得BuildList<N-1>的结果,那么当给定自然数N时,如何由N-1的结果获得新的结果呢?答案是通过把数字N增加到Build<N-1>的结果的尾部。

通过分析,以上算法BuildList<N>实现如下:

template<int n> struct BuildList{

     typedef typename Append<

          typename BuildList<n-1>::Result, n>::Result Result;

};

template<> struct BuildList<2>{

     typedef List<2, Empty> Result;

};

在解决关键问题二的过程中,产生了新的关键问题,如何实现上面的Append算法,从而把一个数字添加到一个序列的尾部?这一问题的难点在于C++Template静态推导在编译期,不能定义任何“编译期变量”,也就是说,任何编译期的序列是不可变(immutable)的。所以Append必须生成一个新的序列并将其作为结果返回[5]。对于Append的实现,同样考虑两种情况:

  • 其一是简单情况的平凡解,把一个数字插入一个空序列中,结果是List<n, Empty>
  • 其二是普通情况,把数字n插入到List<First, Rest>,需要先把数字n插入到Rest,然后在把结果组合到一起。

通过上述分析Append<NList, n>的实现如下:

template<class NList, int n> struct Append{

     typedef List<NList::First,

          typename Append<typename NList::Rest, n>::Result> Result;

};

template<int n> struct Append<Empty, n>{

     typedef List<n, Empty> Result;

};

为了验证这两个关键问题的解是否正确,还需要一个把结果打印出来的程序,这个程序和6月份文章中的Print一样:

template<class NList> struct Print{

     static void print(){

          std::cout<<n<<", ";

          Print<T>::print();

     }

};

template<> struct Print<Empty>{

     static void print(){ std::cout<<"\n"; }

};

首先验证Append的正确性:

int main(int argc, char* argv[]){

     Print<

Append<List<2,<List<3,List<4,Empty>>>>, 5>::Result

>::print();

}

程序输出: 2, 3, 4, 5,

然后再测试一下BuildList的正确性,测试语句为:

Print< BuildList<10>::Result >::print();

程序输出:2, 3, 4, 5, 6, 7, 8, 9, 10,

最后要解决第三个关键问题,从一个序列中筛掉某个数p的所有整数倍数字。解决这个问题还是要考虑几种情况:

  • 首先是简单情况的平凡解,如果序列为空,那么结果仍然是空序列;
  • 如果序列不为空,那么首先要判断,序列的第一个元素是否是p的整数倍,
    • 如果是:则返回对序列的剩余部分进行筛除的结果;
    • 反之,把序列的第一个元素,和对剩余部分筛除的结果合并成最终结果。

所以这个从序列中筛除p的倍数的算法可以实现如下:

template<class NList, int p> struct SieveList{

     template<bool x> struct If;

     template<> struct If<true>{

          typedef typename

SieveList<typename NList::Rest, p>::Result Result;

     };

     template<> struct If<false>{

          typedef List< NList::First,

              typename SieveList<typename NList::Rest, p>::Result

> Result;

     };

     typedef typename If< (NList::First % p) ==0 >::Result Result;

};

template<int p> struct SieveList<Empty, p>{

     typedef Empty Result;

};

为了检验SieveList的正确性,可以使用如下测试语句:

Print<

SieveList<

          typename BuildList<10>::Result, 2>::Result

>::print();

程序将输出:3, 5, 7, 9,

通过对筛法算法中的三个关键问题的求解,目前已经不存在任何难点可以阻止最终实现Eratosthenes素数筛法了。所要做的,就是把前面的这些成果综合起来:

template<int N> struct Sieve{

     template<class NList> struct SieveAll{

          typedef List<

              NList::First,

              typename SieveAll<

                   typename SieveList<

typename NList::Rest, NList::First>::Result

              >::Result

          > Result;

     };

     template<> struct SieveAll<Empty>{

          typedef Empty Result;

     };

     typedef typename SieveAll<

          typename BuildList<N>::Result >::Result Result;

};

最后可以通过测试验证素数筛法的正确性,下面的测试语句:

Print< Sieve<100>::Result >::print();

会输出100以内的素数,程序运行结果为:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,

上面的筛法还有很多可改进之处,其一是算法终止条件,埃拉托斯特尼发现,如果待筛除序列中的第一个素数的平方大于序列中的最大值,就可以终止算法。(为什么?读者可以尝试自己证明)例如N=20的情况下,当算法筛到第3个素数5的时候,5的平方为25已经超过20,这时可停止算法,而把所剩的序列7, 11, 13, 17, 19直接添加到已经找出的素数2, 3, 5的后面作为最终结果。读者可以自行尝试改进,提高筛法算法的效率。

二叉树和排序

 

6月份的文章里,最后以一个插入排序作为结尾。排序是算法中最典型的一类问题,也是显示计算机的特点的一类问题。在任何计算机算法课程中,都会先后给出几种著名的排序算法。二叉排序是众多排序算法中很有趣的一个,随着排序二叉的生成过程,整个排序任务也得到了完成。

下图是两个简单的排序二叉树例子:

序列:3, 8, 1

排序二叉树:

3

/\

/  \

1   8

 -------->

然后,按照上图中箭头的方向,从左到右依次读出树中的数字,就是排序的结果:1, 3, 8

序列:7, 14, 9, 11, 5, 17

排序二叉

7

/\

/  \

5       14

        /\

        /  \

         9     17

  \

    \

  11

------------->

同样,按照上图箭头的方向,从左到右依次读数的结果为:5, 7, 9, 11, 14, 17

观察这些例子,可以验证排序二叉树的定义。排序二叉树的任何一个节点是:

  • 空节点或者,
  • 左子节点,数值,右子节点的组合,
    • 其中左子节点,右子节点分别是一个排序二叉树;
    • 所有左子节点二叉树中的数值<本节点的数值<所有右子节点二叉树中的数值。

根据这个定义,首先可以确定的是二叉树的数据结构,其实现如下:

template<class T, int n, class U> struct Tree{

     typedef T Left;

     static const int value = n;

     typedef U Right;

};

整个排序过程,就是建立二叉树的过程,因此可以大致写出这个算法的思路:

  • 首先是简单情况平凡解,如果待排序序列为空,则返回一个空二叉树。
  • 普通情况下:
    • 从序列中取出第1个元素;
    • 然后将序列中剩余的元素建立成一排序二叉树;
    • 最后,将第1个元素插入到此二叉树中。

这个算法叙述非常简单,但是其引入了一个新的关键问题——“插入”。在解决“插入”这个关键问题前,算法可实现如下:

//算法定义

template<class NList> struct BuildSortTree;

//平凡解

template<> struct BuildSortTree<Empty>{

     typedef Empty Result;

};

//普通情况

template<class NList> struct BuildSortTree{

     typedef typename InsertToTree<

          NList::First,

          typename BuildSortTree<typename NList::Rest>::Result

     >::Result Result;

};

红色粗体表示引入的新“关键问题”,也就是将一个数值插入到某排序二叉树的算法。根据排序二叉树定义中的最后一点,可以描述如下:

  • 简单情况平凡解:若待插入二叉树为空,则返回形式为{空,数值,空}的二叉树;
  • 在普通情况下:
    • 若待插入元素小于根节点数值,则将其插入到左子树中;
    • 反之,将此元素插入到右子树中。

根据这个叙述,此插入算法可以实现如下:

//定义

template<int n, class NTree> struct InsertToTree;

//平凡解

template<int n> struct InsertToTree<n, Empty>{

     typedef Tree<Empty, n, Empty> Result;

};

//普通情况

template<int n, class NTree> struct InsertToTree{

     template<bool x> struct If;

     template<> struct If<true>{

          typedef Tree<

              typename InsertToTree<n, typename NTree::Left>::Result,

              NTree::value,

              typename NTree::Right> Result;

     };

     template<> struct If<false>{

          typedef Tree<

              typename NTree::Left,

              NTree::value,

              typename InsertToTree<n, typename NTree::Right>::Result

              > Result;

     };

     typedef typename If< (n<NTree::value) >::Result Result;

};

为了验证算法的正确性,还需要一个能够打印出二叉树的程序,该程序从左到右依次扫描整棵树,凡节点为空则跳过,否则打印出节点的数值。其实现如下:

template<class NTree> struct PrintTree{

     static void print(){

          PrintTree<typename NTree::Left>::print();

          std::cout<<NTree::value<<", ";

          PrintTree<typename NTree::Right>::print();

     }

};

template<> struct PrintTree<Empty>{

     static void print(){}

};

写在main()函数中的测试代码为:

typedef List<7, List<14, List<9,

List<11, List<5, List<17, Empty>>>>>> TestList;

PrintTree< BuildSortTree<TestList>::Result >::print();

程序输出排好的序列:5, 7, 9, 11, 14, 17

快速排序

快速排序是排序算法中很著名的一种,STL中的排序算法缺省使用快速排序算法[6]。快速排序算法是由霍尔(C.A.R.Hoare)提出的。其思路是采用分而治之的策略进行排序。如果用语言描述快速排序,会发现它非常的朴素:

  • 首先是简单情况的平凡解,若待排序序列为空,则算法输出也为空
  • 针对一般情况,算法描述为:

1.  从待排序序列中任取一个元素作为基准(pivot)

2.  将所有小于此基准的元素找出,并对其进行快速排序,结果为A

3.  将所有大于此基准的元素找出,并对其进行快速排序,结果为B

4.  最终结果为(A, pivot, B)

针对一般情况的描述中,其中第23步为递归调用。现在按照算法的描述给出初步实现,并找出新引入的“关键问题”。为了简化普通情况中的第一步,可以选择待排序序列的第一个元素作为基准:

template<class NList> struct QuickSort{

     typedef typename Join<

          typename Append<

              typename QuickSort<

                   typename Smaller<NList, NList::First>::Result

               >::Result,

              NList::First

          >::Result,

          typename Bigger<NList, NList::First>::Result

     >::Result Result;

};

template<> struct QuickSort<Empty>{

     typedef Empty Result;

};

新引入的“关键问题”用红色粗体字标出。其中Smaller找出某序列中所有比指定数字小的所有元素,而Bigger会找出某序列中所有比指定数字大的所有元素。Join会将两个序列合并成一个序列。BiggerSmaller的设计非常接近,例如Smaller可以描述如下:

  • 简单情况的平凡解,若待筛选序列为空,则结果为空
  • 普通情况,也就是待筛选序列不为空的情况

1.  若序列中第一个元素比指定数字小,则留下此元素,并对剩余元素进行筛选;

2.  反之,跳过此元素,直接对剩余元素进行筛选

上述算法描述可以实现为:

template<class NList, int pivot> struct Smaller{

     template<bool x> struct If;

     template<> struct If<true>{

          typedef List<NList::First,

              typename Smaller<typename NList::Rest, pivot>::Result

          > Result;

     };

     template<> struct If<false>{

          typedef typename

              Smaller<typename NList::Rest, pivot>::Result Result;

     };

     typedef typename

          If< (NList::First < pivot) >::Result Result;

};

template<int pivot> struct Smaller< Empty, pivot>{

     typedef Empty Result;

};

实现Bigger算法时会发现,只要把上面代码中,红色的小于号换成大于号,就实现了Bigger。这说明SmallerBigger之间存在相似性,需要做进一步的抽象[7]Andrei[5]中给出了这种抽象的思路——通过提取出公共的PolicySmallerBigger可以通过一个二元比较运算加以区别,一个是小于运算,一个是大于运算。并且这种抽象有C++语言级别的支持,通过template template parameter可以对二元运算符进行概括。下面的代码将SmallerBigger抽象为Filter

template<

     template<int, int> class Compare,

     class NList,

     int pivot

> struct Filter{

     template<bool x> struct If;

     template<> struct If<true>{

          typedef List<NList::First,

              typename Filter<

Compare, typename NList::Rest, pivot>::Result

          > Result;

     };

     template<> struct If<false>{

          typedef typename

              Filter<

Compare, typename NList::Rest, pivot>::Result Result;

     };

     typedef typename

          If< Compare<NList::First, pivot>::value >::Result Result;

};

template<template<int, int> class Compare, int pivot>

struct Filter<Compare, Empty, pivot>{

     typedef Empty Result;

};

由于“<”和“>”两个运算符,在C++中属于基本运算符,无法纳入template<int, int> class的定义,所以需要略作封装,使之符合。

template<int x, int y> struct Less{

     static const bool value=(x<y);

};

template<int x, int y> struct Greater{

     static const bool value=(x>y);

};

通过Filter的抽象,SmallerBigger可分别表示为Filter<Less, ...>Filter<Greater, ...>

最后尚有一个“关键问题”,就是要设计并实现对两个序列进行合并的算法Join。该算法可以利用以前设计的成果Append。算法描述为:

  • 简单情况的平凡解,若待合并的两个序列中的第二个序列为空,则结果为第一个序列;
  • 普通情况下,也就是第二个序列不为空时:

1.  取出第二个序列中的第一个元素,将其添加到第一个序列的末尾;

2.  合并新的第一个序列和第二个序列中剩下的元素。

此算法描述对应的实现为:

template<class NList1, class NList2> struct Join{

     typedef typename Join<

          typename Append<NList1, NList2::First>::Result,

          typename NList2::Rest>::Result Result;

};

template<class NList1> struct Join<NList1, Empty>{

     typedef NList1 Result;

};

通过以上对关键问题的求解,以及对SmallerBigger的抽象,快速排序算法可以进一步改进并最终实现:

template<class NList> struct QuickSort{

     typedef typename Join<

          typename Append<

              typename QuickSort<

                   typename Filter<Less, NList, NList::First>::Result

              >::Result,

              NList::First

          >::Result,

          typename Filter<Greater, NList, NList::First>::Result

     >::Result Result;

};

template<> struct QuickSort<Empty>{

     typedef Empty Result;

};

为了验证快速排序算法的正确性,可以在主程序的main()函数中添加如下测试语句:

Print< QuickSort<TestList>::Result >::print();

程序会输出排好的序列:5, 7, 9, 11, 14, 17

在快速排序算 法中,出现了筛法和二叉树排序中未曾有的内容——对“关键问题”的抽象,在解决某一问题时,会着重解决一些关键问题,这些关键问题有时并不独立,而是有一 定程度的相似性。对这些相似性加以归纳和抽象,能够极大地简化问题,节省时间,并降低耦合度,从而降低出现错误的可能。有些文献称这种抽象为控制点[4]

结尾

本文虽然力图描述这些算法,并且花费相当的篇幅叙述解决问题的思路,但万万不敢妄言能够“授人与渔”了。其一是这些算法都是前人努力的成果,要感谢从埃拉托斯特尼霍尔这些学者。本文只不过是将这些成果拿来做一个浅显的介绍。其二是C++Template编译期编程,也是有大量的资料得以介绍[8]。因此本文充其量也就是“授人与鱼”的程度。

参考书目:

[1] Mark J. Guzdial, Mark Guzdial. Squeak: Object-Oriented Design with Multimedia Applications. Prentice Hall, December 20, 2000.

[2] Eratosthenes. Wikipedia. http://en.wikipedia.org/wiki/Eratosthenes

[3] Sieve of Eratosthenes. Wikipedia. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[4] Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi. How to Design Programs, An Introduction to Computing and Programming. The MIT Press, 2001

[5] Andrei Alexandrescu, Modern C++ Design: Generic Programming and Design Pattern Applied. Addison Wesley, Feb. 2001

[6] Nicolai M. Josuttis. C++ Standard Library, The: A Tutorial and Reference. Addison Wesley 1st Edition August 06, 1999

[7] Robot C. Martin, Agile software development: principles, patterns, and practice. Printice Hall. 2002.

[8] David Abrahams, Aleksey Gurtovoy. C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond. Addison Wesley Professional. December 10, 2004

Scheme 代码参考

改进的筛法代码

(define (seive N)

      (local(

             (define series (rest (rest (build-list (add1 N)

(lambda (x) x)))))

             (define (seive-prime alon p)

               (cond

                 [(empty? alon) empty]

                 [(= 0 (remainder (first alon) p))

(seive-prime (rest alon) p)]

                 [else (cons(first alon)

(seive-prime (rest alon) p))]))

             (define (seive-all alon N)

               (cond

                 [(> (* (first alon) (first alon)) N) alon]

                 [else (cons (first alon)

                    (seive-all

  (seive-prime (rest alon) (first alon))))])))

      (seive-all series N)))

排序二叉树代码

(define-struct num-tree (left n right))

(define (insert-to-tree n atree)

  (cond

    [(empty? atree) (make-num-tree empty n empty)]

    [(< n (num-tree-n atree))

      (make-num-tree

        (insert-to-tree n (num-tree-left atree))

        (num-tree-n atree)

        (num-tree-right atree) )]

    [else

      (make-num-tree

        (num-tree-left atree)

        (num-tree-n atree)

        (insert-to-tree n (num-tree-right atree)) )]))

 

(define (BST alon)

  (cond

    [(empty? alon) empty]

[else (insert-to-tree (first alon) (BST (rest alon)) )]))

快速排序代码

(define (quick-sort alon)

  (local((define (filter-list cmp alon pivot)

          (cond

            [(empty? alon) empty]

            [(cmp (first alon) pivot)

               (cons (first alon) (filter-list cmp (rest alon) pivot))]

            [else (filter-list cmp (rest alon) pivot)]))

        (define (sort alon)

          (cond

            [(empty? alon) empty]

            [else (append (quick-sort

(filter-list < alon (first alon)))

                         (list (first alon))

                         (quick-sort

(filter-list > alon (first alon))))])))

    (sort alon)))


[English][上一篇][下一篇][目录][主页][联系我们: liuxinyu95@gmail.com]

ċ
fp.h
(7k)
Xinyu LIU,
Apr 8, 2012, 10:47 PM
Comments