posts - 195, comments - 34, trackbacks - 0, articles - 1

          最大公約數(shù)和最小公倍數(shù)

          語言: C, 標(biāo)簽: 無  2008/07/22發(fā)布 5個(gè)月前更新 更新記錄
          作者: 半瓶墨水, 點(diǎn)擊5221次, 評論(0), 收藏者(0), , 打分:登錄以后才能打分, 目前平均0.0分,總分0, 共有0個(gè)用戶參與打分
          # 以下描述來自: http://baike.baidu.com/view/47637.htm
          #
          # 最大公約數(shù)(greatest common divisor,簡寫為gcd;
          # 指某幾個(gè)整數(shù)共有公約數(shù)中的最大一個(gè)
          #  例: 在2、4、6中,2就是2,4,6的最大公約數(shù)。
          #
          # 重要性質(zhì):
          # gcd(a,b)=gcd(b,a) (交換律)
          # gcd(-a,b)=gcd(a,b)
          # gcd(a,a)=|a|
          # gcd(a,0)=|a|
          # gcd(a,1)=1
          # gcd(a,b)=gcd(b, a mod b)
          # gcd(a,b)=gcd(b, a-b)
          # 如果有附加的一個(gè)自然數(shù)m,
          # 則: gcd(ma,mb)=m * gcd(a,b) (分配率)
          # gcd(a+mb ,b)=gcd(a,b)
          # 如果m是a和b的最大公約數(shù),
          # 則: gcd(a/m ,b/m)=gcd(a,b)/m
          # 在乘法函數(shù)中有:
          # gcd(ab,m)=gcd(a,m) * gcd(b,m)
          # 兩個(gè)整數(shù)的最大公約數(shù)主要有兩種尋找方法:
          # * 兩數(shù)各分解質(zhì)因子,然后取出同樣有的項(xiàng)乘起來
          # * 輾轉(zhuǎn)相除法(擴(kuò)展版)
          # 和最小公倍數(shù)(lcm)的關(guān)系:
          # gcd(a, b) * lcm(a, b) = ab
          # a與b有最大公約數(shù),但不一定有最小公倍數(shù)。
          # 兩個(gè)整數(shù)的最大公因子可用于計(jì)算兩數(shù)的最小公倍數(shù),或分?jǐn)?shù)化簡成最簡分?jǐn)?shù)。
          # 兩個(gè)整數(shù)的最大公因子和最小公倍數(shù)中存在分配律:
          # * gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
          # * lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))
          # 在坐標(biāo)里,將點(diǎn)(0, 0)和(a, b)連起來,通過整數(shù)坐標(biāo)的點(diǎn)的數(shù)目(除了(0, 0)一點(diǎn)之外)就是gcd(a, b)。
          #
          #
          # 以下代碼來自: http://bbs.bccn.net/thread-224663-1-1.html
          #
          int GCD(int a, int b)
          {
             if(b == 0) return a;
             else return GCD(b, a % b);
          }

          int LCM(int a, int b)
          {
             return a * b / GCD(a,b);
          }

          /*以下代碼來自:http://en.wikipedia.org/wiki/Binary_GCD_algorithm */
          unsigned int gcd(unsigned int u, unsigned int v)
          {
              int shift;

              /* GCD(0,x) := x */
              if (u == 0 || v == 0)
                  return u | v;

              /* Let shift := lg K, where K is the greatest power of 2
                 dividing both u and v. */
              for (shift = 0; ((u | v) & 1) == 0; ++shift) {
                  u >>= 1;
                  v >>= 1;
              }

              while ((u & 1) == 0)
                  u >>= 1;

              /* From here on, u is always odd. */
              do {
                  while ((v & 1) == 0/* Loop X */
                      v >>= 1;

                  /* Now u and v are both odd, so diff(u, v) is even.
                     Let u = min(u, v), v = diff(u, v)/2. */
                  if (u < v) {
                      v -= u;
                  } else {
                      unsigned int diff = u - v;
                      u = v;
                      v = diff;
                  }
                  v >>= 1;
              } while (v != 0);

              return u << shift;
          }

          posted @ 2009-10-26 22:56 小強(qiáng)摩羯座 閱讀(294) | 評論 (0)編輯 收藏

               摘要:     1package dwq.algo.sort;   2   3import java.util.Arrays;   4   5public class Sorting   6{   7 ...  閱讀全文

          posted @ 2009-10-26 11:53 小強(qiáng)摩羯座 閱讀(184) | 評論 (0)編輯 收藏

               摘要: package com.dwq.algo; import java.util.ArrayList; public class LongestIncrementSubarray {     public static void main(String[] arg...  閱讀全文

          posted @ 2009-10-26 11:39 小強(qiáng)摩羯座 閱讀(186) | 評論 (0)編輯 收藏

          召集)你能想到的最奇妙的算法題是什么?
          http://www.matrix67.com/blog/archives/1850

          DLX
          http://sqybi.com/works/dlxcn/


          OI最后的謝幕·18歲新的開始http://blog.sina.com.cn/s/blog_4a443fd701000bko.html

          posted @ 2009-10-26 01:09 小強(qiáng)摩羯座 閱讀(197) | 評論 (0)編輯 收藏

          轉(zhuǎn)]怎樣做人
          1、不要推卸責(zé)任,哪怕是別人的責(zé)任。無論發(fā)生任何事情,首先想到自己是不是做錯了。如果自己沒錯(那是不可能的),那就站在對方的角度上,體驗(yàn)一下對方的感受。(本人將此點(diǎn)放在第一條是提醒自己永遠(yuǎn)都要帶著責(zé)任心去做事)
          2、要讓自己適應(yīng)環(huán)境,而不是讓環(huán)境來適應(yīng)你。哪怕這是一個(gè)非常痛苦的過程。新到一個(gè)地方不要急于融入到其中的哪一個(gè)圈子中去,等到了足夠的時(shí)間和考驗(yàn),屬于你的圈子自然就會接納你。(本人十幾年跳到過的地方多不勝數(shù),這是一條最寶貴的原則)
          3、大方一點(diǎn),不會大方就學(xué)大方一點(diǎn)。如果大方讓你很心痛,你就裝大方一點(diǎn)。(不怕大家笑話,我最大方)
          4、低調(diào)一點(diǎn),再低調(diào)一點(diǎn),永遠(yuǎn)低調(diào)一點(diǎn)(要比臨時(shí)工還要低調(diào)一點(diǎn),可能在別人的眼光中你還不如一個(gè)新來的臨時(shí)工呢,本人還沒完全做的到)。
          5、嘴甜且不吝惜自己的喝彩聲,要會夸人,好的夸獎讓人覺得很舒服,但不要過份讓人反感。(呵呵,這點(diǎn)我就不太行了,不過還可以)
          6、如果你覺得最近工作順利的不得了,那你就要更加小心了。(順境思危,本人自信做的還行吧
          7、禮貌對待人,打招呼的時(shí)候要看著對方的眼睛。永遠(yuǎn)記著自己就是一個(gè)不者不扣的小字輩。(做人起碼的原則)
          8、言多必失,少說多做,人多的場合少說話。(本人吃的虧太多了,這個(gè)原則是用教訓(xùn)換來的)
          9、不要把別人的好,當(dāng)做理所當(dāng)然,要知道感恩圖報(bào)。(中國人的優(yōu)秀傳統(tǒng)不要忘記了)
          10、手高眼低,要有平常心。(沒有什么大不了的,好事呀往壞處想,壞事要往好處想,塞翁失馬,禍福難測啊)
          11、遵守時(shí)間,但不要期待別人同樣遵守時(shí)間。(對自己永遠(yuǎn)嚴(yán)格要求不會錯)
          12、信守諾言,但不要輕易許諾,更不要把別人的對你的承諾記在心里并信以為真。(本人提醒大家就算要承諾也要承諾永遠(yuǎn)做不到的,呵呵)
          13、不要向同事借錢,如果借了那就要準(zhǔn)時(shí)還;不要借錢給同事,如果不得不借,就當(dāng)作是送給他的好了。(呵呵,別把金錢看的太重,不過沒錢萬萬不能)
          14、如果你帶領(lǐng)一個(gè)團(tuán)隊(duì),在總結(jié)工作時(shí)要把錯誤攬?jiān)谧约旱纳砩希压诙加浽谙聦俚念^上。當(dāng)上司和下屬同時(shí)在場的時(shí)候你要記得及時(shí)表揚(yáng)你的下屬。(批評人的時(shí)候一定要在只有你們兩個(gè)人的情況下才能進(jìn)行,保持團(tuán)隊(duì)的凝聚力最重要)
          15、不要在一個(gè)同事面前不要說另外一個(gè)同事的壞話,要堅(jiān)持說人的好話,別擔(dān)心這好話傳不到對方的耳中。如果有人在你面前說其他人的壞話,你要保持正常的微笑,不參與評論。(流言止于己,禍從口出是至理名言)
          16、避免與同事公開對立,包括公開提出反對意見,激烈的更不可取。(兩虎相爭,必有一傷,堅(jiān)持具備平衡的做人處事能力就會自然化解反對意見)
          17、經(jīng)常幫助別人,但是不要讓對方覺得是你理所當(dāng)然應(yīng)該做的。(好心有時(shí)候不會有好結(jié)果,但不能因此而灰心,天長地久見人心,一句話:苦心人,天不誤!)
          18、說實(shí)在話會讓你倒足八輩子的霉。(本人吃的虧就是一種財(cái)富,這是必須堅(jiān)持的原則)
          19、做事先做人,對事不對人;對事無情,同時(shí)對人要有情。(公平、公正、公開)
          20、經(jīng)常檢查自己是不是又驕傲了,又自負(fù)了,又看不起別人了。(一個(gè)人再有天大的本事,如果沒有別人的合作和幫助都是白搭)
          21、忍耐是人生一輩子要修煉的一門功課,要用一輩子的時(shí)間去學(xué)。(張家名言:張公百忍,另有“百忍堂”為證)
          22、盡量不要和同事發(fā)生有什么辦公室戀情,如果實(shí)在避免不了的話,那就在辦公室避免任何形式的接觸,包括眼神。(兔子不吃窩邊草,煩惱總是從身邊開始的)
          23、待上以敬,待下以寬。(要會拍上司的馬屁,這是和上司溝通的重要途徑之一,但千萬不要弄臟了手)
          24、資歷非常重要,不要和老家伙們耍心眼斗法,否則你會死的很難看。(中國的社會傳統(tǒng),不會有錯)

          posted @ 2009-10-25 14:51 小強(qiáng)摩羯座 閱讀(195) | 評論 (0)編輯 收藏

          最長遞增子序列的求法 LIS (轉(zhuǎn))

          什么是最長遞增子序列呢?
          問題描述如下:
             設(shè)L=<a1,a2,…,an>是n個(gè)不同的實(shí)數(shù)的序列,L的遞增子序列是這樣一個(gè)子序列Lin=<aK1,ak2,…,akm>,其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
          對于這個(gè)問題有以下幾種解決思路:
             1、把a(bǔ)1,a2,...,an排序,假設(shè)得到a'1,a'2,...,a'n,然后求a的a'的最長公共子串,這樣總的時(shí)間復(fù)雜度為o(nlg(n))+o(n^2)=o(n^2);
             2、動態(tài)規(guī)劃的思路:
              另設(shè)一輔助數(shù)組b,定義b[n]表示以a[n]結(jié)尾的最長遞增子序列的長度,則狀態(tài)轉(zhuǎn)移方程如下:b[k]=max(max(b[j]|a[j]<a[k],j<k)+1,1);
              這個(gè)狀態(tài)轉(zhuǎn)移方程解釋如下:在a[k]前面找到滿足a[j]<a[k]的最大b[j],然后把a(bǔ)[k]接在它的后面,可得到a[k]的最長遞增子序列的長度,或者a[k]前面沒有比它小的a[j],那么這時(shí)a[k]自成一序列,長度為1.最后整個(gè)數(shù)列的最長遞增子序列即為max(b[k]   | 0<=k<=n-1);
              實(shí)現(xiàn)代碼如下:
              

          #include <iostream>

          using namespace std;

          int main()

          {

                 int i,j,n,a[100],b[100],max;

                 while(cin>>n)

                 {

                        for(i=0;i<n;i++)

                               cin>>a[i];

                        b[0]=1;//初始化,以a[0]結(jié)尾的最長遞增子序列長度為1

                        for(i=1;i<n;i++)

                        {

                               b[i]=1;//b[i]最小值為1

                               for(j=0;j<i;j++)

                                      if(a[i]>a[j]&&b[j]+1>b[i])

                                             b[i]=b[j]+1;

                        }

                        for(max=i=0;i<n;i++)//求出整個(gè)數(shù)列的最長遞增子序列的長度

                               if(b[i]>max)

                                      max=b[i];

                        cout<<max<<endl;

                 }

                 return 0;

          }

              顯然,這種方法的時(shí)間復(fù)雜度仍為o(n^2);
             3、對第二種思路的改進(jìn):
              第二種思路在狀態(tài)轉(zhuǎn)移時(shí)的復(fù)雜度為o(n),即在找a[k]前面滿足a[j]<a[k]的最大b[j]時(shí)采用的是順序查找的方法,復(fù)雜度為o(n).
              設(shè)想如果能把順序查找改為折半查找,則狀態(tài)轉(zhuǎn)移時(shí)的復(fù)雜度為o(lg(n)),這個(gè)問題的總的復(fù)雜度就可以降到nlg(n).
              另定義一數(shù)組c,c中元素滿足c[b[k]]=a[k],解釋一下,即當(dāng)遞增子序列的長度為b[k]時(shí)子序列的末尾元素為c[b[k]]=a[k].
              先給出這種思路的代碼,然后再對其做出解釋。
              

          #include <iostream>

          using namespace std;

          int find(int *a,int len,int n)//若返回值為x,a[x]>=n>a[x-1]

          {

                 int left=0,right=len,mid=(left+right)/2;

                 while(left<=right)

                 {

                        if(n>a[mid]) left=mid+1;

                        else if(n<a[mid]) right=mid-1;

                        else return mid;

                        mid=(left+right)/2;

                 }

                 return left;

          }

          void fill(int *a,int n)

          {

                 for(int i=0;i<=n;i++)

                        a[i]=1000;

          }

          int main()

          {

                 int max,i,j,n,a[100],b[100],c[100];

                 while(cin>>n)

                 {

                        fill(c,n+1);

                        for(i=0;i<n;i++)

                               cin>>a[i];

                        c[0]=-1;//    …………………………………………1

                        c[1]=a[0];//        ……………………………………2

                        b[0]=1;//     …………………………………………3

                        for(i=1;i<n;i++)//        ………………………………4

                        {

                               j=find(c,n+1,a[i]);//   ……………………5

                               c[j]=a[i];// ………………………………6

                               b[i]=j;//……………………………………7

                        }

                        for(max=i=0;i<n;i++)//………………………………8

                               if(b[i]>max)

                                      max=b[i];

                        cout<<max<<endl;

                 }

                 return 0;

          }

              對于這段程序,我們可以用算法導(dǎo)論上的loop invariants來幫助理解.
              loop invariant: 1、每次循環(huán)結(jié)束后c都是單調(diào)遞增的。(這一性質(zhì)決定了可以用二分查找)
                                     2、每次循環(huán)后,c[i]總是保存長度為i的遞增子序列的最末的元素,若長度為i的遞增子序

                                            列有多個(gè),剛保存末尾元素最小的那個(gè).(這一性質(zhì)決定是第3條性質(zhì)成立的前提)
                                     3、每次循環(huán)完后,b[i]總是保存以a[i]結(jié)尾的最長遞增子序列。
              initialization:    1、進(jìn)入循環(huán)之前,c[0]=-1,c[1]=a[0],c的其他元素均為1000,c是單調(diào)遞增的;
                                     2、進(jìn)入循環(huán)之前,c[1]=a[0],保存了長度為1時(shí)的遞增序列的最末的元素,且此時(shí)長度為1

                                           的遞增了序列只有一個(gè),c[1]也是最小的;
                                     3、進(jìn)入循環(huán)之前,b[0]=1,此時(shí)以a[0]結(jié)尾的最長遞增子序列的長度為1.
              maintenance:   1、若在第n次循環(huán)之前c是單調(diào)遞增的,則第n次循環(huán)時(shí),c的值只在第6行發(fā)生變化,而由

                                          c進(jìn)入循環(huán)前單調(diào)遞增及find函數(shù)的性質(zhì)可知(見find的注釋),

                                           此時(shí)c[j+1]>c[j]>=a[i]>c[j-1],所以把c[j]的值更新為a[i]后,c[j+1]>c[j]>c[j-1]的性質(zhì)仍然成

                                          立,即c仍然是單調(diào)遞增的;
                                     2、循環(huán)中,c的值只在第6行發(fā)生變化,由c[j]>=a[i]可知,c[j]更新為a[i]后,c[j]的值只會變

                                            小不會變大,因?yàn)檫M(jìn)入循環(huán)前c[j]的值是最小的,則循環(huán)中把c[j]更新為更小的a[i],當(dāng)

                                           然此時(shí)c[j]的值仍是最小的;
                                     3、循環(huán)中,b[i]的值在第7行發(fā)生了變化,因?yàn)橛衛(wèi)oop invariant的性質(zhì)2,find函數(shù)返回值

                                          為j有:c[j-1]<a[i]<=c[j],這說明c[j-1]是小于a[i]的,且以c[j-1]結(jié)尾的遞增子序列有最大的

                                         長度,即為j-1,把a(bǔ)[i]接在c[j-1]后可得到以a[i]結(jié)尾的最長遞增子序列,長度為(j-1)+1=j;
              termination:       循環(huán)完后,i=n-1,b[0],b[1],...,b[n-1]的值均已求出,即以a[0],a[1],...,a[n-1]結(jié)尾的最長遞

                                        增子序列的長度均已求出,再通過第8行的循環(huán),即求出了整個(gè)數(shù)組的最長遞增子序列。

                    仔細(xì)分析上面的代碼可以發(fā)現(xiàn),每次循環(huán)結(jié)束后,假設(shè)已經(jīng)求出c[1],c[2],c[3],...,c[len]的值,則此時(shí)最長遞增子序列的長度為len,因此可以把上面的代碼更加簡化,即可以不需要數(shù)組b來輔助存儲,第8行的循環(huán)也可以省略。
              

          #include <iostream>

          using namespace std;

          int find(int *a,int len,int n)//修改后的二分查找,若返回值為x,則a[x]>=n

          {

                 int left=0,right=len,mid=(left+right)/2;

                 while(left<=right)

                 {

                        if(n>a[mid]) left=mid+1;

                        else if(n<a[mid]) right=mid-1;

                        else return mid;

                        mid=(left+right)/2;

                 }

                 return left;

          }

          int main()

          {

                 int n,a[100],b[100],c[100],i,j,len;//新開一變量len,用來儲存每次循環(huán)結(jié)束后c中已經(jīng)求出值的元素的最大下標(biāo)

                 while(cin>>n)

                 {

                        for(i=0;i<n;i++)

                               cin>>a[i];

                        b[0]=1;

                        c[0]=-1;

                        c[1]=a[0];

                        len=1;//此時(shí)只有c[1]求出來,最長遞增子序列的長度為1.

                        for(i=1;i<n;i++)

                        {

                               j=find(c,len,a[i]);

                               c[j]=a[i];

                               if(j>len)//要更新len,另外補(bǔ)充一點(diǎn):由二分查找可知j只可能比len1

                                      len=j;//更新len

                        }

                        cout<<len<<endl;

                 }

                 return 0;

          }

          最長遞增部分序列 Longest Ordered Subsequence Extention hoj10027 poj2533
          2007-08-21 20:19

          求最長遞增部分序列是一個(gè)比較常見的動態(tài)規(guī)劃題。在導(dǎo)彈攔截等題中都有用到。一般來說就是用經(jīng)典的O(n^2)的動態(tài)規(guī)劃算法。

          算法如下:

                   設(shè)A[i]表示序列中的第i個(gè)數(shù),F(xiàn)[i]表示從1到i這一段中以i結(jié)尾的最長上升子序列的長度,初始時(shí)設(shè)F[i] = 0(i = 1, 2, ..., len(A))。則有動態(tài)規(guī)劃方程:F[i] = max{1, F[j] + 1} (j = 1, 2, ..., i - 1, 且A[j] < A[i])。

          然而在hoj10027中n的值達(dá)到了50000。顯而易見經(jīng)典算法是會超時(shí)滴。所以只有另謀出路了。

                   用一個(gè)變量len記錄到目前為止所找出來的最長遞增序列的長度。另外準(zhǔn)備一個(gè)數(shù)組b[],用這個(gè)數(shù)組表示長度為j的遞增序列中最后一個(gè)元素的值。在這里長度為j的遞增序列不止一個(gè),我們所要保存是那個(gè)最小的。為什么呢?因?yàn)樽詈笠粋€(gè)元素越小,那么這個(gè)遞增序列在往后被延長的機(jī)會越大。初始化b[0] = -1;len = 0;從第一個(gè)元素a[1]開始       a[i]( 1 <= i <= n)。如果這個(gè)元素比len長的序列的最大值大。則把這個(gè)元素直接添加到b數(shù)組的后面。如果這個(gè)元素比b數(shù)組的第一個(gè)元素還要小則把這個(gè)元素賦給b數(shù)組的第一個(gè)值。否則進(jìn)行二分查找。當(dāng)在b數(shù)組里面找到一個(gè)數(shù)比a[i]小,并且他的后面的數(shù)大于或等于a[i]則跳出。將a[i]添加到這個(gè)數(shù)的后面。輸出len就可以了。

          代碼如下:

          #include <stdio.h>
          #include <string.h>
          int main()
          {
          int a[50001], b[50001];
          int i, j, l, r, len, n, mid;
          while (scanf("%d", &n) != EOF)
          {
             for (i = 0; i < n; i++)
              scanf("%d", &a[i]);
             len = 0;
             memset(b, 0, sizeof(int) * 50001);
             b[0] = -1;
             for (i = 0; i < n; i++)
             {
              if (a[i] > b[len])
               b[++len] = a[i];
              else if (a[i] < b[1] )
               b[1] = a[i];
              else
              {
               l = 1; r = len;
               while (l <= r)
               {
                mid = (l + r)>>1;
                if (a[i] > b[mid] && a[i] <= b[mid + 1])
                {
                 j = mid;
                 break;
                }
                if (b[mid] > a[i])
                {
                 r = mid - 1;
                }
                else
                {
                 j = mid;
                 l = mid + 1;
                }
               }
               b[j + 1] = a[i];
              }
             }
             printf("%d\n", len);
          }
          return 0;

          posted @ 2009-10-25 11:27 小強(qiáng)摩羯座 閱讀(2929) | 評論 (1)編輯 收藏

           Java把內(nèi)存劃分成兩種:一種是棧內(nèi)存,一種是堆內(nèi)存。

              在函數(shù)中定義的一些基本類型的變量和對象的引用變量都在函數(shù)的棧內(nèi)存中分配。

              當(dāng)在一段代碼塊定義一個(gè)變量時(shí),Java就在棧中為這個(gè)變量分配內(nèi)存空間,當(dāng)超過變量的作用域后,Java會自動釋放掉為該變量所分配的內(nèi)存空間,該內(nèi)存空間可以立即被另作他用。

              堆內(nèi)存用來存放由new創(chuàng)建的對象和數(shù)組。

              在堆中分配的內(nèi)存,由Java虛擬機(jī)的自動垃圾回收器來管理。

              在堆中產(chǎn)生了一個(gè)數(shù)組或?qū)ο蠛螅€可以在棧中定義一個(gè)特殊的變量,讓棧中這個(gè)變量的取值等于數(shù)組或?qū)ο笤诙褍?nèi)存中的首地址,棧中的這個(gè)變量就成了數(shù)組或?qū)ο蟮囊米兞俊?/p>

              引用變量就相當(dāng)于是為數(shù)組或?qū)ο笃鸬囊粋€(gè)名稱,以后就可以在程序中使用棧中的引用變量來訪問堆中的數(shù)組或?qū)ο蟆?/p>

              具體的說:

              棧與堆都是Java用來在Ram中存放數(shù)據(jù)的地方。與C++不同,Java自動管理?xiàng):投眩绦騿T不能直接地設(shè)置棧或堆。

              Java的堆是一個(gè)運(yùn)行時(shí)數(shù)據(jù)區(qū),類的(對象從中分配空間。這些對象通過new、newarray、anewarray和multianewarray等 指令建立,它們不需要程序代碼來顯式的釋放。堆是由垃圾回收來負(fù)責(zé)的,堆的優(yōu)勢是可以動態(tài)地分配內(nèi)存大小,生存期也不必事先告訴編譯器,因?yàn)樗窃谶\(yùn)行時(shí) 動態(tài)分配內(nèi)存的,Java的垃圾收集器會自動收走這些不再使用的數(shù)據(jù)。但缺點(diǎn)是,由于要在運(yùn)行時(shí)動態(tài)分配內(nèi)存,存取速度較慢。

              棧的優(yōu)勢是,存取速度比堆要快,僅次于寄存器,棧數(shù)據(jù)可以共享。但缺點(diǎn)是,存在棧中的數(shù)據(jù)大小與生存期必須是確定的,缺乏靈活性。棧中主要存放一些基本 類型的變量(,int, short, long, byte, float, double, boolean, char)和對象句柄。

              棧有一個(gè)很重要的特殊性,就是存在棧中的數(shù)據(jù)可以共享。假設(shè)我們同時(shí)定義:

              int a = 3;

              int b = 3;

              編譯器先處理int a = 3;首先它會在棧中創(chuàng)建一個(gè)變量為a的引用,然后查找棧中是否有3這個(gè)值,如果沒找到,就將3存放進(jìn)來,然后將a指向3。接著處理int b = 3;在創(chuàng)建完b的引用變量后,因?yàn)樵跅V幸呀?jīng)有3這個(gè)值,便將b直接指向3。這樣,就出現(xiàn)了a與b同時(shí)均指向3的情況。這時(shí),如果再令a=4;那么編譯器 會重新搜索棧中是否有4值,如果沒有,則將4存放進(jìn)來,并令a指向4;如果已經(jīng)有了,則直接將a指向這個(gè)地址。因此a值的改變不會影響到b的值。要注意這 種數(shù)據(jù)的共享與兩個(gè)對象的引用同時(shí)指向一個(gè)對象的這種共享是不同的,因?yàn)檫@種情況a的修改并不會影響到b, 它是由編譯器完成的,它有利于節(jié)省空間。而一個(gè)對象引用變量修改了這個(gè)對象的內(nèi)部狀態(tài),會影響到另一個(gè)對象引用變量。

              String是一個(gè)特殊的包裝類數(shù)據(jù)。可以用:

              String str = new String("abc");

              String str = "abc";

              兩種的形式來創(chuàng)建,第一種是用new()來新建對象的,它會在存放于堆中。每調(diào)用一次就會創(chuàng)建一個(gè)新的對象。

              而第二種是先在棧中創(chuàng)建一個(gè)對String類的對象引用變量str,然后查找棧中有沒有存放"abc",如果沒有,則將"abc"存放進(jìn)棧,并令str指向“abc”,如果已經(jīng)有“abc” 則直接令str指向“abc”。

              比較類里面的數(shù)值是否相等時(shí),用equals()方法;當(dāng)測試兩個(gè)包裝類的引用是否指向同一個(gè)對象時(shí),用==,下面用例子說明上面的理論。

              String str1 = "abc";

              String str2 = "abc";

              System.out.println(str1==str2); //true可以看出str1和str2是指向同一個(gè)對象的。

              String str1 =new String ("abc");

              String str2 =new String ("abc");

              System.out.println(str1==str2); // false用new的方式是生成不同的對象。每一次生成一個(gè)。

              因此用第二種方式創(chuàng)建多個(gè)“abc”字符串,在內(nèi)存中其實(shí)只存在一個(gè)對象而已. 這種寫法有利與節(jié)省內(nèi)存空間. 同時(shí)它可以在一定程度上提高程序的運(yùn)行速度,因?yàn)镴VM會自動根據(jù)棧中數(shù)據(jù)的實(shí)際情況來決定是否有必要創(chuàng)建新對象。而對于String str = new String("abc");的代碼,則一概在堆中創(chuàng)建新對象,而不管其字符串值是否相等,是否有必要創(chuàng)建新對象,從而加重了程序的負(fù)擔(dān)。

              另一方面, 要注意: 我們在使用諸如String str = "abc";的格式定義類時(shí),總是想當(dāng)然地認(rèn)為,創(chuàng)建了String類的對象str。擔(dān)心陷阱!對象可能并沒有被創(chuàng)建!而可能只是指向一個(gè)先前已經(jīng)創(chuàng)建的 對象。只有通過new()方法才能保證每次都創(chuàng)建一個(gè)新的對象。 由于String類的immutable性質(zhì),當(dāng)String變量需要經(jīng)常變換其值時(shí),應(yīng)該考慮使用StringBuffer類,以提高程序效率。

              java中內(nèi)存分配策略及堆和棧的比較

              2.1 內(nèi)存分配策略按照編譯原理的觀點(diǎn),程序運(yùn)行時(shí)的內(nèi)存分配有三種策略,分別是靜態(tài)的,棧式的,和堆式的.靜態(tài)存儲分配是指在編譯時(shí)就能確定每個(gè)數(shù)據(jù)目標(biāo)在運(yùn)行時(shí)刻的存儲空間需求,因而在編譯時(shí)就可以給他們分配固定的內(nèi)存空間.這種分配策略要求程序代碼中不允 許有可變數(shù)據(jù)結(jié)構(gòu)(比如可變數(shù)組)的存在,也不允許有嵌套或者遞歸的結(jié)構(gòu)出現(xiàn),因?yàn)樗鼈兌紩?dǎo)致編譯程序無法計(jì)算準(zhǔn)確的存儲空間需求.棧式存儲分配也可稱為動態(tài)存儲分配,是由一個(gè)類似于堆棧的運(yùn)行棧來實(shí)現(xiàn)的.和靜態(tài)存儲分配相反,在棧式存儲方案中,程序?qū)?shù)據(jù)區(qū)的需求在編譯時(shí)是完全未知 的,只有到運(yùn)行的時(shí)候才能夠知道,但是規(guī)定在運(yùn)行中進(jìn)入一個(gè)程序模塊時(shí),必須知道該程序模塊所需的數(shù)據(jù)區(qū)大小才能夠?yàn)槠浞峙鋬?nèi)存.和我們在數(shù)據(jù)結(jié)構(gòu)所熟知 的棧一樣,棧式存儲分配按照先進(jìn)后出的原則進(jìn)行分配。

              靜態(tài)存儲分配要求在編譯時(shí)能知道所有變量的存儲要求,棧式存儲分配要求在過程的入口處必須知道所有的存儲要求,而堆式存儲分配則專門負(fù)責(zé)在編譯時(shí)或運(yùn)行時(shí) 模塊入口處都無法確定存儲要求的數(shù)據(jù)結(jié)構(gòu)的內(nèi)存分配,比如可變長度串和對象實(shí)例.堆由大片的可利用塊或空閑塊組成,堆中的內(nèi)存可以按照任意順序分配和釋 放.

              2.2 堆和棧的比較

              上面的定義從編譯原理的教材中總結(jié)而來,除靜態(tài)存儲分配之外,都顯得很呆板和難以理解,下面撇開靜態(tài)存儲分配,集中比較堆和棧:從堆和棧的功能和作用來通俗的比較,堆主要用來存放對象的,棧主要是用來執(zhí)行程序的.而這種不同又主要是由于堆和棧的特點(diǎn)決定的:在編程中,例如C/C++中,所有的方法調(diào)用都是通過棧來進(jìn)行的,所有的局部變量,形式參數(shù)都是從棧中分配內(nèi)存空間的。實(shí)際上也不是什么分配,只是從棧頂 向上用就行,就好像工廠中的傳送帶(conveyor belt)一樣,Stack Pointer會自動指引你到放東西的位置,你所要做的只是把東西放下來就行.退出函數(shù)的時(shí)候,修改棧指針就可以把棧中的內(nèi)容銷毀.這樣的模式速度最快, 當(dāng)然要用來運(yùn)行程序了.需要注意的是,在分配的時(shí)候,比如為一個(gè)即將要調(diào)用的程序模塊分配數(shù)據(jù)區(qū)時(shí),應(yīng)事先知道這個(gè)數(shù)據(jù)區(qū)的大小,也就說是雖然分配是在程 序運(yùn)行時(shí)進(jìn)行的,但是分配的大小多少是確定的,不變的,而這個(gè)"大小多少"是在編譯時(shí)確定的,不是在運(yùn)行時(shí).堆是應(yīng)用程序在運(yùn)行的時(shí)候請求操作系統(tǒng)分配給自己內(nèi)存,由于從操作系統(tǒng)管理的內(nèi)存分配,所以在分配和銷毀時(shí)都要占用時(shí)間,因此用堆的效率非常低.但是堆的 優(yōu)點(diǎn)在于,編譯器不必知道要從堆里分配多少存儲空間,也不必知道存儲的數(shù)據(jù)要在堆里停留多長的時(shí)間,因此,用堆保存數(shù)據(jù)時(shí)會得到更大的靈活性。事實(shí)上,面 向?qū)ο蟮亩鄳B(tài)性,堆內(nèi)存分配是必不可少的,因?yàn)槎鄳B(tài)變量所需的存儲空間只有在運(yùn)行時(shí)創(chuàng)建了對象之后才能確定.在C++中,要求創(chuàng)建一個(gè)對象時(shí),只需用 new命令編制相關(guān)的代碼即可。執(zhí)行這些代碼時(shí),會在堆里自動進(jìn)行數(shù)據(jù)的保存.當(dāng)然,為達(dá)到這種靈活性,必然會付出一定的代價(jià):在堆里分配存儲空間時(shí)會花 掉更長的時(shí)間!這也正是導(dǎo)致我們剛才所說的效率低的原因,看來列寧同志說的好,人的優(yōu)點(diǎn)往往也是人的缺點(diǎn),人的缺點(diǎn)往往也是人的優(yōu)點(diǎn).

              2.3 JVM中的堆和棧JVM是基于堆棧的虛擬機(jī).JVM為每個(gè)新創(chuàng)建的線程都分配一個(gè)堆棧.也就是說,對于一個(gè)Java程序來說,它的運(yùn)行就是通過對堆棧的操作來完成的。堆棧以幀為單位保存線程的狀態(tài)。JVM對堆棧只進(jìn)行兩種操作:以幀為單位的壓棧和出棧操作。

              我們知道,某個(gè)線程正在執(zhí)行的方法稱為此線程的當(dāng)前方法.我們可能不知道,當(dāng)前方法使用的幀稱為當(dāng)前幀。當(dāng)線程激活一個(gè)Java方法,JVM就會在線程的 Java堆棧里新壓入一個(gè)幀。這個(gè)幀自然成為了當(dāng)前幀.在此方法執(zhí)行期間,這個(gè)幀將用來保存參數(shù),局部變量,中間計(jì)算過程和其他數(shù)據(jù).這個(gè)幀在這里和編譯 原理中的活動紀(jì)錄的概念是差不多的.從Java的這種分配機(jī)制來看,堆棧又可以這樣理解:堆棧(Stack)是操作系統(tǒng)在建立某個(gè)進(jìn)程時(shí)或者線程(在支持多線程的操作系統(tǒng)中是線程)為這個(gè)線程建立的存儲區(qū)域,該區(qū)域具有先進(jìn)后出的特性。

              每一個(gè)Java應(yīng)用都唯一對應(yīng)一個(gè)JVM實(shí)例,每一個(gè)實(shí)例唯一對應(yīng)一個(gè)堆。應(yīng)用程序在運(yùn)行中所創(chuàng)建的所有類實(shí)例或數(shù)組都放在這個(gè)堆中,并由應(yīng)用所有的線程 共享.跟C/C++不同,Java中分配堆內(nèi)存是自動初始化的。Java中所有對象的存儲空間都是在堆中分配的,但是這個(gè)對象的引用卻是在堆棧中分配,也 就是說在建立一個(gè)對象時(shí)從兩個(gè)地方都分配內(nèi)存,在堆中分配的內(nèi)存實(shí)際建立這個(gè)對象,而在堆棧中分配的內(nèi)存只是一個(gè)指向這個(gè)堆對象的指針(引用)而已。

          posted @ 2009-10-12 21:22 小強(qiáng)摩羯座 閱讀(192) | 評論 (0)編輯 收藏


          在《編程珠璣》中有詳細(xì)的討論。主要出于性能方向改進(jìn)。

          1. 二分法很簡單吧 ,但要想 一次寫對  也不容易吧 ,更何況他的一些擴(kuò)展應(yīng)用呢 ,我這里擴(kuò)展了四種,<P> </P><P>基礎(chǔ)知識 還是牢靠的好</P><P> </P>  
          1. /**  
          2.  * Author: yiminghe  
          3.  * Date: 2008-10-13  
          4.  * Time: 23:50:48  
          5.  * Any problem ,contact yiminghe@fudan.edu.cn.  
          6.  */  
          7. public class BinarySearch {   
          8.   
          9.     //返回中間一個(gè)數(shù)   
          10.     //12345666689   
          11.     // 6  不確定返回哪個(gè)6   
          12.     public static int b1(int[] array, int v) {   
          13.         int left = 0;   
          14.         int right = array.length - 1;   
          15.         while (left <= right) {   
          16.             int middle = (left + right) / 2;   
          17.             if (array[middle] == v) return middle;   
          18.             if (array[middle] > v)   
          19.                 right = middle - 1;   
          20.             else  
          21.                 left = middle + 1;   
          22.         }   
          23.   
          24.         return -1;   
          25.   
          26.     }   
          27.   
          28.     //返回重復(fù)元素的最后一個(gè)數(shù)   
          29.     //123456667   
          30.     //最后一個(gè)6位置返回    
          31.     public static int b2(int[] array, int v) {   
          32.         int left = 0;   
          33.         int right = array.length - 1;   
          34.         while (left < right) {   
          35.             int middle = (left + right + 1) / 2;   
          36.             if (array[middle] > v)   
          37.                 right = middle - 1;   
          38.             else  
          39.                 left = middle;   
          40.         }   
          41.   
          42.         if (array[left] == v)   
          43.             return left;   
          44.   
          45.         return -1;   
          46.   
          47.     }   
          48.   
          49.   
          50.     //返回重復(fù)元素的最前一個(gè)數(shù)   
          51.     //123456667   
          52.     //最前一個(gè)6位置返回   
          53.     public static int b3(int[] array, int v) {   
          54.         int left = 0;   
          55.         int right = array.length - 1;   
          56.         while (left < right) {   
          57.             int middle = (left + right) / 2;   
          58.             if (array[middle] < v)   
          59.                 left = middle + 1;   
          60.             else  
          61.                 right = middle;   
          62.         }   
          63.   
          64.         if (array[right] == v)   
          65.             return right;   
          66.   
          67.         return -1;   
          68.   
          69.     }   
          70.   
          71.   
          72.     //返回重復(fù)元素的最前一個(gè)數(shù)   
          73.     //1234566689   
          74.     //最前一個(gè)6位置返回 ,若找不到,顯示 比他小的離它最大位置,比它小的離它最小位置   
          75.     //如 找 7 ,則 輸出 最后一個(gè)6的位置 和 8 的位置   
          76.     public static int b4(int[] array, int v, int flag) {   
          77.         int left = 0;   
          78.         int right = array.length - 1;   
          79.         while (left < right) {   
          80.             int middle = (left + right) / 2;   
          81.             if (array[middle] < v)   
          82.                 left = middle + 1;   
          83.             else  
          84.                 right = middle;   
          85.         }   
          86.   
          87.   
          88.         if (array[right] == v)   
          89.             return right;   
          90.         System.out.println(right - 1 + "  -- " + left);   
          91.         return -1;   
          92.   
          93.     }   
          94.   
          95.   
          96.     public static void main(String[] args) {   
          97.         //                       0, 1, 2, 3  4  5  6  7   
          98.         int[] array = new int[]{12341016161616161618110};   
          99.         //array = new int[]{0, 6};   
          100.         //array = new int[]{6, 7};   
          101.         System.out.println(b1(array, 16));   
          102.         System.out.println(b2(array, 16));   
          103.         System.out.println(b3(array, 16));   
          104.         System.out.println(b4(array, 61));   
          105.   
          106.   
          107.     }   
          108. }  

           


          posted @ 2009-09-30 23:47 小強(qiáng)摩羯座 閱讀(90) | 評論 (0)編輯 收藏

          Java AIO初探(異步網(wǎng)絡(luò)IO) 

            按照《Unix網(wǎng)絡(luò)編程》的劃分,IO模型可以分為:阻塞IO、非阻塞IO、IO復(fù)用、信號驅(qū)動IO和異步IO,按照POSIX標(biāo)準(zhǔn)來劃分只分為兩類:同步IO和異步IO.如何區(qū)分呢?首先一個(gè)IO操作其實(shí)分成了兩個(gè)步驟:發(fā)起IO請求和實(shí)際的IO操作,同步IO和異步IO的區(qū)別就在于第二個(gè)步驟是否阻塞,如果實(shí)際的IO讀寫阻塞請求進(jìn)程,那么就是同步IO,因此阻塞IO、非阻塞IO、IO服用、信號驅(qū)動IO都是同步IO,如果不阻塞,而是操作系統(tǒng)幫你做完IO操作再將結(jié)果返回給你,那么就是異步IO.阻塞IO和非阻塞IO的區(qū)別在于第一步,發(fā)起IO請求是否會被阻塞,如果阻塞直到完成那么就是傳統(tǒng)的阻塞IO,如果不阻塞,那么就是非阻塞IO.

              Java nio 2.0的主要改進(jìn)就是引入了異步IO(包括文件和網(wǎng)絡(luò)),這里主要介紹下異步網(wǎng)絡(luò)IO API的使用以及框架的設(shè)計(jì),以TCP服務(wù)端為例。首先看下為了支持AIO引入的新的類和接口:

              java.nio.channels.AsynchronousChannel標(biāo)記一個(gè)channel支持異步IO操作。

              java.nio.channels.AsynchronousServerSocketChannel ServerSocket的aio版本,創(chuàng)建TCP服務(wù)端,綁定地址,監(jiān)聽端口等。

              java.nio.channels.AsynchronousSocketChannel面向流的異步socket channel,表示一個(gè)連接。

              java.nio.channels.AsynchronousChannelGroup異步channel的分組管理,目的是為了資源共享。一個(gè)AsynchronousChannelGroup綁定一個(gè)線程池,這個(gè)線程池執(zhí)行兩個(gè)任務(wù):處理IO事件和派發(fā)CompletionHandler.AsynchronousServerSocketChannel創(chuàng)建的時(shí)候可以傳入一個(gè)AsynchronousChannelGroup,那么通過AsynchronousServerSocketChannel創(chuàng)建的AsynchronousSocketChannel將同屬于一個(gè)組,共享資源。

              java.nio.channels.CompletionHandler異步IO操作結(jié)果的回調(diào)接口,用于定義在IO操作完成后所作的回調(diào)工作。AIO的API允許兩種方式來處理異步操作的結(jié)果:返回的Future模式或者注冊CompletionHandler,我更推薦用CompletionHandler的方式,這些handler的調(diào)用是由AsynchronousChannelGroup的線程池派發(fā)的。顯然,線程池的大小是性能的關(guān)鍵因素。AsynchronousChannelGroup允許綁定不同的線程池,通過三個(gè)靜態(tài)方法來創(chuàng)建:public static AsynchronousChannelGroup withFixedThreadPool(int nThreads,

              ThreadFactory threadFactory)

              throws IOException

              public static AsynchronousChannelGroup withCachedThreadPool(ExecutorService executor,

              int initialSize)

              public static AsynchronousChannelGroup withThreadPool(ExecutorService executor)

              throws IOException

              需要根據(jù)具體應(yīng)用相應(yīng)調(diào)整,從框架角度出發(fā),需要暴露這樣的配置選項(xiàng)給用戶。

              在介紹完了aio引入的TCP的主要接口和類之后,我們來設(shè)想下一個(gè)aio框架應(yīng)該怎么設(shè)計(jì)。參考非阻塞nio框架的設(shè)計(jì),一般都是采用Reactor模式,Reacot負(fù)責(zé)事件的注冊、select、事件的派發(fā);相應(yīng)地,異步IO有個(gè)Proactor模式,Proactor負(fù)責(zé)CompletionHandler的派發(fā),查看一個(gè)典型的IO寫操作的流程來看兩者的區(qū)別:

              Reactor:  send(msg) -> 消息隊(duì)列是否為空,如果為空  -> 向Reactor注冊O(shè)P_WRITE,然后返回 -> Reactor select -> 觸發(fā)Writable,通知用戶線程去處理 ->先注銷Writable(很多人遇到的cpu 100%的問題就在于沒有注銷),處理Writeable,如果沒有完全寫入,繼續(xù)注冊O(shè)P_WRITE.注意到,寫入的工作還是用戶線程在處理。

              Proactor: send(msg) -> 消息隊(duì)列是否為空,如果為空,發(fā)起read異步調(diào)用,并注冊CompletionHandler,然后返回。 -> 操作系統(tǒng)負(fù)責(zé)將你的消息寫入,并返回結(jié)果(寫入的字節(jié)數(shù))給Proactor -> Proactor派發(fā)CompletionHandler.可見,寫入的工作是操作系統(tǒng)在處理,無需用戶線程參與。事實(shí)上在aio的API中,AsynchronousChannelGroup就扮演了Proactor的角色。

              CompletionHandler有三個(gè)方法,分別對應(yīng)于處理成功、失敗、被取消(通過返回的Future)情況下的回調(diào)處理:

              public interface CompletionHandler {

              void completed(V result, A attachment);

              void failed(Throwable exc, A attachment);

              void cancelled(A attachment);

              }

              其中的泛型參數(shù)V表示IO調(diào)用的結(jié)果,而A是發(fā)起調(diào)用時(shí)傳入的attchment.

              在初步介紹完aio引入的類和接口后,我們看看一個(gè)典型的tcp服務(wù)端是怎么啟動的,怎么接受連接并處理讀和寫,這里引用的代碼都是yanf4j 的aio分支中的代碼,可以從svn checkout,svn地址: http://yanf4j.googlecode.com/svn/branches/yanf4j-aio

              第一步,創(chuàng)建一個(gè)AsynchronousServerSocketChannel,創(chuàng)建之前先創(chuàng)建一個(gè)AsynchronousChannelGroup,上文提到AsynchronousServerSocketChannel可以綁定一個(gè)AsynchronousChannelGroup,那么通過這個(gè)AsynchronousServerSocketChannel建立的連接都將同屬于一個(gè)AsynchronousChannelGroup并共享資源:this.asynchronousChannelGroup = AsynchronousChannelGroup。withCachedThreadPool(Executors.newCachedThreadPool(),this.threadPoolSize);然后初始化一個(gè)AsynchronousServerSocketChannel,通過open方法:this.serverSocketChannel = AsynchronousServerSocketChannel。open(this.asynchronousChannelGroup);通過nio 2.0引入的SocketOption類設(shè)置一些TCP選項(xiàng):this.serverSocketChannel。setOption(StandardSocketOption.SO_REUSEADDR,true);this.serverSocketChannel。setOption(StandardSocketOption.SO_RCVBUF,16*1024);

              綁定本地地址:

              this.serverSocketChannel。bind(new InetSocketAddress("localhost",8080), 100);其中的100用于指定等待連接的隊(duì)列大小(backlog)。完了嗎?還沒有,最重要的監(jiān)聽工作還沒開始,監(jiān)聽端口是為了等待連接上來以便accept產(chǎn)生一個(gè)AsynchronousSocketChannel來表示一個(gè)新建立的連接,因此需要發(fā)起一個(gè)accept調(diào)用,調(diào)用是異步的,操作系統(tǒng)將在連接建立后,將最后的結(jié)果——AsynchronousSocketChannel返回給你:

              public void pendingAccept(){

              if (this.started  this.serverSocketChannel.isOpen()) { this.acceptFuture = this.serverSocketChannel.accept(null,

              new AcceptCompletionHandler());

              } else {

              throw new IllegalStateException("Controller has been closed");

              }

              注意,重復(fù)的accept調(diào)用將會拋出PendingAcceptException,后文提到的read和write也是如此。accept方法的第一個(gè)參數(shù)是你想傳給CompletionHandler的attchment,第二個(gè)參數(shù)就是注冊的用于回調(diào)的CompletionHandler,最后返回結(jié)果Future.你可以對future做處理,這里采用更推薦的方式就是注冊一個(gè)CompletionHandler.那么accept的CompletionHandler中做些什么工作呢?顯然一個(gè)赤裸裸的AsynchronousSocketChannel是不夠的,我們需要將它封裝成session,一個(gè)session表示一個(gè)連接(mina里就叫IoSession了),里面帶了一個(gè)緩沖的消息隊(duì)列以及一些其他資源等。在連接建立后,除非你的服務(wù)器只準(zhǔn)備接受一個(gè)連接,不然你需要在后面繼續(xù)調(diào)用pendingAccept來發(fā)起另一個(gè)accept請求:

              private final class AcceptCompletionHandler implements

              CompletionHandler {

              @Override

              public void cancelled(Object attachment){

              logger.warn("Accept operation was canceled");

              }

            @Override

              public void completed(AsynchronousSocketChannel socketChannel,

              Object attachment){

              try {

              logger.debug("Accept connection from " + socketChannel.getRemoteAddress());

              configureChannel(socketChannel);

              AioSessionConfig sessionConfig = buildSessionConfig(socketChannel);

              Session session = new AioTCPSession(sessionConfig,AioTCPController.this.configuration。getSessionReadBufferSize(),AioTCPController.this.sessionTimeout);session.start();

              registerSession(session);

              } catch(Exception e){

              e.printStackTrace();logger.error("Accept error", e);

              notifyException(e);

              } finally {

              pendingAccept();

              }

              @Override

              public void failed(Throwable exc, Object attachment) { logger.error("Accept error", exc);

              try {

              notifyException(exc);

              } finally {

              pendingAccept();

              }

              注意到了吧,我們在failed和completed方法中在最后都調(diào)用了pendingAccept來繼續(xù)發(fā)起accept調(diào)用,等待新的連接上來。有的同學(xué)可能要說了,這樣搞是不是遞歸調(diào)用,會不會堆棧溢出?實(shí)際上不會,因?yàn)榘l(fā)起accept調(diào)用的線程與CompletionHandler回調(diào)的線程并非同一個(gè),不是一個(gè)上下文中,兩者之間沒有耦合關(guān)系。要注意到,CompletionHandler的回調(diào)共用的是AsynchronousChannelGroup綁定的線程池,因此千萬別在回調(diào)方法中調(diào)用阻塞或者長時(shí)間的操作,例如sleep,回調(diào)方法最好能支持超時(shí),防止線程池耗盡。

              連接建立后,怎么讀和寫呢?回憶下在nonblocking nio框架中,連接建立后的第一件事是干什么?注冊O(shè)P_READ事件等待socket可讀。異步IO也同樣如此,連接建立后馬上發(fā)起一個(gè)異步read調(diào)用,等待socket可讀,這個(gè)是Session.start方法中所做的事情:

              public class AioTCPSession {

              protected void start0(){

              pendingRead();

              }

              protected final void pendingRead(){

              if (!isClosed()  this.asynchronousSocketChannel.isOpen()) { if (!this.readBuffer.hasRemaining()) { this.readBuffer = ByteBufferUtils。increaseBufferCapatity(this.readBuffer);

              }

              this.readFuture = this.asynchronousSocketChannel.read(this.readBuffer, this, this.readCompletionHandler);

              } else {

              throw new IllegalStateException(

              "Session Or Channel has been closed");

              }

              }

              AsynchronousSocketChannel的read調(diào)用與AsynchronousServerSocketChannel的accept調(diào)用類似,同樣是非阻塞的,返回結(jié)果也是一個(gè)Future,但是寫的結(jié)果是整數(shù),表示寫入了多少字節(jié),因此read調(diào)用返回的是Future,方法的第一個(gè)參數(shù)是讀的緩沖區(qū),操作系統(tǒng)將IO讀到數(shù)據(jù)拷貝到這個(gè)緩沖區(qū),第二個(gè)參數(shù)是傳遞給CompletionHandler的attchment,第三個(gè)參數(shù)就是注冊的用于回調(diào)的CompletionHandler.這里保存了read的結(jié)果Future,這是為了在關(guān)閉連接的時(shí)候能夠主動取消調(diào)用,accept也是如此。現(xiàn)在可以看看read的CompletionHandler的實(shí)現(xiàn):

              public final class ReadCompletionHandler implements

              CompletionHandler {

              private static final Logger log = LoggerFactory

              。getLogger(ReadCompletionHandler.class);

              protected final AioTCPController controller;

              public ReadCompletionHandler(AioTCPController controller){

              this.controller = controller;

              }

              @Override

              public void cancelled(AbstractAioSession session){

              log.warn("Session(" + session.getRemoteSocketAddress()

              + ")read operation was canceled");

              }

              @Override

              public void completed(Integer result, AbstractAioSession session) { if (log.isDebugEnabled())

              log.debug("Session(" + session.getRemoteSocketAddress()

              + ")read +" + result + " bytes");

              if(result 0){

              session.updateTimeStamp();session.getReadBuffer()。flip();session.decode();session.getReadBuffer()。compact();

              }

              } finally {

              try {

              session.pendingRead();

              } catch(IOException e){

              session.onException(e);session.close();

              }

              controller.checkSessionTimeout();

              }

              @Override

              public void failed(Throwable exc, AbstractAioSession session) { log.error("Session read error", exc);session.onException(exc);session.close();

              }

              }

           如果IO讀失敗,會返回失敗產(chǎn)生的異常,這種情況下我們就主動關(guān)閉連接,通過session.close()方法,這個(gè)方法干了兩件事情:關(guān)閉channel和取消read調(diào)用:if (null != this.readFuture) { this.readFuture.cancel(true);

              }

              this.asynchronousSocketChannel.close();   在讀成功的情況下,我們還需要判斷結(jié)果result是否小于0,如果小于0就表示對端關(guān)閉了,這種情況下我們也主動關(guān)閉連接并返回。如果讀到一定字節(jié),也就是result大于0的情況下,我們就嘗試從讀緩沖區(qū)中decode出消息,并派發(fā)給業(yè)務(wù)處理器的回調(diào)方法,最終通過pendingRead繼續(xù)發(fā)起read調(diào)用等待socket的下一次可讀。可見,我們并不需要自己去調(diào)用channel來進(jìn)行IO讀,而是操作系統(tǒng)幫你直接讀到了緩沖區(qū),然后給你一個(gè)結(jié)果表示讀入了多少字節(jié),你處理這個(gè)結(jié)果即可。而nonblocking IO框架中,是reactor通知用戶線程socket可讀了,然后用戶線程自己去調(diào)用read進(jìn)行實(shí)際讀操作。這里還有個(gè)需要注意的地方,就是decode出來的消息的派發(fā)給業(yè)務(wù)處理器工作最好交給一個(gè)線程池來處理,避免阻塞group綁定的線程池。

              IO寫的操作與此類似,不過通常寫的話我們會在session中關(guān)聯(lián)一個(gè)緩沖隊(duì)列來處理,沒有完全寫入或者等待寫入的消息都存放在隊(duì)列中,隊(duì)列為空的情況下發(fā)起write調(diào)用:

              protected void write0(WriteMessage message){

              boolean needWrite = false;

              synchronized (this.writeQueue) { needWrite = this.writeQueue.isEmpty();this.writeQueue.offer(message);

              }

              if(needWrite){

              pendingWrite(message);

              }

              protected final void pendingWrite(WriteMessage message){

              message = preprocessWriteMessage(message);

              if (!isClosed()  this.asynchronousSocketChannel.isOpen()) { this.asynchronousSocketChannel.write(message.getWriteBuffer(),this, this.writeCompletionHandler);

              } else {

              throw new IllegalStateException(

              "Session Or Channel has been closed");

              }

              write調(diào)用返回的結(jié)果與read一樣是一個(gè)Future,而write的CompletionHandler處理的核心邏輯大概是這樣:

              @Override

              public void completed(Integer result, AbstractAioSession session) { if (log.isDebugEnabled())

              log.debug("Session(" + session.getRemoteSocketAddress()

              + ")writen " + result + " bytes");

              WriteMessage writeMessage;

              Queue writeQueue = session.getWriteQueue();

              synchronized(writeQueue){

              writeMessage = writeQueue.peek();if (writeMessage.getWriteBuffer() == null || !writeMessage.getWriteBuffer()。hasRemaining()) { writeQueue.remove();if (writeMessage.getWriteFuture() != null) { writeMessage.getWriteFuture()。setResult(Boolean.TRUE);

              }

              try {

              session.getHandler()。onMessageSent(session,writeMessage.getMessage());

              } catch(Exception e){

              session.onException(e);

              }

              writeMessage = writeQueue.peek();

              }

              if (writeMessage != null) {

              try {

              session.pendingWrite(writeMessage);

              } catch(IOException e){

              session.onException(e);session.close();

              }

              compete方法中的result就是實(shí)際寫入的字節(jié)數(shù),然后我們判斷消息的緩沖區(qū)是否還有剩余,如果沒有就將消息從隊(duì)列中移除,如果隊(duì)列中還有消息,那么繼續(xù)發(fā)起write調(diào)用。

              重復(fù)一下,這里引用的代碼都是yanf4j aio分支中的源碼,感興趣的朋友可以直接check out出來看看: http://yanf4j.googlecode.com/svn/branches/yanf4j-aio.在引入了aio之后,java對于網(wǎng)絡(luò)層的支持已經(jīng)非常完善,該有的都有了,java也已經(jīng)成為服務(wù)器開發(fā)的首選語言之一。java的弱項(xiàng)在于對內(nèi)存的管理上,由于這一切都交給了GC,因此在高性能的網(wǎng)絡(luò)服務(wù)器上還是Cpp的天下。java這種單一堆模型比之erlang的進(jìn)程內(nèi)堆模型還是有差距,很難做到高效的垃圾回收和細(xì)粒度的內(nèi)存管理。

              這里僅僅是介紹了aio開發(fā)的核心流程,對于一個(gè)網(wǎng)絡(luò)框架來說,還需要考慮超時(shí)的處理、緩沖buffer的處理、業(yè)務(wù)層和網(wǎng)絡(luò)層的切分、可擴(kuò)展性、性能的可調(diào)性以及一定的通用性要求。

          posted @ 2009-09-21 22:22 小強(qiáng)摩羯座 閱讀(286) | 評論 (0)編輯 收藏


          generic points to List<String> , List is called raw type here, and <String> is the parametered type.

          Generic's functions are :
          1. remove type cast;
          2. typesafe programming;

          The key question of Generic:
          1. the inheritance attribute of OO is not support: List<String> is not a type of List<Object>。

          2. Collection<?> c: the parametered type is unknown. so you cant add elem into c.but you may get the elem in c and we know they are of type Object.

          3、類型推斷

          static  < T >   void  fromArrayToCollection(T[] a, Collection  <  T  >  c)   

             
          for  (T o : a)   
                   c.add(o);  
          //  correct  
                }
           
           }

            對這個(gè)方法參數(shù)化類型T,由定義數(shù)據(jù)a和Collection時(shí)傳入的共同決定,它們可以使用相同類型,也可以使用不同類型,當(dāng)類型不同時(shí),它們必須有繼承關(guān)系,類型推斷時(shí)使用較高的那個(gè)。
          4, when to use <?> or <T> :他們主要用在泛型方法,T相比?,它有名稱,可多次使用來表達(dá)依賴關(guān)系。所以在不表達(dá)依賴關(guān)系的地方就應(yīng)該使用?。它簡單、靈活。

          而且有趣的是,它們并非水火不容,反而可以精妙配合,如下:  

           

          1  class Collections 
          2
          3  public static < T > void copy(List < T > dest, List < ? extends T > src) {  } 
          4
          5}
           

           

          這個(gè)合作使得dest src 的依賴關(guān)系得以表達(dá),同時(shí)讓 src 的接納范疇擴(kuò)大了。假如我們只用泛型方法來實(shí)現(xiàn):  

           

          1  class Collections 
          2
          3   public static < T, S extends T > void copy(List < T > dest, List < S > src) {  } 
          4
          5}
           

           

          那么S 的存在就顯得有些不必要,有些不優(yōu)雅。總的來說,通配符更簡潔清晰,只要情況允許就應(yīng)該首選。

          5、由于普通數(shù)組是協(xié)變的,而GenricType由于List<String>不是List<Object>的子類型,所以它不能協(xié)變。可以使用?來new 一個(gè)數(shù)組。但是通常new完就要加元素,而?類型未知不可以產(chǎn)生對象的。所以最后使用Class<T> 類型做形參,實(shí)參用T.class就可以。這就是為什么Hibernate.load和get中會使用的.class的用法。比較新知識點(diǎn)是String.class就是Class<String>(String.class稱字面類常量)。當(dāng)傳入Class<T> c 對象后,可以利用reflect來構(gòu)造對象,并作狀態(tài)設(shè)置。


          posted @ 2009-08-15 16:15 小強(qiáng)摩羯座 閱讀(267) | 評論 (0)編輯 收藏

          僅列出標(biāo)題
          共20頁: First 上一頁 2 3 4 5 6 7 8 9 10 下一頁 Last 
          主站蜘蛛池模板: 曲靖市| 土默特左旗| 屯门区| 乳山市| 项城市| 长治县| 兰溪市| 荃湾区| 望都县| 夏邑县| 武鸣县| 萨迦县| 中山市| 连平县| 建昌县| 怀柔区| 阳原县| 太白县| 中山市| 虹口区| 河北省| 衡东县| 湖口县| 屏东县| 峨眉山市| 沂源县| 宕昌县| 厦门市| 陆良县| 永川市| 巴东县| 民勤县| 广东省| 宁陕县| 南皮县| 朝阳县| 鹤岗市| 洪江市| 宜都市| 东安县| 凌云县|