Yet Another Programmer

這個(gè)blog主要記錄程序設(shè)計(jì)方面的內(nèi)容，既然是落戶(hù)C++博客，自然要寫(xiě)C/C++的內(nèi)容了。此外，我還對(duì)動(dòng)態(tài)語(yǔ)言（比如Python，Ruby），函數(shù)式編程語(yǔ)言（比如Haskell）感興趣。最近還在斷斷續(xù)續(xù)地學(xué)習(xí).NET Framework的知識(shí)。此外我還在Donews上有一個(gè)blog，寫(xiě)一些和編程無(wú)關(guān)的雜七雜八的內(nèi)容。Donews的最大缺點(diǎn)是沒(méi)法顯示代碼縮進(jìn)，至少我不知道。

今天寫(xiě)代碼的時(shí)候，發(fā)現(xiàn)g++好像不支持模板成員函數(shù)的全特化?？创a：

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

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

我用的是g++ 3.4.2 mingw版本。編譯上面這段代碼時(shí)，錯(cuò)誤信息如下：

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

如果把f的定義放到全局作用域中，就不會(huì)出錯(cuò)。而上面這段代碼在VC++ 8.0下可以編譯通過(guò)。運(yùn)行起來(lái)也沒(méi)有問(wèn)題。別的編譯器我沒(méi)有試過(guò)。

Update：多謝周星星的指點(diǎn)，比較“常規(guī)”的寫(xiě)法如下:

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)
{
??? //...
}

這種寫(xiě)法就沒(méi)有任何問(wèn)題(在g++ 3.4.2和VC++ 8.0下均表現(xiàn)正常）。至于為什么前面的寫(xiě)法導(dǎo)致g++下報(bào)錯(cuò)，還不是很清楚。

歷史：高級(jí)程序語(yǔ)言的老祖宗，F(xiàn)ortran，對(duì)源程序中的名字，或者叫標(biāo)識(shí)符(identifier)有很?chē)?yán)格的規(guī)定，譬如首字母代表變量的類(lèi)型等等。個(gè)人認(rèn)為這是當(dāng)年編譯技術(shù)還未成熟時(shí)的權(quán)宜之計(jì)。后來(lái)主流的程序設(shè)計(jì)語(yǔ)言都放松了對(duì)名字的限制，像C/C++/Java，只有一點(diǎn)點(diǎn)小小的約束（對(duì)所用字符的限制：只能使用英文字母、數(shù)字、下劃線(xiàn)，必須以下劃線(xiàn)或英文字母開(kāi)頭。這也容易理解，完全是為了寫(xiě)詞法分析器的方便）。而和Fortran同時(shí)代的Lisp，這方面更是大開(kāi)綠燈，愛(ài)怎么定義怎么定義。然而到了現(xiàn)在，似乎有點(diǎn)復(fù)古的潮流，有些語(yǔ)言開(kāi)始對(duì)名字設(shè)立一些規(guī)則，比如Haskell,Erlang,包括Ruby。

言歸正傳。Ruby中的名字規(guī)則主要是根據(jù)名字的第一個(gè)字母來(lái)決定這個(gè)名字的使用方式。具體來(lái)說(shuō)，

• 局部變量，方法名，方法參數(shù)：以小寫(xiě)字母或下劃線(xiàn)開(kāi)頭，以'_'連接。
  Example：i,note_controller
• 常量：全部大寫(xiě)，以'_'連接
  Example：A_NUM
• 類(lèi)，模塊(module)：都是開(kāi)頭大寫(xiě)（因?yàn)轭?lèi)名是全局變量），其他小寫(xiě)并且直接連接在一起
  Example：ActiveRecord
• 全局變量：以'$'開(kāi)頭（肯定是跟Perl學(xué)的，我覺(jué)得不怎么好）
• 實(shí)例變量(instance variable)：以'@'開(kāi)頭（同上）
• 類(lèi)變量(class variable)：以'@@'開(kāi)頭（詭異）

有點(diǎn)Perl的味道，但Perl更加變態(tài)，居然要以首字母區(qū)分標(biāo)量、數(shù)組和Hash表，這就不太人道了。相比起來(lái)，Ruby的設(shè)置還是可以接受的，它只不過(guò)是把有些約定俗成的規(guī)則直接變成了語(yǔ)言規(guī)則。每個(gè)程序員基本上都會(huì)有自己的一套命名規(guī)則，比如寫(xiě)C++程序時(shí)，類(lèi)名通常用大寫(xiě)字母開(kāi)頭，宏名則通常由大寫(xiě)字母組成，而下劃線(xiàn)開(kāi)頭的（特別是雙下劃線(xiàn)）往往留給庫(kù)開(kāi)發(fā)者等等。Ruby的想法可能是：干脆統(tǒng)一了這些命名規(guī)則，免得人們?yōu)檫@種風(fēng)格(Style)問(wèn)題爭(zhēng)論不休。也是挺有道理的。

我在自己的電腦上裝了ruby，稍微看了點(diǎn)Programming Ruby，感覺(jué)Ruby有很多想法都非常有意思，值得學(xué)習(xí)，比如塊，以及徹底的Object Oriented(對(duì)于誰(shuí)比誰(shuí)更OO，從來(lái)都是爭(zhēng)吵不斷，比如Java比C++更OO，C#比Java又更OO，等等，往往引起論壇上一片腥風(fēng)血雨。我這個(gè)也就是隨便說(shuō)說(shuō)），迭代器。很多語(yǔ)言特性和Python相差不大，估計(jì)腳本語(yǔ)言做到一定程度多少都有些相似的，當(dāng)然各有各的特點(diǎn)。然后又看了點(diǎn)源代碼，終于明白為何Ruby的性能如此被人詬病：構(gòu)造了AST以后，直接在AST上遞歸進(jìn)行eval。而Python，Perl,Lua等都是編譯為中間語(yǔ)言再交給虛擬機(jī)執(zhí)行。如果能有一個(gè)JIT編譯器（像.NET那樣）就更牛了。Ruby傳說(shuō)中的2.0版本要引入虛擬機(jī)，YARV。不過(guò)那2.0遙遙無(wú)期，目前最新的stable是1.8.5，2.0據(jù)說(shuō)要到08奧運(yùn)那會(huì)了。

Ruby的源代碼還充分體現(xiàn)了拿來(lái)主義的精神，能重用的決不自己寫(xiě)：比如Hash表就用了一個(gè)通用的Hash表實(shí)現(xiàn)，正則表達(dá)式則使用了GNU的regex庫(kù)，random是有名的MT19937（也是日本人寫(xiě)的）。嘗試了一下編譯，在mingw上執(zhí)行標(biāo)準(zhǔn)三部曲：./configure,make,make install，一切OK。

上次寫(xiě)了一篇關(guān)于google面試題的文章。我給的算法跑得很慢，后面張沈鵬同學(xué)用python寫(xiě)了一個(gè)算法，速度很快（再次感覺(jué)python的性能不像想象中那么壞，當(dāng)然和算法有關(guān)），看了一下他的代碼，函數(shù)count(i)用來(lái)計(jì)算小于i的1的個(gè)數(shù)，和我寫(xiě)的calc_ones算法基本相同，只不過(guò)count(i)用了遞歸，看上去更清楚一些。主要的速度差別在little(i)函數(shù)上，這個(gè)函數(shù)避免了很多迭代：

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++版本。主循環(huán)也要略微改變一下：

void solve()
{
??? size_t max = 10000000000;
??? for(size_t i = max;i > 0;i = little(i));
}

可以看到，現(xiàn)在循環(huán)從大到小。little函數(shù)找到下一個(gè)可能滿(mǎn)足題目約束的i。在little函數(shù)中，首先計(jì)算小于i的1的個(gè)數(shù)ones，如果ones和i相等，就將i輸出（這就是題目要求干的事）。如果i小于ones，那么就要在小于i的自然數(shù)中找下一個(gè)可能滿(mǎn)足條件的數(shù)。因?yàn)樗阉鞯姆秶怀^(guò)10^10，所以一個(gè)數(shù)中至多含有9個(gè)1，按照這種極端情況，也必須將i減少(ones-i)/8才有可能滿(mǎn)足條件(這里之所以是8，因?yàn)橥瑫r(shí)i也減少了）。如果i大于ones，考慮一個(gè)小于i的數(shù)i'，可以考慮一下calc_ones(i')的取值，極端情況，[i',i)的范圍內(nèi)的整數(shù)沒(méi)有一個(gè)包含1，也就是說(shuō)當(dāng)i減少到i'時(shí)1的個(gè)數(shù)沒(méi)有損失，那么calc_ones(i') = calc_ones(i)，如果i'>calc_ones(i)，則就有i'>calc_ones(i')，直到i'=calc_ones(i)，因此下一個(gè)需要查看的數(shù)就是calc_ones(i)。其實(shí)上面這一段討論可以用一個(gè)式子來(lái)概括：對(duì)i'<i,calc_ones(i)-9*(i-i') <= calc_ones(i') <= calc_ones(i)。這樣就能大大提高速度了。

     摘要: 問(wèn)題是這樣的：3*3的方格，填入1-10（比10更大也可以），要求相鄰兩數(shù)之和為素?cái)?shù)。 這個(gè)題目除了回溯似乎沒(méi)有別的方法了。  閱讀全文

     摘要: 這回還是一個(gè)語(yǔ)言細(xì)節(jié)問(wèn)題：求值順序，副作用等等。說(shuō)白了和v[i]=i++是差不多的。不關(guān)心這類(lèi)細(xì)枝末節(jié)的朋友們可以不用看了。  閱讀全文

從同學(xué)那兒聽(tīng)說(shuō)了一個(gè)傳說(shuō)是Google面試題的題目：找出所有的正整數(shù)N，使得小于N的所有正整數(shù)的各位數(shù)字中所有的'1'的數(shù)目和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下編譯運(yùn)行，輸出結(jié)果為：

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

可以證明，再往上就沒(méi)有了。跑得比較慢，需要好幾分鐘。我考慮過(guò)進(jìn)一步縮小檢索的范圍，應(yīng)該是可以做到的，不過(guò)沒(méi)有實(shí)現(xiàn)。

Update：上面的算法有很大的改進(jìn)余地，主要來(lái)自張沈鵬同學(xué)給出的程序，我專(zhuān)門(mén)寫(xiě)了一篇文章來(lái)討論，這里?；蛘呖梢灾苯涌?a href="/zuroc/archive/2006/09/16/12540.html">張沈鵬同學(xué)的文章。

余生也晚，沒(méi)趕上那個(gè)Turbo Pascal風(fēng)靡世界的年代，只在學(xué)C的時(shí)候用過(guò)一陣Turbo C，后來(lái)拿C++ Builder搞了幾個(gè)小GUI程序，感覺(jué)比VC6容易上手……所以一直關(guān)心Borland公司?，F(xiàn)在Borland已經(jīng)賣(mài)掉了它的IDE開(kāi)發(fā)部門(mén)；這個(gè)開(kāi)發(fā)部門(mén)如今的名字叫DevCo，它的第一個(gè)動(dòng)作就是讓“王者歸來(lái)”，重新做了一個(gè)Turbo系列：Turbo Delphi,Turbo Delphi for .NET,Turbo C++,Turbo C#。尤其值得稱(chēng)道的是提供了免費(fèi)的Explorer版本下載，對(duì)我這樣的非專(zhuān)業(yè)人員，Explorer的功能已經(jīng)足夠。從這一點(diǎn)上可以看出Turbos的定位?，F(xiàn)在我正在下載Turbo C++，從介紹上看，感覺(jué)像是C++ Builder的一個(gè)精簡(jiǎn)版，不知道實(shí)際表現(xiàn)如何。

Turbo下載

Update：說(shuō)一下下載文件的情況。有兩個(gè)部分，一個(gè)是prerequisites，另一個(gè)是main installation。奇怪的是prerequisites當(dāng)中還包括.NET Framework 1.1，是不是太old了一點(diǎn)？這部分prerequisites和Borland Develop Studio基本上是一樣的。

繼續(xù)Update：很不幸，未能成功。安裝了一遍之后，啟動(dòng)時(shí)接連保錯(cuò)，似乎是在讀取rtl100.bpl和coreide100.bpl的時(shí)候出了段錯(cuò)誤，結(jié)果IDE是啟動(dòng)了，和C++有關(guān)的項(xiàng)目還有組件一個(gè)都沒(méi)有……雖然還剩了諸如編譯器和編輯器調(diào)試器等內(nèi)容，但意義不大。考慮到機(jī)子上原來(lái)還裝了個(gè)C++ Builder 6，卸之，再重裝一遍T(mén)urbo C++，還是老樣子……徹底放棄。

來(lái)自于CSDN上的一個(gè)帖子，題目很?chē)樔耍?a >發(fā)現(xiàn)了VS 2005的一個(gè)重量級(jí)Bug!

還是直接給出代碼：

#include <iostream>
#include <string>

using namespace std;

int main()
{
??? const char *p = string("hello").c_str();
??? cout << p << endl;
??? return 0;
}

想想輸出結(jié)果是什么？

這時(shí)VS2005和g++的結(jié)果就不一樣了。VS2005上什么都不輸出，而g++ 3.4上則輸出了似乎非常合理的結(jié)果：hello，符合很多人的預(yù)期。不過(guò)查了標(biāo)準(zhǔn)以后，還是把票投給VS2005。

首先，string("hello")產(chǎn)生了一個(gè)temporary object，或者說(shuō)臨時(shí)對(duì)象。C++標(biāo)準(zhǔn)對(duì)臨時(shí)對(duì)象的生存期(life time)有明確的規(guī)定，可見(jiàn)標(biāo)準(zhǔn)12.2節(jié)第3-5條。第3條討論了臨時(shí)對(duì)象的析構(gòu)時(shí)間：

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的定義了，參見(jiàn)1.9節(jié)。整個(gè)對(duì)p的初始化構(gòu)成了一個(gè)full-expression。在下結(jié)論之前，還要先看看第4、5條，分別討論了兩個(gè)例外情形，一個(gè)是將臨時(shí)對(duì)象作為初始化子，例如string s = string("hello")；第二是將一個(gè)引用變量綁定到這個(gè)臨時(shí)對(duì)象上，例如const string &s = string("hello")，總而言之，在這兩種情形中可以通過(guò)一個(gè)名字來(lái)存取這個(gè)對(duì)象，此對(duì)象的生存期就延長(zhǎng)到變量名的作用域結(jié)束。除此之外，都按照第3條處理。

有了這些準(zhǔn)備，拿前面給的例子往里套就明白了：這里沒(méi)有出現(xiàn)4、5所指出的例外，因此第3條的原則適用。而不管full-expression如何，可以確定的是在p被初始化之后臨時(shí)對(duì)象string("hello")的析構(gòu)函數(shù)就應(yīng)該被調(diào)用。在VS2005中進(jìn)行調(diào)試，可以發(fā)現(xiàn)string析構(gòu)函數(shù)調(diào)用的時(shí)間就在p被初始化之后，語(yǔ)句cout << p << endl執(zhí)行之前。手頭沒(méi)有方便的工具來(lái)調(diào)試g++編譯出來(lái)的程序(不太會(huì)用gdb調(diào)試C++程序，特別涉及到STL)。至于之后p指向的內(nèi)存到底如何，則和具體的string實(shí)現(xiàn)相關(guān)了。這樣分析下來(lái)，VS2005的結(jié)果還是比較不錯(cuò)的，而g++的結(jié)果則容易讓人產(chǎn)生誤解。

Update：察看g++編譯出來(lái)的匯編代碼，發(fā)現(xiàn)g++同樣在表達(dá)式求值后析構(gòu)了臨時(shí)對(duì)象，只不過(guò)由于實(shí)現(xiàn)上的原因，p指向的內(nèi)容還沒(méi)有清空。

主要是因?yàn)榭戳?a >這篇blog突然想到的。這個(gè)篩法求素?cái)?shù)的程序想必每個(gè)學(xué)編程的人都寫(xiě)過(guò)，幾乎是最經(jīng)典的算法之一了，雖然似乎沒(méi)什么用。但好像的確沒(méi)見(jiàn)過(guò)對(duì)這個(gè)古老算法的嚴(yán)格分析。一時(shí)好奇，就想把這個(gè)算法納入大O的框架之中……不管怎么樣，先拿出代碼再說(shuō)

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，對(duì)篩法作性能測(cè)試。初看起來(lái)，程序的主體是二重循環(huán)，因此算法的復(fù)雜性好像是O(N²)之類(lèi)的玩意？要么是O(NlnN)？
?
下圖是Ruby自帶的benchmark模塊測(cè)量的結(jié)果，上限N從10000到500000，步長(zhǎng)20000。Rober C.Martin的文章里也有一張圖，是從1000000到5000000，從圖中可以看到，他電腦的性能遠(yuǎn)勝于我，我要是從1000000到5000000這么跑一遍，花兒都謝了……總之，實(shí)測(cè)的結(jié)果是：這個(gè)算法的性能基本上是線(xiàn)性的。出于對(duì)ruby這樣的解釋型語(yǔ)言的某種不信任，我又把這段程序用C++重寫(xiě)了一遍，拿C標(biāo)準(zhǔn)庫(kù)提供的clock函數(shù)測(cè)量時(shí)間，結(jié)果在N小于10000000的時(shí)候，基本上呈線(xiàn)性，但再往后花費(fèi)的時(shí)間就開(kāi)始超過(guò)線(xiàn)性增長(zhǎng)了。

下面我給一個(gè)比較粗略的分析，解釋為什么這個(gè)算法的復(fù)雜度表現(xiàn)為線(xiàn)性。首先，我認(rèn)為主要花費(fèi)時(shí)間的是對(duì)sieve數(shù)組的讀寫(xiě)，循環(huán)變量的增加應(yīng)該可以忽略。如果p<N是素?cái)?shù)，那么就要進(jìn)入內(nèi)循環(huán)將i的倍數(shù)“挖掉”，也就是對(duì)sieve的相應(yīng)元素賦值，要進(jìn)行[N/p]-1次。這樣就得到總共的賦值次數(shù)S為：



其中p為素?cái)?shù)。顯然



數(shù)論中有個(gè)Mertens定理可以估計(jì)上面括號(hào)中的和式，結(jié)果為



其中c是一個(gè)常數(shù)?？梢钥吹?，在N很大時(shí)和式的主要部分為NlnlnN。而lnlnN是一個(gè)增長(zhǎng)極慢的函數(shù)，lnln10⁵=2.44，lnln10⁹=2.91，幾乎就可以當(dāng)常數(shù)處理（至少在32位無(wú)符號(hào)整數(shù)范圍內(nèi)）。其他的一些項(xiàng)，比如循環(huán)變量的步進(jìn)，都是O(N)，這也就不難理解整個(gè)程序的性能是幾乎是O(N)了。




Update：上面的代碼有個(gè)很明顯的問(wèn)題，就是內(nèi)循環(huán)應(yīng)該從i*i開(kāi)始，而不是2*i，這樣對(duì)于比較大的N，性能提高很明顯（接近一半）。另外一個(gè)可改進(jìn)的地方是外層循環(huán)的upto(n)，可以改為upto(Integer(Math.sqrt(n))，其實(shí)這兩個(gè)改動(dòng)效果是重疊的，任意改一個(gè)就差不多了。賦值次數(shù)S應(yīng)為：



結(jié)果為：



可以看到效率的提升是很明顯的，畢竟lnln2³²也才不到3.1，ln2約為0.7。