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 阅读(2453) | 评论 (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 阅读(296) | 评论 (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 阅读(731) | 评论 (4)编辑 收藏

2006年9月13日

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

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

2006年9月11日

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