青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

  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 閱讀(3234) | 評論 (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 閱讀(447) | 評論 (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 閱讀(436) | 評論 (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 閱讀(920) | 評論 (4)編輯 收藏

2006年9月13日

     摘要: 問題是這樣的:3*3的方格,填入1-10(比10更大也可以),要求相鄰兩數之和為素數。 這個題目除了回溯似乎沒有別的方法了。  閱讀全文

posted @ 2006-09-13 23:13 chenger 閱讀(992) | 評論 (0)編輯 收藏

2006年9月11日

     摘要: 這回還是一個語言細節問題:求值順序,副作用等等。說白了和v[i]=i++是差不多的。不關心這類細枝末節的朋友們可以不用看了。  閱讀全文

posted @ 2006-09-11 19:01 chenger 閱讀(752) | 評論 (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 閱讀(1803) | 評論 (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 閱讀(876) | 評論 (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 閱讀(1394) | 評論 (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 閱讀(709) | 評論 (0)編輯 收藏

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲宅男天堂在线观看无病毒| 亚洲人成人一区二区在线观看| 欧美精品国产| 欧美.www| 欧美成人免费在线视频| 免费在线看成人av| 欧美韩日高清| 国产精品视频观看| 国产三区二区一区久久| 韩国成人福利片在线播放| 狠狠干成人综合网| 日韩视频一区二区在线观看| 午夜在线一区| 亚洲欧美成人一区二区在线电影 | 一本不卡影院| 亚洲午夜视频在线| 最新国产乱人伦偷精品免费网站 | 亚洲美女中文字幕| 久久九九国产精品| 国产精品国产| 亚洲日本成人女熟在线观看| 中文亚洲欧美| 免费欧美日韩国产三级电影| 亚洲乱码精品一二三四区日韩在线 | 国产精品美女在线| 欧美sm重口味系列视频在线观看| 亚洲国产天堂久久国产91| 欧美一区二区三区日韩视频| 欧美一区二区精品| 国产精品美女久久久久久免费| 亚洲第一区在线| 另类av一区二区| 久久精品国产2020观看福利| 国产精品裸体一区二区三区| 91久久精品www人人做人人爽| 国产尤物精品| 久久精品国产综合精品| 日韩视频在线播放| 欧美午夜寂寞影院| 亚洲专区一区| 欧美一区二区视频97| 国产欧美精品日韩精品| 久久精品国产综合精品| 久久大香伊蕉在人线观看热2| 国产欧美亚洲精品| 麻豆九一精品爱看视频在线观看免费| 亚洲永久网站| 亚洲福利视频免费观看| 亚洲国产mv| 国产美女搞久久| 欧美成人精品1314www| 欧美日本三级| 欧美在线视频导航| 欧美成人午夜激情在线| 亚洲视频一二三| 久久久久久久久久久一区| 亚洲精品免费一二三区| 999亚洲国产精| 欧美一区=区| 亚洲精品欧美激情| 亚洲欧美一区二区原创| 夜夜狂射影院欧美极品| 亚洲欧美日韩在线播放| 日韩午夜免费视频| 久久久国产91| 久久久另类综合| 国产欧美精品| 亚洲伊人伊色伊影伊综合网| 日韩一本二本av| 久久亚洲免费| 亚洲国产老妈| 欧美成人中文| 欧美激情第4页| 亚洲第一网站| 欧美成人一区在线| 欧美黄色一区二区| 亚洲大片在线观看| 两个人的视频www国产精品| 欧美aⅴ99久久黑人专区| 亚洲国产成人午夜在线一区| 久久久久国产精品厨房| 欧美激情精品久久久久久大尺度| 亚洲第一精品电影| 欧美喷水视频| 欧美亚洲免费在线| 亚洲国产精品va在线看黑人| 一本到12不卡视频在线dvd| 欧美亚州一区二区三区| 久久国产精品色婷婷| 亚洲毛片在线免费观看| 亚洲一卡二卡三卡四卡五卡| 国产一区二区精品久久91| 免费成人黄色av| 午夜精品久久久久久99热软件| 免费在线国产精品| 一本到12不卡视频在线dvd| 国产视频精品xxxx| 国产精品青草久久久久福利99| 久久成人精品无人区| 亚洲一区日韩在线| 一区二区毛片| 99在线精品观看| 欧美激情欧美激情在线五月| 亚洲字幕一区二区| 亚洲专区在线视频| 亚洲午夜日本在线观看| 中文在线不卡视频| 亚洲神马久久| 一区二区三区.www| 夜夜嗨av一区二区三区网站四季av | 亚洲新中文字幕| 亚洲精品日产精品乱码不卡| 欧美日韩三级在线| 午夜久久福利| 亚洲裸体在线观看| 欧美成人综合一区| 亚洲欧美精品| 欧美黄色精品| 久久久久成人精品免费播放动漫| 国产日韩视频| 久久综合伊人77777尤物| 午夜激情一区| 久久九九免费| 欧美激情免费在线| 欧美日韩三区| 欧美日韩久久久久久| 欧美日韩国产探花| 欧美二区在线| 欧美日本高清视频| 国产精品视频999| 日韩视频不卡中文| 亚洲天堂av在线免费观看| 欧美性猛交视频| 国产精品一区免费视频| 亚洲精品视频在线看| 亚洲人成啪啪网站| 亚洲午夜激情网站| 麻豆久久精品| 欧美一区二区三区另类 | 欧美韩日一区| 香蕉成人伊视频在线观看| 老司机一区二区三区| 狠狠狠色丁香婷婷综合激情| 夜夜嗨av色综合久久久综合网| 欧美一级久久久| 久久理论片午夜琪琪电影网| 欧美精品一区二区三| 怡红院精品视频| 日韩视频一区二区在线观看| 校园激情久久| 蜜桃av一区二区三区| 99在线精品视频在线观看| 欧美.www| 国产精品久久久久久亚洲调教| 亚洲美女在线观看| 亚洲激情一区| 亚洲一二三级电影| 国产精品亚洲不卡a| 欧美一区二区女人| 久久婷婷色综合| 亚洲乱码国产乱码精品精可以看 | 亚洲女爱视频在线| 欧美日韩亚洲一区二区三区| 亚洲精品久久久蜜桃| 欧美激情亚洲国产| 鲁大师影院一区二区三区| 136国产福利精品导航网址应用| 久久婷婷久久一区二区三区| 午夜精品久久久久久久久久久久 | 亚洲欧美另类在线| 国产精品高清免费在线观看| 亚洲欧美高清| 午夜精品视频| 黄网动漫久久久| 欧美国产免费| 欧美三级欧美一级| 欧美在线视频观看| 午夜一区二区三区在线观看| 亚洲免费视频一区二区| 国产日韩精品一区| 欧美成人免费在线| 国产精品美女在线观看| 另类尿喷潮videofree| 欧美日韩精品综合| 亚洲欧美日韩国产成人精品影院| 欧美在线观看视频一区二区| 亚洲国产二区| 销魂美女一区二区三区视频在线| 亚洲精品久久久久久下一站| 亚洲一区二区三区在线| 黑人一区二区三区四区五区| 欧美国产精品一区| 国产午夜久久| 欧美一二区视频| 亚洲自拍偷拍网址| 欧美激情第三页| 亚洲小少妇裸体bbw| 欧美伦理在线观看| 亚洲欧洲精品一区二区三区不卡| 国产欧美日韩激情|