David's profileprowyh's spaceBlogLists Tools Help

Blog


    June 28

    Accelerated C++ - part three

    “I find using C++ more enjoyable than ever.”

    Bjarne Stroustrup在《The C++ Programming Language》(Special Edition)的前言中的第一句话,透露着欣喜与自豪!

    是啊,“吾家有女已长成” !“By now, C++ has fulfilled most of the hopes I originally had for it, and also succeeded at task I hadn’t even dreamt of.”经过20多年的努力,Bjarne Stroustrup的“女儿”已长大成人!这些话,还有谁比Bjarne Stroustrup更有资格说呢?

    下面继续上篇留下的一个问题。

    Andrew Koenig特意区分了standard headers和header files:

    #include <iostream>
    #include <string>
    #include <vector>
    #include “grade.h”
    #include “median.h”

    上面的iostream、string、vector为系统(实现)提供的standard headers(或system headers),而grade.h和median.h为用户提供的header files。

    之所以称为standard headers而不再叫header files,是因为这些头(headers)不再一定是以头文件的形式存在了(比如,这些标准头可能是以某种形式组合在一起而存在于一个(库)文件中,从而不再以单独的头文件形式存在)。与标准头不同,用户提供的头都是以标准头文件的形式(.h, .hpp, .hxx)存在的,所以仍然称为header files。

    下面看一个非常有趣的问题。

    for (int r = 0; r != rows; ++r) {
     // write a row
    }
    for (int r = 1; r <= rows; ++r) {
     // write a row
    }

    这两个for语句有什么区别?乍一看好像没什么区别,都是循环一次就write a row,总共write rows row!可Andrew说,区别大了!

    区别之一:从0开始计数鼓励我们用非对称范围来表达区间(多么数学化的语言!)。第一个for的计数区间是[0, rows),第二个for的计数区间是[1, rows]。

    区间的一个重要属性:[m, n)有m – n个元素,而[m, n]有m – n + 1个元素。从这点上来说,非对称区间比对称区间更容易计数。我们往往为计算m和n之间有多少个元素而是否需要加1举棋不定,要掰着手指算半天。用非对称区间就很容易解决问题。这是非对称区间的好处之一。

    [m, n),当m = n时,就成为[n, n),这表示一个空的区间(范围,集合)。如果用对称区间来表示,则[n,n]表示有一个元素的区间,而要表示空区间,则必须写成[n, n-1]!Andrew说,“The possibility that the end of a range could be ever less than the beginning can cause no end of trouble in designing programs.”这是非对称区间的好处之二。

    区别之二:从0开始计数更容易表示循环不变式(loop invariants)。

    所谓循环不变式,是指表示程序行为的一种断言(assertion),这种断言在每次测试循环条件时都为真。看下面的程序片段:

    // invariant: we have written r rows so far
    int r = 0; // ① setting r to 0 makes the invariant true
    while (r != rows) {
     // ② we can assume that the invariant is true here
     write(); // ③ write a row of output makes the invariant false
     
     ++r;  // ④ incrementing r makes the invariant true again
    }
    // ⑤ we can conclude that the invariant is true here

    该程序片段的循环不变式是:至此已输出r行。
     
    在①处,r赋值为0,而此时还没有任何输出,所以此循环不变式为真;在进入while语句的②处,不变式仍然为真;③处实际执行输出,此时循环不变式不再为真,但在④处对r进行加1操作之后,循环不变式又变为真。进入下一次循环过程,结果不变式仍然为真。直到while条件变为假从而退出循环,到达⑤处,此时循环不变式仍然为真!

    循环不变式是循环语句的一个重要属性。是理解循环程序行为的一个重要工具!

    第一个for语句与上面的while循环的程序片段等价,所以其循环不变式也是“至此已输出r行”。而第二个for语句的循环不变式是什么呢?“至此已输出r - 1行”!

    区别之三:从0开始计数,我们可以用 != 比较符,而不用 <= 比较符。

    以前for语句的典型写法是:

    for (int r = 0; r < rows; r++) {
     // write a row
    }

    这是C的经典写法。标准C++已将此写法改为:

    for (int r = 0; r != rows; ++r) {
     // write a row
    }

    对比一下,有两点变化:一是比较符从 < 变为 !=,二是 ++ 操作符从后缀变为前缀。

    这两种写法都是正确的!但标准C++的写法使得程序员能够更准确地表达自己的意图(intention):r != rows说明for循环在r等于rows时结束!++r使得C++编译器在进行aggressive optimization时仍然能够保证语义的正确性!

    无论r <= rows,还是r < rows,都不如r != rows在表达程序语义上的精确性。

    还没有看到有谁像Andrew这样仔细地探讨起始计数从0还是1开始的问题。大家就是大家!

    P.S.

    [m, n)称为半开区间(half-open range),表示m, …, n-1,其中n不包含在区间内,是紧接着区间最后一个元素(n-1)之后的元素,被称为off-the-end value。

    半开区间的性质:(《Generic Programming and the STL》pp.12)

      空区间[n, n)是有效区间;
      如果[m, n)有效且非空,则[m+1, n)也有效;
      如果[m, n)是一个有效区间,且m ≤ k ≤ n,则[m, k)和[k, n)均为有效区间;
      如果[m, k)和[k, n)均为有效区间,则[m, n)亦为有效区间。
     
    June 25

    Accelerated C++ - part two

    Dennis M. Ritchie在1972年设计并实现了C,并与Ken Thompson一起用C重写了UNIX。C的广为传布与接受始自Brian W. Kernighan & Dennis M. Ritchie于1978年出版的《The C Programming Language》。C语言于1983年提交ANSI进行标准化,ANSI于1988年完成了C的标准化,形成了“ANSI C”,而在此之前的C被尊称为“K&R C”。ANSI C在K&R的《The C Programming Language》第二版(出版于1988)中得到了完整的表述。

    Bjarne Stroustrup设计并于1983年完成了C++的第一个实现,《The C++ Programming Language》第一版出版于1986年。随后,于1989年开始了C++的标准化工作,并于1998年最终完成(C++的标准化耗时近10年!可见其难度之大!)。Bjarne Stroustrup的《The C++ Programming Language》特别版(Special Edition)出版于2000年,是根据标准C++写成的最新权威版本。《Accelerated C++》也是出版于2000年,亦是根据标准C++而写就。

    从“血缘”关系上说,C++直接来自于C(最初C++名为“C with Classes”),并从Simula 67、Algol 68、Ada等汲取了“营养”(《The Design and Evolution of C++》pp.6)。

    C++的标准化在C++的发展中至关重要。标准化之前,很多人都是以C的方式使用C++。此时的C++(包括C),由于格式自由,以及指针的不受限制的使用,就像西部牛崽(cowboy)一样,无所不能却又桀骜不驯!(The C language is like a carving knife: simple, sharp, and extremely useful in skilled hands. Like any sharp tool, C can injure people who don’t know how to handle it. ——Andrew Koenig《C Traps and Pitfalls》)

    标准化以后的C++,由于Template、Generics等技术的成熟,特别是STL的一部分被标准化而纳入The C++ Standard Library,使得C++逐渐变得优雅。现代C++已脱离西部牛崽的蛮气,变身而为一位受过良好教育,有着良好教养,具有优雅气质的知性女人!这是我读《Accelerated C++》一书最大的体会。(书中自有颜如玉?huh........)

    两个小例子:
    1、 splitting a string to separated words(pp.103)
    bool space(char c)
    {
        return isspace(c);
    }
    bool not_space(char c)
    {
        return !isspace(c);
    }
    vector<string> split(const string& str)
    {
        typedef string::const_iterator iter;
        vector<string> ret;
        iter i = str.begin();
        while (i != str.end()) {
            // ignore leading blanks
            i = find_if(i, str.end(), not_space);
            // find end of next word
            iter j = find_if(i, str.end(), space);
            // copy the characters in [i,  j)
            if (i != str.end())
                ret.push_back(string(i, j));
            i = j;
        }
        return ret;
    }

    2、 counting words of input(pp.124,稍有改动)
    #include <iostream>
    #include <string>
    #include <vector>
    #include <map>
    int main()
    {
        std::string s;
        std::map<std::string, int> counters; // store each word and an associated counter
     
        // read the input, keeping track of each word and how often we see it
        while (std::cin >> s)
            ++counters[s];
     
        // write the words and associated counts
        for (std::map<std::string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it) 
        {
            std::cout << it->first << “\t” << it->second << std::endl;
        }

        return 0;
    }

    这两个简单的例子已足以体现现代C++的优雅,想想我们以前用C写出来的同样程序是个什么样子!

    现在,C++又进入了新一轮的标准化过程,新的C++被称为C++0x,意为2010年之前完成标准化工作。2010年之后的C++又会是个什么样子呢?……
     
    上面的第二个例子有两个问题需要讨论,下面先看第一个,另外一个留待下回再说。

    随着处理问题的规模越来越大,现代程序都是以模块(module, library, component)方式对问题进行分解,然后组装为可运行的程序。这就带来一个问题:名字冲突(name collision)!不同模块可能会用同样的名字指称不同的事物!

    为了解决这个问题,现代程序设计中引入了“名字空间(namespace)”的概念。

    C#支持namespace,XML支持namespace,C++也支持namespace。(从某种意义上说,支持名字空间概念是现代程序设计区别于传统程序设计的特征之一!)

    C++的标准库具有std名字空间,所以,所有标准库中的名字都处于std名字空间中,所以仅仅写

        vector<string> vs;

    是不够的,完整的写法应该是:

        std::vector<std::string> vs;

    就像上面的例子所表示的一样(qualify the identifier directly ——《The C++ Standard Library》)。

    但如果程序稍微大一点的话,这种写法就太tedious了!C++支持一种简化的写法(using directive):

        using namespace std;

    这种写法是可以的,但不推荐,因为对于程序中哪些名字来自于标准库,这种写法没有提供任何帮助(hint)。

    还有一种写法就是用using declaration写出程序中用到的所有名字:

    using std::cin;
    using std::cout;
    using std::endl;
    using std::string;
    using std::vector;
    using std::map;
    int main()
    {
        string s;
        map<string, int> counters; // store each word and an associated counter
     
        // read the input, keeping track of each word and how often we see it
        while (cin >> s)
            ++counters[s];
     
        // write the words and associated counts
        for (map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it) {
            cout << it->first << “\t” << it->second << endl;
        }

        return 0;
    }

    这种写法避免了qualify the identifier directly的verbose and tedious,也不像using directive方式那样简单粗暴,using declaration是一种“执两端而取其中”的中庸方式。
     
    June 21

    Accelerated C++ - part one

    已经十几年没看过C++的书了,为了实现做Mentor的愿望,近来又捧起了C++恶补。

    看英文的技术著作有两难,一是语言难,英文作者在写作时并没有贯彻Internalization的观念,许多GRE级别的词汇随手捻来,让我们这些只有TOEFL词汇量的人看得实在头大!二也是语言难,C++是所有Programming Languages中最难的,庞大,复杂,充满了各种各样的pitfalls(想想pointers)!掌握C++,实非一朝一夕之功!

    伟人说:红军不怕远征难!俺说:真正的程序员也不怕C++!!伟人还说:无限风光在险峰!俺还说:不征服C++,则不足以览众山之小!!!

    征服C++的登山之旅,从此开始。

    登山之旅,有攀登的艰难,有征服的喜悦,有美景的陶醉,有回望的感慨,有避开陷阱的小心翼翼,有针尖上跳舞的头晕目眩,有脚底踏实的窃喜,有登高望远的豁然……

    为了不虚此行,特记录下行程中的点滴心得,一则免得遗忘(实在没有办法,人的大脑只是一个遵循LRU算法的Cache,无法做到Persistence)。再则也是为将来的Mentor做些资料准备。

    本文乃系列读书笔记之第一篇。让我们先从Andrew Koenig先生的《Accelerated C++》开始罢。

    《Accelerated C++》由Andrew Koenig和Barbara E. Moo夫妇写成。二人均在AT&T(Bell Labs)供职(现已退休),Barbara开发过Unix上的Fortran 77编译器(这是一个很好用的Fortran编译器),后来一直负责C++编译器。Andrew是ISO/ANSI C++委员会的成员,翻开任何一本C++的顶级著作,在作者的致谢名单中几乎都能看到Andrew Koenig的大名。可喜的是,现在终于读到了Andrew自己写的著作。

    Accelerated C++,顾名思义,就是“向C++加速前进”。为了达此目的,Andrew和Barbara采取了不同于以往的书写方式,不是“学究式”step-by-step地讲解C++的语言特征(我们读过不少这样的书,以概念的逻辑演进为序,先词法,再句法……,仅printf()的格式控制符就翻来覆去讲上大半天!读这样的书,很容易导致脑部缺氧),而是以其副标题所揭示的那样,Practical Programming by Example!换言之,就是Learn C++ Programming by Example。就像作者在前言中所说,这是a new approach to C++ programming。作者开宗明义:We assume that you want to learn quickly how to write useful C++ programs. Therefore, we start by explaining the most useful parts of C++. ……Our approach is unusual in another way: We concentrate on solving problems, rather than on exploring language and library features.

    所以,Bjarne Stroustrup赞之曰:Francis Glassborow的《You Can Do It》和Koenig & Moo的《Accelerated C++》是打破旧式而令人厌烦的教育方式的例子。

    The first example(类似于第一推动,huh!):

    // a small C++ program
    #include <iostream>
    int main()
    {
        std::cout << “Hello, world!” << std::endl;
    }

    自从Brian W. Kernighan & Dennis M. Ritchie在《The C Programming Language》中以Hello, world作为第一个C语言程序例子以来,Hello, world已经成为程序语言入门的Classic Example!

    Andrew & Barbara也不例外,仍然以这个经典的例子开始其C++加速!

    例子随小,却“五脏俱全”。这个最小的C++程序包含了许多概念(诸如comment, standard library, standard header, #include directive, statement, expression, type, scope, namespace, output operator, standard output stream, etc),作者用了一章的篇幅(Chapter 0 Getting Started)讲述这个例子。

    C的等价物:
    /* a small C program */
    #include <stdio.h>
    main()
    {
        printf(“Hello, world.\n”);
    }

    C#的等价物:
    // a small C# program
    using System;
    public class CSharpProgram
    {
        public static void Main()
        {
            Console.Write(“Hello, world.\n”);
        }
    }

    附:

    Andrew Koenig

    Barbara E. Moo

    June 20

    江山代有才人出(二)

    Russia-based Quintura Search Engine为我们带来了另外的惊喜: Quintura号称“可视化的搜索引擎(visual search engine)”,试图以人们思考概念的自然方式进行搜索。
     
    Google.com是基于关键词(keyword)的搜索,没有表达概念相关性的手段。实际上,人们进行搜索的过程就是一个不断求精(refinement)的过程,而此求精过程就是通过概念的相关性来完成的。
     
    Ask.com通过Narrow your searches和Expand your searches来体现这个过程,Quintura.com则是通过“概念云图(concept cloud)”来实现。下图是搜索“search engine”的结果。
     
     
    Quintura.com的页面分为三个部分:上部为功能条,左部为云图区,右部为结果列表区。结果列表区为嵌入的IFrame,其余就是一个平板的页面(flat page),通过嵌入的DIV而区分为若干个功能区。应用了Ajax技术,使得整个页面非常具有动态性。
     
     
    由此图可以看出,search engine与很多概念相关,如submission, watch, plugins, web, 等等。其中:
    Query words - words from the search box. The search engine looks for these words and highlights them in your search results.
    Query context - words close to your query words by meaning. The context words let you refine your query.
    Selected word - a word you are pointing to. If the Autorefinement check box is selected in your Settings, relevant links are downloaded (as if you add this word to your search query).
    Selected word context - words close to the selected word by meaning. The context words let you change the direction of searching.
    Favorite icon - an icon to the left of a word referring to a website found as most relevant for the specific word.

    Quintura.com声称,概念云图由后台非常复杂的神经网络和服务器集群做支撑!所以,搜索引擎是非常tech-intensive的!
    但IT,特别是Internet(Web),就是这样不断由技术推动着,“从胜利走向胜利”……
    June 19

    江山代有才人出

    Internet信息的海量特征催生了搜索引擎,使得人们可以快速地搜索信息。
     
    从信息搜索的角度来说,Google.com可以说达到了目前的最高水平,以至甚至认为Google.com是不可超越的(连Microsoft也自叹弗如)!
     
    But really? No!
     
    Ask.com is a better one!
     
     
    Ask.com的首页不再是Google.com简单的文本页面,而代之以华丽的视觉感受!然而,这并不是Ask.com最重要的。
     
     
    这是以搜索pancreas一词而显示的Ask.com页面,整个页面分为左、中、右三栏结构。中栏(A)为页面主体,显示搜索结果。右栏由多个组件组成,首先是图片(B),该部分显示与搜索关键词相关的图片,此图中显示的是与pancreas(胰腺)相关的图片,使人文图对照,一目了然。下面的组件(C)是pancreas的百科全书条目,再下面的组件D是pancreas一词的词典定义(下面未显示部分还有相关的blog)。通过这些内容,可以对所搜索的词(pancreas)有更准确的理解。左栏的E是精确搜索(narrow your search),F是扩展搜索(expand you search),通过这两部分,可以对搜索进行窄化(内涵搜索)与泛化(外延搜索)。
     
    通过简单的介绍可以看出,Ask.com已经不再是简单的search,而是对search加入了data mining技术!Ask.com所有这些组件作为一个整体,大大提高了结果信息的相关性!
     
    当然,Ask.com不仅仅是search:
     
     
    Ask.com也在努力创造自己的社区!
     
    Ask.com和Answers.com在某种意义上体现了知识搜索的雏形!
     
    当然,Ask.com也并非完美,访问速度比较慢,而且有横向滚动条,其社区的页面还处于Yahoo.com早期的水平,对图片的编辑也不如flickr.com方便!Anyway, I love Ask.com!
    June 12

    上帝啊,我的flickr!

    有比这更加无耻的么?
    有比这更加流氓的么?
    有比这更加残酷的么?
    有比这更加疯狂的么?
     
    wikipedia.org被封掉了!
    technorati.com被封掉了!
    google.com被过滤了!
    现在,flickr.com也被封了!!!
     
    我的space到处是难看的“疤痕”……
    可我的图片并非关乎“政治”!
    “宁可错杀一千,也不放过一个!”
    我听到黑暗处传来咬牙切齿的声音……
     
    可是,谁给你的权利?
    可是,我的小屋真的是“风能进,雨能进,而国王不能进”么?
    “我们这是为了人民!”
    黑暗处又响起了声音……
     
    让我拿什么来爱你,我的上帝?
    眼中满是邪恶……
    到处是阉割与被阉割者……
    oh, my!!!
     
    注记:
    2007.6.14,flickr.com上被封的图片又羞羞答答地、琵琶遮面地、不太情愿地、掩耳盗铃地、此地无银地放开了……
    “我举起灰黑的手,装作喝干一杯酒”,算作庆祝罢……
     
    June 01

    厦门的“儿童节”

     
    美丽的厦门如果不再美丽…………
    见过的丑恶太多了,留住这美丽罢,Amen!
     
    注一:
    所引照片已被删除,留下了这难看的“疤痕”……为了不使space太难看,故删去这些“疤痕”,但为了保留本文的真实性,仍然留下一块……#$%@^&*+_=-)(*&……………………
     
    注二:
    民众的记忆远比想象中顽固,这一点本期有两本精彩的新书分别从理论和实践予以了证明。十几年前的事先不说,近的像厦门的“六一万人大散步”,即使官方半官方媒体同时失声,对反对PX关注家园的厦门人民来说,这件事已经写入了他们的集体记忆。并且这个环境公共事件或多或少地恢复了知识者的名誉:中科院的院士们最早联名提交了“关于厦门海沧PX项目迁址建议的议案”;公共知识分子也发出了他们可敬的声音:“作为社会里一个微小的个体,当看到强大势力吃相难看地侵犯自己权利之时——你不仅没有知情权、决定权,甚至呼吸的空气、喝的水,孩子的健康,精子的质量都被人拿去卖了钱——觉得自己乏力是肯定的,但越是这样,越是要留下反对的证据,不然将来人家很潇洒地一摊手:是呀,这件事情当初决策是错的;不过,我们没有听到任何反对的声音”。
    ——【季风书讯】NO.47 2007.6
     
    注三:
    终于找到一张照片……