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

最大公约数和最小公倍数

语言: C, 标签: 无  2008/07/22发布 5个月前更新 更新记录
作者: 半瓶墨水, 点击5221次, 评论(0), 收藏者(0), , 打分:登录以后才能打分, 目前平均0.0分,总分0, 共有0个用户参与打分
# 以下描述来自: http://baike.baidu.com/view/47637.htm
#
# 最大公约数(greatest common divisor,简写为gcd;
# 指某几个整数共有公约数中的最大一个
#  例: 在2、4、6中,2就是2,4,6的最大公约数。
#
# 重要性质:
# 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)
# 如果有附加的一个自然数m,
# 则: gcd(ma,mb)=m * gcd(a,b) (分配率)
# gcd(a+mb ,b)=gcd(a,b)
# 如果m是a和b的最大公约数,
# 则: gcd(a/m ,b/m)=gcd(a,b)/m
# 在乘法函数中有:
# gcd(ab,m)=gcd(a,m) * gcd(b,m)
# 两个整数的最大公约数主要有两种寻找方法:
# * 两数各分解质因子,然后取出同样有的项乘起来
# * 辗转相除法(扩展版)
# 和最小公倍数(lcm)的关系:
# gcd(a, b) * lcm(a, b) = ab
# a与b有最大公约数,但不一定有最小公倍数。
# 两个整数的最大公因子可用于计算两数的最小公倍数,或分数化简成最简分数。
# 两个整数的最大公因子和最小公倍数中存在分配律:
# * gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
# * lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))
# 在坐标里,将点(0, 0)和(a, b)连起来,通过整数坐标的点的数目(除了(0, 0)一点之外)就是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 小强摩羯座 阅读(285) | 评论 (0)编辑 收藏

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

posted @ 2009-10-26 11:53 小强摩羯座 阅读(174) | 评论 (0)编辑 收藏

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

posted @ 2009-10-26 11:39 小强摩羯座 阅读(173) | 评论 (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 小强摩羯座 阅读(187) | 评论 (0)编辑 收藏

转]怎样做人
1、不要推卸责任,哪怕是别人的责任。无论发生任何事情,首先想到自己是不是做错了。如果自己没错(那是不可能的),那就站在对方的角度上,体验一下对方的感受。(本人将此点放在第一条是提醒自己永远都要带着责任心去做事)
2、要让自己适应环境,而不是让环境来适应你。哪怕这是一个非常痛苦的过程。新到一个地方不要急于融入到其中的哪一个圈子中去,等到了足够的时间和考验,属于你的圈子自然就会接纳你。(本人十几年跳到过的地方多不胜数,这是一条最宝贵的原则)
3、大方一点,不会大方就学大方一点。如果大方让你很心痛,你就装大方一点。(不怕大家笑话,我最大方)
4、低调一点,再低调一点,永远低调一点(要比临时工还要低调一点,可能在别人的眼光中你还不如一个新来的临时工呢,本人还没完全做的到)。
5、嘴甜且不吝惜自己的喝彩声,要会夸人,好的夸奖让人觉得很舒服,但不要过份让人反感。(呵呵,这点我就不太行了,不过还可以)
6、如果你觉得最近工作顺利的不得了,那你就要更加小心了。(顺境思危,本人自信做的还行吧
7、礼貌对待人,打招呼的时候要看着对方的眼睛。永远记着自己就是一个不者不扣的小字辈。(做人起码的原则)
8、言多必失,少说多做,人多的场合少说话。(本人吃的亏太多了,这个原则是用教训换来的)
9、不要把别人的好,当做理所当然,要知道感恩图报。(中国人的优秀传统不要忘记了)
10、手高眼低,要有平常心。(没有什么大不了的,好事呀往坏处想,坏事要往好处想,塞翁失马,祸福难测啊)
11、遵守时间,但不要期待别人同样遵守时间。(对自己永远严格要求不会错)
12、信守诺言,但不要轻易许诺,更不要把别人的对你的承诺记在心里并信以为真。(本人提醒大家就算要承诺也要承诺永远做不到的,呵呵)
13、不要向同事借钱,如果借了那就要准时还;不要借钱给同事,如果不得不借,就当作是送给他的好了。(呵呵,别把金钱看的太重,不过没钱万万不能)
14、如果你带领一个团队,在总结工作时要把错误揽在自己的身上,把功劳都记在下属的头上。当上司和下属同时在场的时候你要记得及时表扬你的下属。(批评人的时候一定要在只有你们两个人的情况下才能进行,保持团队的凝聚力最重要)
15、不要在一个同事面前不要说另外一个同事的坏话,要坚持说人的好话,别担心这好话传不到对方的耳中。如果有人在你面前说其他人的坏话,你要保持正常的微笑,不参与评论。(流言止于己,祸从口出是至理名言)
16、避免与同事公开对立,包括公开提出反对意见,激烈的更不可取。(两虎相争,必有一伤,坚持具备平衡的做人处事能力就会自然化解反对意见)
17、经常帮助别人,但是不要让对方觉得是你理所当然应该做的。(好心有时候不会有好结果,但不能因此而灰心,天长地久见人心,一句话:苦心人,天不误!)
18、说实在话会让你倒足八辈子的霉。(本人吃的亏就是一种财富,这是必须坚持的原则)
19、做事先做人,对事不对人;对事无情,同时对人要有情。(公平、公正、公开)
20、经常检查自己是不是又骄傲了,又自负了,又看不起别人了。(一个人再有天大的本事,如果没有别人的合作和帮助都是白搭)
21、忍耐是人生一辈子要修炼的一门功课,要用一辈子的时间去学。(张家名言:张公百忍,另有“百忍堂”为证)
22、尽量不要和同事发生有什么办公室恋情,如果实在避免不了的话,那就在办公室避免任何形式的接触,包括眼神。(兔子不吃窝边草,烦恼总是从身边开始的)
23、待上以敬,待下以宽。(要会拍上司的马屁,这是和上司沟通的重要途径之一,但千万不要弄脏了手)
24、资历非常重要,不要和老家伙们耍心眼斗法,否则你会死的很难看。(中国的社会传统,不会有错)

posted @ 2009-10-25 14:51 小强摩羯座 阅读(184) | 评论 (0)编辑 收藏

最长递增子序列的求法 LIS (转)

什么是最长递增子序列呢?
问题描述如下:
   设L=<a1,a2,…,an>是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>,其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
对于这个问题有以下几种解决思路:
   1、把a1,a2,...,an排序,假设得到a'1,a'2,...,a'n,然后求a的a'的最长公共子串,这样总的时间复杂度为o(nlg(n))+o(n^2)=o(n^2);
   2、动态规划的思路:
    另设一辅助数组b,定义b[n]表示以a[n]结尾的最长递增子序列的长度,则状态转移方程如下:b[k]=max(max(b[j]|a[j]<a[k],j<k)+1,1);
    这个状态转移方程解释如下:在a[k]前面找到满足a[j]<a[k]的最大b[j],然后把a[k]接在它的后面,可得到a[k]的最长递增子序列的长度,或者a[k]前面没有比它小的a[j],那么这时a[k]自成一序列,长度为1.最后整个数列的最长递增子序列即为max(b[k]   | 0<=k<=n-1);
    实现代码如下:
    

#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]结尾的最长递增子序列长度为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++)//求出整个数列的最长递增子序列的长度

                     if(b[i]>max)

                            max=b[i];

              cout<<max<<endl;

       }

       return 0;

}

    显然,这种方法的时间复杂度仍为o(n^2);
   3、对第二种思路的改进:
    第二种思路在状态转移时的复杂度为o(n),即在找a[k]前面满足a[j]<a[k]的最大b[j]时采用的是顺序查找的方法,复杂度为o(n).
    设想如果能把顺序查找改为折半查找,则状态转移时的复杂度为o(lg(n)),这个问题的总的复杂度就可以降到nlg(n).
    另定义一数组c,c中元素满足c[b[k]]=a[k],解释一下,即当递增子序列的长度为b[k]时子序列的末尾元素为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;

}

    对于这段程序,我们可以用算法导论上的loop invariants来帮助理解.
    loop invariant: 1、每次循环结束后c都是单调递增的。(这一性质决定了可以用二分查找)
                           2、每次循环后,c[i]总是保存长度为i的递增子序列的最末的元素,若长度为i的递增子序

                                  列有多个,刚保存末尾元素最小的那个.(这一性质决定是第3条性质成立的前提)
                           3、每次循环完后,b[i]总是保存以a[i]结尾的最长递增子序列。
    initialization:    1、进入循环之前,c[0]=-1,c[1]=a[0],c的其他元素均为1000,c是单调递增的;
                           2、进入循环之前,c[1]=a[0],保存了长度为1时的递增序列的最末的元素,且此时长度为1

                                 的递增了序列只有一个,c[1]也是最小的;
                           3、进入循环之前,b[0]=1,此时以a[0]结尾的最长递增子序列的长度为1.
    maintenance:   1、若在第n次循环之前c是单调递增的,则第n次循环时,c的值只在第6行发生变化,而由

                                c进入循环前单调递增及find函数的性质可知(见find的注释),

                                 此时c[j+1]>c[j]>=a[i]>c[j-1],所以把c[j]的值更新为a[i]后,c[j+1]>c[j]>c[j-1]的性质仍然成

                                立,即c仍然是单调递增的;
                           2、循环中,c的值只在第6行发生变化,由c[j]>=a[i]可知,c[j]更新为a[i]后,c[j]的值只会变

                                  小不会变大,因为进入循环前c[j]的值是最小的,则循环中把c[j]更新为更小的a[i],当

                                 然此时c[j]的值仍是最小的;
                           3、循环中,b[i]的值在第7行发生了变化,因为有loop invariant的性质2,find函数返回值

                                为j有:c[j-1]<a[i]<=c[j],这说明c[j-1]是小于a[i]的,且以c[j-1]结尾的递增子序列有最大的

                               长度,即为j-1,把a[i]接在c[j-1]后可得到以a[i]结尾的最长递增子序列,长度为(j-1)+1=j;
    termination:       循环完后,i=n-1,b[0],b[1],...,b[n-1]的值均已求出,即以a[0],a[1],...,a[n-1]结尾的最长递

                              增子序列的长度均已求出,再通过第8行的循环,即求出了整个数组的最长递增子序列。

          仔细分析上面的代码可以发现,每次循环结束后,假设已经求出c[1],c[2],c[3],...,c[len]的值,则此时最长递增子序列的长度为len,因此可以把上面的代码更加简化,即可以不需要数组b来辅助存储,第8行的循环也可以省略。
    

#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,用来储存每次循环结束后c中已经求出值的元素的最大下标

       while(cin>>n)

       {

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

                     cin>>a[i];

              b[0]=1;

              c[0]=-1;

              c[1]=a[0];

              len=1;//此时只有c[1]求出来,最长递增子序列的长度为1.

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

              {

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

                     c[j]=a[i];

                     if(j>len)//要更新len,另外补充一点:由二分查找可知j只可能比len1

                            len=j;//更新len

              }

              cout<<len<<endl;

       }

       return 0;

}

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

求最长递增部分序列是一个比较常见的动态规划题。在导弹拦截等题中都有用到。一般来说就是用经典的O(n^2)的动态规划算法。

算法如下:

         设A[i]表示序列中的第i个数,F[i]表示从1到i这一段中以i结尾的最长上升子序列的长度,初始时设F[i] = 0(i = 1, 2, ..., len(A))。则有动态规划方程:F[i] = max{1, F[j] + 1} (j = 1, 2, ..., i - 1, 且A[j] < A[i])。

然而在hoj10027中n的值达到了50000。显而易见经典算法是会超时滴。所以只有另谋出路了。

         用一个变量len记录到目前为止所找出来的最长递增序列的长度。另外准备一个数组b[],用这个数组表示长度为j的递增序列中最后一个元素的值。在这里长度为j的递增序列不止一个,我们所要保存是那个最小的。为什么呢?因为最后一个元素越小,那么这个递增序列在往后被延长的机会越大。初始化b[0] = -1;len = 0;从第一个元素a[1]开始       a[i]( 1 <= i <= n)。如果这个元素比len长的序列的最大值大。则把这个元素直接添加到b数组的后面。如果这个元素比b数组的第一个元素还要小则把这个元素赋给b数组的第一个值。否则进行二分查找。当在b数组里面找到一个数比a[i]小,并且他的后面的数大于或等于a[i]则跳出。将a[i]添加到这个数的后面。输出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 小强摩羯座 阅读(2910) | 评论 (1)编辑 收藏

 Java把内存划分成两种:一种是栈内存,一种是堆内存。

    在函数中定义的一些基本类型的变量和对象的引用变量都在函数的栈内存中分配。

    当在一段代码块定义一个变量时,Java就在栈中为这个变量分配内存空间,当超过变量的作用域后,Java会自动释放掉为该变量所分配的内存空间,该内存空间可以立即被另作他用。

    堆内存用来存放由new创建的对象和数组。

    在堆中分配的内存,由Java虚拟机的自动垃圾回收器来管理。

    在堆中产生了一个数组或对象后,还可以在栈中定义一个特殊的变量,让栈中这个变量的取值等于数组或对象在堆内存中的首地址,栈中的这个变量就成了数组或对象的引用变量。

    引用变量就相当于是为数组或对象起的一个名称,以后就可以在程序中使用栈中的引用变量来访问堆中的数组或对象。

    具体的说:

    栈与堆都是Java用来在Ram中存放数据的地方。与C++不同,Java自动管理栈和堆,程序员不能直接地设置栈或堆。

    Java的堆是一个运行时数据区,类的(对象从中分配空间。这些对象通过new、newarray、anewarray和multianewarray等 指令建立,它们不需要程序代码来显式的释放。堆是由垃圾回收来负责的,堆的优势是可以动态地分配内存大小,生存期也不必事先告诉编译器,因为它是在运行时 动态分配内存的,Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是,由于要在运行时动态分配内存,存取速度较慢。

    栈的优势是,存取速度比堆要快,仅次于寄存器,栈数据可以共享。但缺点是,存在栈中的数据大小与生存期必须是确定的,缺乏灵活性。栈中主要存放一些基本 类型的变量(,int, short, long, byte, float, double, boolean, char)和对象句柄。

    栈有一个很重要的特殊性,就是存在栈中的数据可以共享。假设我们同时定义:

    int a = 3;

    int b = 3;

    编译器先处理int a = 3;首先它会在栈中创建一个变量为a的引用,然后查找栈中是否有3这个值,如果没找到,就将3存放进来,然后将a指向3。接着处理int b = 3;在创建完b的引用变量后,因为在栈中已经有3这个值,便将b直接指向3。这样,就出现了a与b同时均指向3的情况。这时,如果再令a=4;那么编译器 会重新搜索栈中是否有4值,如果没有,则将4存放进来,并令a指向4;如果已经有了,则直接将a指向这个地址。因此a值的改变不会影响到b的值。要注意这 种数据的共享与两个对象的引用同时指向一个对象的这种共享是不同的,因为这种情况a的修改并不会影响到b, 它是由编译器完成的,它有利于节省空间。而一个对象引用变量修改了这个对象的内部状态,会影响到另一个对象引用变量。

    String是一个特殊的包装类数据。可以用:

    String str = new String("abc");

    String str = "abc";

    两种的形式来创建,第一种是用new()来新建对象的,它会在存放于堆中。每调用一次就会创建一个新的对象。

    而第二种是先在栈中创建一个对String类的对象引用变量str,然后查找栈中有没有存放"abc",如果没有,则将"abc"存放进栈,并令str指向“abc”,如果已经有“abc” 则直接令str指向“abc”。

    比较类里面的数值是否相等时,用equals()方法;当测试两个包装类的引用是否指向同一个对象时,用==,下面用例子说明上面的理论。

    String str1 = "abc";

    String str2 = "abc";

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

    String str1 =new String ("abc");

    String str2 =new String ("abc");

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

    因此用第二种方式创建多个“abc”字符串,在内存中其实只存在一个对象而已. 这种写法有利与节省内存空间. 同时它可以在一定程度上提高程序的运行速度,因为JVM会自动根据栈中数据的实际情况来决定是否有必要创建新对象。而对于String str = new String("abc");的代码,则一概在堆中创建新对象,而不管其字符串值是否相等,是否有必要创建新对象,从而加重了程序的负担。

    另一方面, 要注意: 我们在使用诸如String str = "abc";的格式定义类时,总是想当然地认为,创建了String类的对象str。担心陷阱!对象可能并没有被创建!而可能只是指向一个先前已经创建的 对象。只有通过new()方法才能保证每次都创建一个新的对象。 由于String类的immutable性质,当String变量需要经常变换其值时,应该考虑使用StringBuffer类,以提高程序效率。

    java中内存分配策略及堆和栈的比较

    2.1 内存分配策略按照编译原理的观点,程序运行时的内存分配有三种策略,分别是静态的,栈式的,和堆式的.静态存储分配是指在编译时就能确定每个数据目标在运行时刻的存储空间需求,因而在编译时就可以给他们分配固定的内存空间.这种分配策略要求程序代码中不允 许有可变数据结构(比如可变数组)的存在,也不允许有嵌套或者递归的结构出现,因为它们都会导致编译程序无法计算准确的存储空间需求.栈式存储分配也可称为动态存储分配,是由一个类似于堆栈的运行栈来实现的.和静态存储分配相反,在栈式存储方案中,程序对数据区的需求在编译时是完全未知 的,只有到运行的时候才能够知道,但是规定在运行中进入一个程序模块时,必须知道该程序模块所需的数据区大小才能够为其分配内存.和我们在数据结构所熟知 的栈一样,栈式存储分配按照先进后出的原则进行分配。

    静态存储分配要求在编译时能知道所有变量的存储要求,栈式存储分配要求在过程的入口处必须知道所有的存储要求,而堆式存储分配则专门负责在编译时或运行时 模块入口处都无法确定存储要求的数据结构的内存分配,比如可变长度串和对象实例.堆由大片的可利用块或空闲块组成,堆中的内存可以按照任意顺序分配和释 放.

    2.2 堆和栈的比较

    上面的定义从编译原理的教材中总结而来,除静态存储分配之外,都显得很呆板和难以理解,下面撇开静态存储分配,集中比较堆和栈:从堆和栈的功能和作用来通俗的比较,堆主要用来存放对象的,栈主要是用来执行程序的.而这种不同又主要是由于堆和栈的特点决定的:在编程中,例如C/C++中,所有的方法调用都是通过栈来进行的,所有的局部变量,形式参数都是从栈中分配内存空间的。实际上也不是什么分配,只是从栈顶 向上用就行,就好像工厂中的传送带(conveyor belt)一样,Stack Pointer会自动指引你到放东西的位置,你所要做的只是把东西放下来就行.退出函数的时候,修改栈指针就可以把栈中的内容销毁.这样的模式速度最快, 当然要用来运行程序了.需要注意的是,在分配的时候,比如为一个即将要调用的程序模块分配数据区时,应事先知道这个数据区的大小,也就说是虽然分配是在程 序运行时进行的,但是分配的大小多少是确定的,不变的,而这个"大小多少"是在编译时确定的,不是在运行时.堆是应用程序在运行的时候请求操作系统分配给自己内存,由于从操作系统管理的内存分配,所以在分配和销毁时都要占用时间,因此用堆的效率非常低.但是堆的 优点在于,编译器不必知道要从堆里分配多少存储空间,也不必知道存储的数据要在堆里停留多长的时间,因此,用堆保存数据时会得到更大的灵活性。事实上,面 向对象的多态性,堆内存分配是必不可少的,因为多态变量所需的存储空间只有在运行时创建了对象之后才能确定.在C++中,要求创建一个对象时,只需用 new命令编制相关的代码即可。执行这些代码时,会在堆里自动进行数据的保存.当然,为达到这种灵活性,必然会付出一定的代价:在堆里分配存储空间时会花 掉更长的时间!这也正是导致我们刚才所说的效率低的原因,看来列宁同志说的好,人的优点往往也是人的缺点,人的缺点往往也是人的优点.

    2.3 JVM中的堆和栈JVM是基于堆栈的虚拟机.JVM为每个新创建的线程都分配一个堆栈.也就是说,对于一个Java程序来说,它的运行就是通过对堆栈的操作来完成的。堆栈以帧为单位保存线程的状态。JVM对堆栈只进行两种操作:以帧为单位的压栈和出栈操作。

    我们知道,某个线程正在执行的方法称为此线程的当前方法.我们可能不知道,当前方法使用的帧称为当前帧。当线程激活一个Java方法,JVM就会在线程的 Java堆栈里新压入一个帧。这个帧自然成为了当前帧.在此方法执行期间,这个帧将用来保存参数,局部变量,中间计算过程和其他数据.这个帧在这里和编译 原理中的活动纪录的概念是差不多的.从Java的这种分配机制来看,堆栈又可以这样理解:堆栈(Stack)是操作系统在建立某个进程时或者线程(在支持多线程的操作系统中是线程)为这个线程建立的存储区域,该区域具有先进后出的特性。

    每一个Java应用都唯一对应一个JVM实例,每一个实例唯一对应一个堆。应用程序在运行中所创建的所有类实例或数组都放在这个堆中,并由应用所有的线程 共享.跟C/C++不同,Java中分配堆内存是自动初始化的。Java中所有对象的存储空间都是在堆中分配的,但是这个对象的引用却是在堆栈中分配,也 就是说在建立一个对象时从两个地方都分配内存,在堆中分配的内存实际建立这个对象,而在堆栈中分配的内存只是一个指向这个堆对象的指针(引用)而已。

posted @ 2009-10-12 21:22 小强摩羯座 阅读(180) | 评论 (0)编辑 收藏


在《编程珠玑》中有详细的讨论。主要出于性能方向改进。

  1. 二分法很简单吧 ,但要想 一次写对  也不容易吧 ,更何况他的一些扩展应用呢 ,我这里扩展了四种,<P> </P><P>基础知识 还是牢靠的好</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.     //返回中间一个数   
  10.     //12345666689   
  11.     // 6  不确定返回哪个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.     //返回重复元素的最后一个数   
  29.     //123456667   
  30.     //最后一个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.     //返回重复元素的最前一个数   
  51.     //123456667   
  52.     //最前一个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.     //返回重复元素的最前一个数   
  73.     //1234566689   
  74.     //最前一个6位置返回 ,若找不到,显示 比他小的离它最大位置,比它小的离它最小位置   
  75.     //如 找 7 ,则 输出 最后一个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 小强摩羯座 阅读(83) | 评论 (0)编辑 收藏

Java AIO初探(异步网络IO) 

  按照《Unix网络编程》的划分,IO模型可以分为:阻塞IO、非阻塞IO、IO复用、信号驱动IO和异步IO,按照POSIX标准来划分只分为两类:同步IO和异步IO.如何区分呢?首先一个IO操作其实分成了两个步骤:发起IO请求和实际的IO操作,同步IO和异步IO的区别就在于第二个步骤是否阻塞,如果实际的IO读写阻塞请求进程,那么就是同步IO,因此阻塞IO、非阻塞IO、IO服用、信号驱动IO都是同步IO,如果不阻塞,而是操作系统帮你做完IO操作再将结果返回给你,那么就是异步IO.阻塞IO和非阻塞IO的区别在于第一步,发起IO请求是否会被阻塞,如果阻塞直到完成那么就是传统的阻塞IO,如果不阻塞,那么就是非阻塞IO.

    Java nio 2.0的主要改进就是引入了异步IO(包括文件和网络),这里主要介绍下异步网络IO API的使用以及框架的设计,以TCP服务端为例。首先看下为了支持AIO引入的新的类和接口:

    java.nio.channels.AsynchronousChannel标记一个channel支持异步IO操作。

    java.nio.channels.AsynchronousServerSocketChannel ServerSocket的aio版本,创建TCP服务端,绑定地址,监听端口等。

    java.nio.channels.AsynchronousSocketChannel面向流的异步socket channel,表示一个连接。

    java.nio.channels.AsynchronousChannelGroup异步channel的分组管理,目的是为了资源共享。一个AsynchronousChannelGroup绑定一个线程池,这个线程池执行两个任务:处理IO事件和派发CompletionHandler.AsynchronousServerSocketChannel创建的时候可以传入一个AsynchronousChannelGroup,那么通过AsynchronousServerSocketChannel创建的AsynchronousSocketChannel将同属于一个组,共享资源。

    java.nio.channels.CompletionHandler异步IO操作结果的回调接口,用于定义在IO操作完成后所作的回调工作。AIO的API允许两种方式来处理异步操作的结果:返回的Future模式或者注册CompletionHandler,我更推荐用CompletionHandler的方式,这些handler的调用是由AsynchronousChannelGroup的线程池派发的。显然,线程池的大小是性能的关键因素。AsynchronousChannelGroup允许绑定不同的线程池,通过三个静态方法来创建: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

    需要根据具体应用相应调整,从框架角度出发,需要暴露这样的配置选项给用户。

    在介绍完了aio引入的TCP的主要接口和类之后,我们来设想下一个aio框架应该怎么设计。参考非阻塞nio框架的设计,一般都是采用Reactor模式,Reacot负责事件的注册、select、事件的派发;相应地,异步IO有个Proactor模式,Proactor负责CompletionHandler的派发,查看一个典型的IO写操作的流程来看两者的区别:

    Reactor:  send(msg) -> 消息队列是否为空,如果为空  -> 向Reactor注册OP_WRITE,然后返回 -> Reactor select -> 触发Writable,通知用户线程去处理 ->先注销Writable(很多人遇到的cpu 100%的问题就在于没有注销),处理Writeable,如果没有完全写入,继续注册OP_WRITE.注意到,写入的工作还是用户线程在处理。

    Proactor: send(msg) -> 消息队列是否为空,如果为空,发起read异步调用,并注册CompletionHandler,然后返回。 -> 操作系统负责将你的消息写入,并返回结果(写入的字节数)给Proactor -> Proactor派发CompletionHandler.可见,写入的工作是操作系统在处理,无需用户线程参与。事实上在aio的API中,AsynchronousChannelGroup就扮演了Proactor的角色。

    CompletionHandler有三个方法,分别对应于处理成功、失败、被取消(通过返回的Future)情况下的回调处理:

    public interface CompletionHandler {

    void completed(V result, A attachment);

    void failed(Throwable exc, A attachment);

    void cancelled(A attachment);

    }

    其中的泛型参数V表示IO调用的结果,而A是发起调用时传入的attchment.

    在初步介绍完aio引入的类和接口后,我们看看一个典型的tcp服务端是怎么启动的,怎么接受连接并处理读和写,这里引用的代码都是yanf4j 的aio分支中的代码,可以从svn checkout,svn地址: http://yanf4j.googlecode.com/svn/branches/yanf4j-aio

    第一步,创建一个AsynchronousServerSocketChannel,创建之前先创建一个AsynchronousChannelGroup,上文提到AsynchronousServerSocketChannel可以绑定一个AsynchronousChannelGroup,那么通过这个AsynchronousServerSocketChannel建立的连接都将同属于一个AsynchronousChannelGroup并共享资源:this.asynchronousChannelGroup = AsynchronousChannelGroup。withCachedThreadPool(Executors.newCachedThreadPool(),this.threadPoolSize);然后初始化一个AsynchronousServerSocketChannel,通过open方法:this.serverSocketChannel = AsynchronousServerSocketChannel。open(this.asynchronousChannelGroup);通过nio 2.0引入的SocketOption类设置一些TCP选项:this.serverSocketChannel。setOption(StandardSocketOption.SO_REUSEADDR,true);this.serverSocketChannel。setOption(StandardSocketOption.SO_RCVBUF,16*1024);

    绑定本地地址:

    this.serverSocketChannel。bind(new InetSocketAddress("localhost",8080), 100);其中的100用于指定等待连接的队列大小(backlog)。完了吗?还没有,最重要的监听工作还没开始,监听端口是为了等待连接上来以便accept产生一个AsynchronousSocketChannel来表示一个新建立的连接,因此需要发起一个accept调用,调用是异步的,操作系统将在连接建立后,将最后的结果——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");

    }

    注意,重复的accept调用将会抛出PendingAcceptException,后文提到的read和write也是如此。accept方法的第一个参数是你想传给CompletionHandler的attchment,第二个参数就是注册的用于回调的CompletionHandler,最后返回结果Future.你可以对future做处理,这里采用更推荐的方式就是注册一个CompletionHandler.那么accept的CompletionHandler中做些什么工作呢?显然一个赤裸裸的AsynchronousSocketChannel是不够的,我们需要将它封装成session,一个session表示一个连接(mina里就叫IoSession了),里面带了一个缓冲的消息队列以及一些其他资源等。在连接建立后,除非你的服务器只准备接受一个连接,不然你需要在后面继续调用pendingAccept来发起另一个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方法中在最后都调用了pendingAccept来继续发起accept调用,等待新的连接上来。有的同学可能要说了,这样搞是不是递归调用,会不会堆栈溢出?实际上不会,因为发起accept调用的线程与CompletionHandler回调的线程并非同一个,不是一个上下文中,两者之间没有耦合关系。要注意到,CompletionHandler的回调共用的是AsynchronousChannelGroup绑定的线程池,因此千万别在回调方法中调用阻塞或者长时间的操作,例如sleep,回调方法最好能支持超时,防止线程池耗尽。

    连接建立后,怎么读和写呢?回忆下在nonblocking nio框架中,连接建立后的第一件事是干什么?注册OP_READ事件等待socket可读。异步IO也同样如此,连接建立后马上发起一个异步read调用,等待socket可读,这个是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调用与AsynchronousServerSocketChannel的accept调用类似,同样是非阻塞的,返回结果也是一个Future,但是写的结果是整数,表示写入了多少字节,因此read调用返回的是Future,方法的第一个参数是读的缓冲区,操作系统将IO读到数据拷贝到这个缓冲区,第二个参数是传递给CompletionHandler的attchment,第三个参数就是注册的用于回调的CompletionHandler.这里保存了read的结果Future,这是为了在关闭连接的时候能够主动取消调用,accept也是如此。现在可以看看read的CompletionHandler的实现:

    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读失败,会返回失败产生的异常,这种情况下我们就主动关闭连接,通过session.close()方法,这个方法干了两件事情:关闭channel和取消read调用:if (null != this.readFuture) { this.readFuture.cancel(true);

    }

    this.asynchronousSocketChannel.close();   在读成功的情况下,我们还需要判断结果result是否小于0,如果小于0就表示对端关闭了,这种情况下我们也主动关闭连接并返回。如果读到一定字节,也就是result大于0的情况下,我们就尝试从读缓冲区中decode出消息,并派发给业务处理器的回调方法,最终通过pendingRead继续发起read调用等待socket的下一次可读。可见,我们并不需要自己去调用channel来进行IO读,而是操作系统帮你直接读到了缓冲区,然后给你一个结果表示读入了多少字节,你处理这个结果即可。而nonblocking IO框架中,是reactor通知用户线程socket可读了,然后用户线程自己去调用read进行实际读操作。这里还有个需要注意的地方,就是decode出来的消息的派发给业务处理器工作最好交给一个线程池来处理,避免阻塞group绑定的线程池。

    IO写的操作与此类似,不过通常写的话我们会在session中关联一个缓冲队列来处理,没有完全写入或者等待写入的消息都存放在队列中,队列为空的情况下发起write调用:

    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调用返回的结果与read一样是一个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就是实际写入的字节数,然后我们判断消息的缓冲区是否还有剩余,如果没有就将消息从队列中移除,如果队列中还有消息,那么继续发起write调用。

    重复一下,这里引用的代码都是yanf4j aio分支中的源码,感兴趣的朋友可以直接check out出来看看: http://yanf4j.googlecode.com/svn/branches/yanf4j-aio.在引入了aio之后,java对于网络层的支持已经非常完善,该有的都有了,java也已经成为服务器开发的首选语言之一。java的弱项在于对内存的管理上,由于这一切都交给了GC,因此在高性能的网络服务器上还是Cpp的天下。java这种单一堆模型比之erlang的进程内堆模型还是有差距,很难做到高效的垃圾回收和细粒度的内存管理。

    这里仅仅是介绍了aio开发的核心流程,对于一个网络框架来说,还需要考虑超时的处理、缓冲buffer的处理、业务层和网络层的切分、可扩展性、性能的可调性以及一定的通用性要求。

posted @ 2009-09-21 22:22 小强摩羯座 阅读(276) | 评论 (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  
      }
 
 }

  对这个方法参数化类型T,由定义数据a和Collection时传入的共同决定,它们可以使用相同类型,也可以使用不同类型,当类型不同时,它们必须有继承关系,类型推断时使用较高的那个。
4, when to use <?> or <T> :他们主要用在泛型方法,T相比?,它有名称,可多次使用来表达依赖关系。所以在不表达依赖关系的地方就应该使用?。它简单、灵活。

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

 

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

 

这个合作使得dest src 的依赖关系得以表达,同时让 src 的接纳范畴扩大了。假如我们只用泛型方法来实现:  

 

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

 

那么S 的存在就显得有些不必要,有些不优雅。总的来说,通配符更简洁清晰,只要情况允许就应该首选。

5、由于普通数组是协变的,而GenricType由于List<String>不是List<Object>的子类型,所以它不能协变。可以使用?来new 一个数组。但是通常new完就要加元素,而?类型未知不可以产生对象的。所以最后使用Class<T> 类型做形参,实参用T.class就可以。这就是为什么Hibernate.load和get中会使用的.class的用法。比较新知识点是String.class就是Class<String>(String.class称字面类常量)。当传入Class<T> c 对象后,可以利用reflect来构造对象,并作状态设置。


posted @ 2009-08-15 16:15 小强摩羯座 阅读(259) | 评论 (0)编辑 收藏

仅列出标题
共20页: First 上一页 2 3 4 5 6 7 8 9 10 下一页 Last