oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6
大约每隔十年,都会出现一个编程新概念,宣布自己是以往概念的继承者。我们也再一次相信,从今往后软件比以前更可靠,更容易build,或者更有意思(没有人相信它会比以前更小或者更快)。在70年代,有结构编程;在80年代,开始了面向对象编程;从90年代中期,出现了范型编程(generic programming)。范型编程得名于其用模板而使代码重用的高效技术(范型类和范型函数)。

模板类和模板函数都是非常有用的工具。例如sqr()函数可以计算平方数,任何定义了乘法运算的数据类型(数字,矩阵)都适用。标准容器类(如list)都是模板,这样对于每个新类型无需重写了,这正是使用旧版的C++时真正头疼的事情,因此我认为ISO的标准是个伟大的进步。然而,在这个过程中有些东西用得过头了。

例如:标准库中得string 和iostream 都是使用"character traits"类型作为参数。这意味着同一个basic_string<>类可以用于ASCII字符串,也可用于Unicode,甚至用于火星人的三字节字符串(原则虽然如此,但许多版本都只是实现了ASCII字符串,看起来有点滑稽)。标准要求这些常用类必须实现成模板形式,而这些类几乎涉及到所有C++应用。

但是这对性能和调试会带来许多麻烦。下面几个试验解释了这个问题(本试验使用的编译器为VC++6.0)。编译器同时支持新风格的iostream(使用模板)和经典风格的iostream, 因此我们能比较他们二者的版本实现。第一个测试程序当然是使用"Hello, Word"了,新风格的编译时间是经典风格的2倍。另一个更正规的例子大约有200行,每行输出10个变量用于计数。这个测试程序最显著的结论是编译速度:新风格版本花了10秒编译完成,而旧版本只使用了1.5秒。10秒时间可并不少,可以完成很多事情。另外,新风格版本的可执行文件的大小为115K,而旧版本只有70K。你的测试数据可能有些出入,但是整体结论是一样的:当使用新版本时,会有更慢的编译速度和更大的可执行文件。这并不是因为微软公司编译器的问题,使用GCC测试也会得到同样的结论。

当然,和过去不一样,可执行文件的大小并不是那么重要,现在,可编程设备种类正快速增长,包括许多信息应用,如遥控、手机、智能冰箱、基于蓝牙技术的咖啡机等等,在这些应用中内存近几年都会是十分宝贵的资源。使用标准iostream 而产生的额外的二进制文件,来源于内联了整个模板类的代码,要是没有code bload工具,你很难优化那些重要的操作。对我来说,编译时间问题更严重一些,因为这样意味着更长的等待,从而失去了开发中非常重要原则:互动原则。

现在我们来考虑调试的问题。标准库中string 类的模板实现非常聪明,但并不适合于调试。你会面临使用超长名字的编译器和调试器的信息:

class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char>>
同样对于非常有用的容器 map < string,string > , 你可以去想象其复杂性。这些名字太长了,以至于产生数十个内部名字被截断的警告。对于初学者来说,std::string 应该设计得尽可能透明,而不应该让他们面临许多语言内置得一些特性。当输出了编译错误信息后,在技术上讲,应该是可以查找到所有的 typedef 。我在 UnderC 项目中就试图这么做。Verity Stob 建议编写一个后置的处理器来翻译这些错误信息,我倒希望这是她这么做只是开个玩笑。如果不使用这么复杂的类型,这个问题就会容易处理的多。我在C++开发上的秘诀就是(我首次坦诚的公开这个秘密): 在稍微大一点的工程中使用一个兼容的string 类来替换std::string 的头文件. 有时我会重新build 这些标准的头文件,用来检测是否我的库还能正常使用,但让其他人为如何提高其性能而努力。

当然,在许多应用中我们都需要这种std::string提供的灵活性,例如,需要同时处理ASCII 和Unicode字符串,或者需要定制自己的allocator 等等。但这并不是普遍需求(通常程序员要么只处理ASCII,要么只处理Unicode ), 看起来对于程序员承担这种范型机制有些不公平。这种机制确实让标准库的设计者觉得很有意思,但增加了应用开发程序员使用的复杂度。这似乎颠倒了这个原则:良好的标准库设计应该隐藏其实现的复杂度,而让用户直接使用。但std::string 对其实现的复杂度隐藏得并不够,导致在用户使用过程中不断的遇到设计中的问题。我们不能要求标准库的用户都是专家。标准坚持要求这种特定的实现方式,和标准库的设计初衷相违背,其初衷是只提供公共的接口和包含一些特定功能的类库。自然,这种范型模板对于那些真正去要他们的人是一直有效的。

这些细节考虑同样应用于标准容器,例如list<>容器,list 有一些额外的默认模板参数,用于定义了默认的allocator。当然自己定义allocator 十分有用,但绝大多数人不需要自己去实现。这些泛化的版本完全可以作为单独的模板提供。我承认这样做会让标准库的设计在技术上变得没有以前有意思,但这些库在设计之初就应该考虑到最终用户。篡改一下C++的颂歌:用户不应该为他们不需要的东西买单。

当我们不需要模板的时候,我们不得不使用模板。除此之外,在C++中用范型编程还会遇到另一个的问题。大多数人都同意,标准的algorithm 十分有用。如果你有一个整型的vector, 你可以直接使用下面的语句来排序:

sort(v.begin(),v.end());
因为int型数据的比较函数时内联的,而且这种范型算法比旧版本的qsort()函数速度还快,也更容易使用,特别是使用用户自定义类型的vector. copy()函数也可以在任何时候高效率地拷贝任何数据。

但有些应用理解起来十分晦涩:

copy_if(v.begin(),v.end(),ostream_iterator<int>(cout) bind2nd(greater<int>(),7));
如果要写得严格一点,每个名字都应该加上std::前缀,这里假定所有变量都是使用全局命名空间,或单独使用命令或用其他方法。用Stroustrup (C++的创始人)的例子更容易说明问题,这个例子把所有的整型数输出到终端:
vector<int>::iterator li;
for (li = v.begin(); li != v.end(); ++li)
if (*li > 7) cout << *li;
Stroustrup 告诉我们如果使用显示的循环是"麻烦而又容易产生错误", 但我看不出使用第一个版本有什么优势。显然,人们能习惯这种方式,人类的适应性很强,作为专业人士,我们也不得不学习这个新概念。但是,这样做并没有减少多少麻烦,而且我们可以证明这样做可读性更差,更不灵活。同时,它还会限制你的设计。例如,假设我们有一个Shape * 的指针list, 我们可以通过下面的调用方式来画出他们自己的形状:
for_each(ls.begin(),ls.end(),
bind2nd(mem_fun(&Shape::draw),canvas));
也可以选择这种方式:
ShapeList::iterator li;
for (li = ls.begin(); li != ls.end(); ++li)
(*li)->draw(canvas);
现在假设我需要修改我的设计,我只想画那些满足某种要求的图形(而且不希望把这些需求包在shape类里面), 那么我只需要在显式的循环中增加一条if条件语句。如果要使用范型概念,我唯一能想到的方式定义一个函数,然后使用for_each()算法。使用设计模式一书中的术语,第一个例子是一个内部迭代器(internal iterator),第二个例子式一个外部跌倒器(external iterator). 作者认为C++ 并不擅长使用内部迭代器,我想我们还是应该考虑语言的局限性。其实问题在于在C++中过度应用范型概念--从而导致不必要的难度。C++ 完全不支持一般的匿名函数(anonymous functions)如LIST, SmallTalk, Ruby等。C++中的匿名函数或许看起来和下面一样,可能某天有人会实现它:
for_each(ls.begin(),ls.end(),
void lambda(Shape *p) { p->draw(canvas); }); 

C++ 是一种不可思议的编程语言,小到手机,大到跨国际网络,都有其应用。它非常灵活,能够支持多种编程风格,但这种灵活同样也是其问题所在。编程的艺术在于为特定的问题选择合适编程风格,就像老师总提醒写作文是要选择好的风格一样。我并不想诋毁 C++ 标准库,这里面包含了许多人的辛勤劳动,并为大家提供了一个公共平台。我对于这个标准的态度是,它和范型编程联系过于紧密,从而变成了在说明什么风格是好的编程风格(例如,算法中明显倾向于不要使用显式循环), 同时它也让程序员们不得不介入一些实现细节(如basic_string<>),这样做让人们更加觉得C++ 是只是内核工程师们的编程语言。


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理