C++博客 :: 首页 ::  :: 联系 ::  :: 管理

置顶随笔

这个blog主要记录程序设计方面的内容,既然是落户C++博客,自然要写C/C++的内容了。此外,我还对动态语言(比如Python,Ruby),函数式编程语言(比如Haskell)感兴趣。最近还在断断续续地学习.NET Framework的知识。此外我还在Donews上有一个blog,写一些和编程无关的杂七杂八的内容。Donews的最大缺点是没法显示代码缩进,至少我不知道。

posted @ 2006-09-11 21:02 chenger| 编辑 收藏

2006年10月12日

今天写代码的时候,发现g++好像不支持模板成员函数的全特化。看代码:

class A
{
public:
    template
<typename T>
    T f(T val);

    template <>
    int
f<int>(int val);
};

我用的是g++ 3.4.2 mingw版本。编译上面这段代码时,错误信息如下:

5: error: invalid explicit specialization before '>' token
5: error: explicit specialization in non-namespace scope `class A'

如果把f的定义放到全局作用域中,就不会出错。而上面这段代码在VC++ 8.0下可以编译通过。运行起来也没有问题。别的编译器我没有试过。

Update:多谢周星星的指点,比较“常规”的写法如下:

class A
{
public:
    template <typename T>
    T f(T val);
};


template
<typename T>
T A::f(T val)
{
    // ...
}

template <>
int
A::f<int>(int val)
{
    //...
}


这种写法就没有任何问题(在g++ 3.4.2和VC++ 8.0下均表现正常)。至于为什么前面的写法导致g++下报错,还不是很清楚。

posted @ 2006-10-12 16:28 chenger 阅读(2377) | 评论 (4)编辑 收藏

2006年9月29日

Ruby中的名字约定

历史:高级程序语言的老祖宗,Fortran,对源程序中的名字,或者叫标识符(identifier)有很严格的规定,譬如首字母代表变量的类型等等。个人认为这是当年编译技术还未成熟时的权宜之计。后来主流的程序设计语言都放松了对名字的限制,像C/C++/Java,只有一点点小小的约束(对所用字符的限制:只能使用英文字母、数字、下划线,必须以下划线或英文字母开头。这也容易理解,完全是为了写词法分析器的方便)。而和Fortran同时代的Lisp,这方面更是大开绿灯,爱怎么定义怎么定义。然而到了现在,似乎有点复古的潮流,有些语言开始对名字设立一些规则,比如Haskell,Erlang,包括Ruby。

言归正传。Ruby中的名字规则主要是根据名字的第一个字母来决定这个名字的使用方式。具体来说,
  • 局部变量,方法名,方法参数:以小写字母或下划线开头,以'_'连接。
    Example:i,note_controller
  • 常量:全部大写,以'_'连接
    Example:A_NUM
  • 类,模块(module):都是开头大写(因为类名是全局变量),其他小写并且直接连接在一起
    Example:ActiveRecord
  • 全局变量:以'$'开头(肯定是跟Perl学的,我觉得不怎么好)
  • 实例变量(instance variable):以'@'开头(同上)
  • 类变量(class variable):以'@@'开头(诡异)
有点Perl的味道,但Perl更加变态,居然要以首字母区分标量、数组和Hash表,这就不太人道了。相比起来,Ruby的设置还是可以接受的,它只不过是把有些约定俗成的规则直接变成了语言规则。每个程序员基本上都会有自己的一套命名规则,比如写C++程序时,类名通常用大写字母开头,宏名则通常由大写字母组成,而下划线开头的(特别是双下划线)往往留给库开发者等等。Ruby的想法可能是:干脆统一了这些命名规则,免得人们为这种风格(Style)问题争论不休。也是挺有道理的。

posted @ 2006-09-29 18:56 chenger 阅读(291) | 评论 (0)编辑 收藏

2006年9月24日

我在自己的电脑上装了ruby,稍微看了点Programming Ruby,感觉Ruby有很多想法都非常有意思,值得学习,比如块,以及彻底的Object Oriented(对于谁比谁更OO,从来都是争吵不断,比如Java比C++更OO,C#比Java又更OO,等等,往往引起论坛上一片腥风血雨。我这个也就是随便说说),迭代器。很多语言特性和Python相差不大,估计脚本语言做到一定程度多少都有些相似的,当然各有各的特点。然后又看了点源代码,终于明白为何Ruby的性能如此被人诟病:构造了AST以后,直接在AST上递归进行eval。而Python,Perl,Lua等都是编译为中间语言再交给虚拟机执行。如果能有一个JIT编译器(像.NET那样)就更牛了。Ruby传说中的2.0版本要引入虚拟机,YARV。不过那2.0遥遥无期,目前最新的stable是1.8.5,2.0据说要到08奥运那会了。

Ruby的源代码还充分体现了拿来主义的精神,能重用的决不自己写:比如Hash表就用了一个通用的Hash表实现,正则表达式则使用了GNU的regex库,random是有名的MT19937(也是日本人写的)。尝试了一下编译,在mingw上执行标准三部曲:./configure,make,make install,一切OK。

posted @ 2006-09-24 14:50 chenger 阅读(310) | 评论 (0)编辑 收藏

2006年9月16日

上次写了一篇关于google面试题的文章。我给的算法跑得很慢,后面张沈鹏同学用python写了一个算法,速度很快(再次感觉python的性能不像想象中那么坏,当然和算法有关),看了一下他的代码,函数count(i)用来计算小于i的1的个数,和我写的calc_ones算法基本相同,只不过count(i)用了递归,看上去更清楚一些。主要的速度差别在little(i)函数上,这个函数避免了很多迭代:

size_t little(size_t i)
{

   
size_t ones = calc_ones(i);
    if(ones == i)
        cout << i <<
"\n";
    if(i < ones)
        if
((ones - i)/9 > 1)
            return
i - (ones - i)/8;
    if
(i > ones)
        return
ones;
    return
i - 1;
}


这是C++版本。主循环也要略微改变一下:

void
solve()
{

    size_t
max = 10000000000;
    for
(size_t i = max;i > 0;i = little(i));
}


可以看到,现在循环从大到小。little函数找到下一个可能满足题目约束的i。在little函数中,首先计算小于i的1的个数ones,如果ones和i相等,就将i输出(这就是题目要求干的事)。如果i小于ones,那么就要在小于i的自然数中找下一个可能满足条件的数。因为搜索的范围不超过10^10,所以一个数中至多含有9个1,按照这种极端情况,也必须将i减少(ones-i)/8才有可能满足条件(这里之所以是8,因为同时i也减少了)。如果i大于ones,考虑一个小于i的数i',可以考虑一下calc_ones(i')的取值,极端情况,[i',i)的范围内的整数没有一个包含1,也就是说当i减少到i'时1的个数没有损失,那么calc_ones(i') = calc_ones(i),如果i'>calc_ones(i),则就有i'>calc_ones(i'),直到i'=calc_ones(i),因此下一个需要查看的数就是calc_ones(i)。其实上面这一段讨论可以用一个式子来概括:对i'<i,calc_ones(i)-9*(i-i') <= calc_ones(i') <= calc_ones(i)。这样就能大大提高速度了。

posted @ 2006-09-16 15:35 chenger 阅读(729) | 评论 (4)编辑 收藏

2006年9月13日

     摘要: 问题是这样的:3*3的方格,填入1-10(比10更大也可以),要求相邻两数之和为素数。 这个题目除了回溯似乎没有别的方法了。  阅读全文

posted @ 2006-09-13 23:13 chenger 阅读(810) | 评论 (0)编辑 收藏

2006年9月11日

     摘要: 这回还是一个语言细节问题:求值顺序,副作用等等。说白了和v[i]=i++是差不多的。不关心这类细枝末节的朋友们可以不用看了。  阅读全文

posted @ 2006-09-11 19:01 chenger 阅读(620) | 评论 (3)编辑 收藏

2006年9月8日

从同学那儿听说了一个传说是Google面试题的题目:找出所有的正整数N,使得小于N的所有正整数的各位数字中所有的'1'的数目和N相等。

我的解法:

#include <iostream>
#include
<limits>
#include
<cstddef>

using
namespace std;

size_t calc_ones(size_t n)
{

    const
size_t save = n;
    size_t sum = 0,ten = 1,cnt = 1;
    if(n%10 > 1)
        sum =
1;
    n /=
10;
    for
(;n;n /= 10)
    {

        size_t
r = n%10;
        if
(r == 1)
            sum += save + (r*cnt -
10*n)*ten;
        else if(r != 0)
            sum += (
10 + r*cnt)*ten;
        ten *=
10;
        ++cnt;
    }
    return sum;
}

void solve()
{

    size_t
max = numeric_limits<size_t>::max();
    for
(size_t i = 1;i < max;++i)
        if
(calc_ones(i) == i)
            cout << i <<
"\n";
}


int
main()
{
    solve();

    return
0;
}


在VS2005下编译运行,输出结果为:

199992 199993 199994 199995 199996 199997 199998 199999 200000 1599992 1599993 1599994 1599995 1599996 1599997 1599998 1599999 1600000 1600001 2600000 13200000 13200001 35000000 35199992 35199993 35199994 35199995 35199996 35199997 35199998 35199999 35200000 117463827 500000000 500199992 500199993 500199994 500199995 500199996 500199997 500199998 500199999 500200000 501599992 501599993 501599994 501599995 501599996 501599997 501599998 501599999 501600000 501600001 502600000 513200000 513200001 535000000 535199992 535199993 535199994 535199995 535199996 535199997 535199998 535199999 535200000

可以证明,再往上就没有了。跑得比较慢,需要好几分钟。我考虑过进一步缩小检索的范围,应该是可以做到的,不过没有实现。

Update:上面的算法有很大的改进余地,主要来自张沈鹏同学给出的程序,我专门写了一篇文章来讨论,这里。或者可以直接看张沈鹏同学的文章

posted @ 2006-09-08 13:05 chenger 阅读(1560) | 评论 (13)编辑 收藏

2006年9月6日

余生也晚,没赶上那个Turbo Pascal风靡世界的年代,只在学C的时候用过一阵Turbo C,后来拿C++ Builder搞了几个小GUI程序,感觉比VC6容易上手……所以一直关心Borland公司。现在Borland已经卖掉了它的IDE开发部门;这个开发部门如今的名字叫DevCo,它的第一个动作就是让“王者归来”,重新做了一个Turbo系列:Turbo Delphi,Turbo Delphi for .NET,Turbo C++,Turbo C#。尤其值得称道的是提供了免费的Explorer版本下载,对我这样的非专业人员,Explorer的功能已经足够。从这一点上可以看出Turbos的定位。现在我正在下载Turbo C++,从介绍上看,感觉像是C++ Builder的一个精简版,不知道实际表现如何。

Turbo下载

Update:说一下下载文件的情况。有两个部分,一个是prerequisites,另一个是main installation。奇怪的是prerequisites当中还包括.NET Framework 1.1,是不是太old了一点?这部分prerequisites和Borland Develop Studio基本上是一样的。

继续Update:很不幸,未能成功。安装了一遍之后,启动时接连保错,似乎是在读取rtl100.bpl和coreide100.bpl的时候出了段错误,结果IDE是启动了,和C++有关的项目还有组件一个都没有……虽然还剩了诸如编译器和编辑器调试器等内容,但意义不大。考虑到机子上原来还装了个C++ Builder 6,卸之,再重装一遍Turbo C++,还是老样子……彻底放弃。

posted @ 2006-09-06 07:32 chenger 阅读(693) | 评论 (7)编辑 收藏

2006年9月4日

来自于CSDN上的一个帖子,题目很吓人,发现了VS 2005的一个重量级Bug!

还是直接给出代码:

#include <iostream>
#include
<string>

using
namespace std;

int
main()
{

    const
char *p = string("hello").c_str();
    cout << p << endl;

    return
0;
}


想想输出结果是什么?

这时VS2005和g++的结果就不一样了。VS2005上什么都不输出,而g++ 3.4上则输出了似乎非常合理的结果:hello,符合很多人的预期。不过查了标准以后,还是把票投给VS2005。

首先,string("hello")产生了一个temporary object,或者说临时对象。C++标准对临时对象的生存期(life time)有明确的规定,可见标准12.2节第3-5条。第3条讨论了临时对象的析构时间:

3. ... Temporary objects are destroyed as the last step in evaluating the full-expression (1.9) that (lexically) contains the point where they were created. This is true even if that evaluation ends in throwing an exception.

这又涉及到full-expression的定义了,参见1.9节。整个对p的初始化构成了一个full-expression。在下结论之前,还要先看看第4、5条,分别讨论了两个例外情形,一个是将临时对象作为初始化子,例如string s = string("hello");第二是将一个引用变量绑定到这个临时对象上,例如const string &s = string("hello"),总而言之,在这两种情形中可以通过一个名字来存取这个对象,此对象的生存期就延长到变量名的作用域结束。除此之外,都按照第3条处理。

有了这些准备,拿前面给的例子往里套就明白了:这里没有出现4、5所指出的例外,因此第3条的原则适用。而不管full-expression如何,可以确定的是在p被初始化之后临时对象string("hello")的析构函数就应该被调用。在VS2005中进行调试,可以发现string析构函数调用的时间就在p被初始化之后,语句cout << p << endl执行之前。手头没有方便的工具来调试g++编译出来的程序(不太会用gdb调试C++程序,特别涉及到STL)。至于之后p指向的内存到底如何,则和具体的string实现相关了。这样分析下来,VS2005的结果还是比较不错的,而g++的结果则容易让人产生误解。

Update:察看g++编译出来的汇编代码,发现g++同样在表达式求值后析构了临时对象,只不过由于实现上的原因,p指向的内容还没有清空。

posted @ 2006-09-04 23:23 chenger 阅读(1095) | 评论 (13)编辑 收藏

2006年9月2日

主要是因为看了这篇blog突然想到的。这个筛法求素数的程序想必每个学编程的人都写过,几乎是最经典的算法之一了,虽然似乎没什么用。但好像的确没见过对这个古老算法的严格分析。一时好奇,就想把这个算法纳入大O的框架之中……不管怎么样,先拿出代码再说

require'benchmark'
 
def
sievePerformance(n)
    r =
Benchmark.realtime() do
        sieve =
Array.new(n,true)
        sieve[
0..1] = [false,false]
        2.upto(n) do |i|
            if sieve[i]
                (
2*i).step(n,i) do |j|
                    sieve[j] =
false
               
end
           
end
       
end
    end

   
r
end


这段代码抄自前面Robert C.Martin先生的blog,对筛法作性能测试。初看起来,程序的主体是二重循环,因此算法的复杂性好像是O(N2)之类的玩意?要么是O(NlnN)?
 
下图是Ruby自带的benchmark模块测量的结果,上限N从10000到500000,步长20000。Rober C.Martin的文章里也有一张图,是从1000000到5000000,从图中可以看到,他电脑的性能远胜于我,我要是从1000000到5000000这么跑一遍,花儿都谢了……总之,实测的结果是:这个算法的性能基本上是线性的。出于对ruby这样的解释型语言的某种不信任,我又把这段程序用C++重写了一遍,拿C标准库提供的clock函数测量时间,结果在N小于10000000的时候,基本上呈线性,但再往后花费的时间就开始超过线性增长了。

下面我给一个比较粗略的分析,解释为什么这个算法的复杂度表现为线性。首先,我认为主要花费时间的是对sieve数组的读写,循环变量的增加应该可以忽略。如果p<N是素数,那么就要进入内循环将i的倍数“挖掉”,也就是对sieve的相应元素赋值,要进行[N/p]-1次。这样就得到总共的赋值次数S为:



其中p为素数。显然



数论中有个Mertens定理可以估计上面括号中的和式,结果为



其中c是一个常数。可以看到,在N很大时和式的主要部分为NlnlnN。而lnlnN是一个增长极慢的函数,lnln105=2.44,lnln109=2.91,几乎就可以当常数处理(至少在32位无符号整数范围内)。其他的一些项,比如循环变量的步进,都是O(N),这也就不难理解整个程序的性能是几乎是O(N)了。




Update:上面的代码有个很明显的问题,就是内循环应该从i*i开始,而不是2*i,这样对于比较大的N,性能提高很明显(接近一半)。另外一个可改进的地方是外层循环的upto(n),可以改为upto(Integer(Math.sqrt(n)),其实这两个改动效果是重叠的,任意改一个就差不多了。赋值次数S应为:



结果为:



可以看到效率的提升是很明显的,毕竟lnln232也才不到3.1,ln2约为0.7。

posted @ 2006-09-02 21:16 chenger 阅读(531) | 评论 (0)编辑 收藏