Leetcode-Maximum Subarray

最近在leetcode上看到一个有趣的题目Maximum Subarray,跟大家分享一下,题目如下:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 

1.  O(n) 的一般解法

这个解法的思路是:用iMax表示包含第i个元素的subArray的最大值,那么iMax(i) = max( iMax( i -1) + nums[i] , iMax( i -1))

    public int maxSubArrayOnWithOutDivide1(int[] nums) {
        int max = nums[0];
        int iMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            iMax = Math.max(iMax + nums[i], nums[i]);
            max = Math.max(iMax, max);
        }
        return max;
    }

 

还有一个类似的解法,思路是:保证i之前的最大值是个非负数,那么到i的iMax 就是 iMax + nums[i]。

讨论区还有个逆序的解法,思路和这个一样https://discuss.leetcode.com/topic/61770/only-one-pass-to-solve-the-problem

    public int maxSubArrayOnWithOutDivide2(int[] nums) {
        int max = nums[0];
        int iMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            iMax += nums[i];
            max = Math.max(iMax, max);
            if(iMax < 0){
                iMax = 0;
            }
        }
        return max;
    }

2. O(nLogn)的divide and conquer 解法 

在more practice 里面,让我们尝试使用分治法,问题变得更有趣啦!

 index:    0    1     2      3      4      5      6      7      8

array:    [-2,   1,   -3,    4,    -1,    2,      1,    -5,     4]

解题思路:

如果我们要计算index 0-8的最大和子串,那么可以考虑计算

1. 0-4 的最大和子串

2. 5-8 的最大和子串

3. 0-4中以4结尾最大和子串 + 5-8中以5开头的最大和子串

根据这个思路,首先有一种O(n) = 2O(2/n) + n 的解法,这个直接就贴别人的代码了 

public class Solution {
public int maxSubArray(int[] nums) {
    /*
 Divide-and-conquer method.
 The maximum summation of subarray can only exists under following conditions:
 1. the maximum summation of subarray exists in left half.
 2. the maximum summation of subarray exists in right half.
 3. the maximum summation of subarray exists crossing the midpoints to left and right. 
 1 and 2 can be reached by using recursive calls to left half and right half of the subarraies. 
 Condition 3 can be found starting from the middle point to the left,
 then starting from the middle point to the right. Then adds up these two parts and return. 

 T(n) = 2*T(n/2) + O(n)
 this program runs in O(nlogn) time
 */

    int maxsum = subArray(nums, 0, nums.length-1);
    return maxsum;
}

private int subArray(int[] A, int left, int right){
    if (left == right){
        //base case
        return A[left];
    }
    int mid = left + (right-left)/2;
    int leftsum = subArray(A, left, mid); //left part of the subarray sum, condition 1
    int rightsum = subArray(A, mid+1, right); //right part of the subarray sum, condition 2
    int middlesum = midSubArray(A, left, mid, right); //cross part of the subarray sum, condition 3
    // System.out.println(leftsum);
    // System.out.println(rightsum);
    // System.out.println(middlesum);

    //following if condition will return middlesum if lost the "=" under the conditon of leftsum = rightsum, which may be problematic if leftsum = rightsum < middlesum.
    //for example: [-1, -1, -2, -2]
    if (leftsum >= rightsum && leftsum >= middlesum){
        return leftsum;
    }
    if (rightsum >= leftsum && rightsum >= middlesum){
        return rightsum;
    }
    return middlesum;
}

private int midSubArray(int[] A, int left, int mid, int right){
    int leftsum = Integer.MIN_VALUE;
    int rightsum = Integer.MIN_VALUE;
    int sum = 0;
    for (int i = mid; i >= left; i--){
        sum += A[i];
        if (leftsum < sum){
            leftsum = sum;
        }
    }

    sum = 0;
    for (int j = mid + 1; j <= right; j++){
        sum += A[j];
        if (rightsum < sum){
            rightsum = sum;
        }
    }

    return leftsum + rightsum;
}}

虽然这种解法利用了分治法的思路,但是复杂度确实O(nLogn),复杂度比1中的解法高,实在不是我们想要的 

 

 3. O(n) divide and conquer

虽然想到了2中的思路,但是怎么把它变成一个O(n)的算法,表示实在没解出来。后来在评论区看到一段c++代码,眼前一亮!

mx (largest sum of this subarray), lmx(largest sum starting from the left most element), rmx(largest sum ending with the right most element), sum(the sum of the total subarray). 

class Solution {
public:
    void maxSubArray(vector<int>& nums, int l, int r, int& mx, int& lmx, int& rmx, int& sum) {
        if (l == r) {
            mx = lmx = rmx = sum = nums[l];
        }
        else {
            int m = (l + r) / 2;
            int mx1, lmx1, rmx1, sum1;
            int mx2, lmx2, rmx2, sum2;
            maxSubArray(nums, l, m, mx1, lmx1, rmx1, sum1);
            maxSubArray(nums, m + 1, r, mx2, lmx2, rmx2, sum2);
            mx = max(max(mx1, mx2), rmx1 + lmx2);
            lmx = max(lmx1, sum1 + lmx2);
            rmx = max(rmx2, sum2 + rmx1);
            sum = sum1 + sum2;
        }
    }
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        int mx, lmx, rmx, sum;
        maxSubArray(nums, 0, nums.size() - 1, mx, lmx, rmx, sum);
        return mx;
    }
};

 

 

 


 以下是我的java实现:

    //************ O(n) divide and conquer
    /**
 * for example: array = [-2,1,-3]
 * max = 1
 * lMax = -1
 * rMax = -2
 * sum = -4
 */
    private class ArrayContext {
        int max; // max sum of the sub array
        int lMax; // max sum begins with the leftmost element
        int rMax; // max sum ends with the rightmost element
        int sum; // sum of all elements

    }

    public ArrayContext getArrayContext(int[] nums, int l, int r) {
        ArrayContext ctx = new ArrayContext();
        if (l == r) {
            // only one element
            ctx.max = nums[l];
            ctx.lMax = nums[l];
            ctx.rMax = nums[l];
            ctx.sum = nums[l];
        } else {
            int m = (l + r) / 2;
            ArrayContext lCtx = getArrayContext(nums, l, m);
            ArrayContext rCtx = getArrayContext(nums, m + 1, r);

            // the max sum of sub array would be the max of:
            // 1. max of the left sub array
            // 2. max of the right sub array
            // 3. rMax of the left sub array + lMax of the right sub array
            ctx.max = Math.max(Math.max(lCtx.max, rCtx.max), lCtx.rMax + rCtx.lMax);
            ctx.lMax = Math.max(lCtx.lMax, lCtx.sum + rCtx.lMax);
            ctx.rMax = Math.max(rCtx.rMax, rCtx.sum + lCtx.rMax);
            ctx.sum = lCtx.sum + rCtx.sum;
        }

        return ctx;
    }


    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        ArrayContext ctx = getArrayContext(nums, 0, nums.length - 1);
        return ctx.max;
    }

<!– HTML generated using hilite.me –><div style=”background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;”><pre style=”margin: 0; line-height: 125%”>    <span style=”color: #888888″>//************  O(n)  divide and conquer</span>

    <span style=”color: #888888″>/**</span><span style=”color: #888888″>     * for example:  array = [-2,1,-3]</span><span style=”color: #888888″>     * max = 1</span><span style=”color: #888888″>     * lMax = -1</span><span style=”color: #888888″>     * rMax = -2</span><span style=”color: #888888″>     * sum = -4</span><span style=”color: #888888″>     */</span>    <span style=”color: #008800; font-weight: bold”>private</span> <span style=”color: #008800; font-weight: bold”>class</span> <span style=”color: #BB0066; font-weight: bold”>ArrayContext</span> <span style=”color: #333333″>{</span>        <span style=”color: #333399; font-weight: bold”>int</span> max<span style=”color: #333333″>;</span> <span style=”color: #888888″>// max sum of the sub array</span>        <span style=”color: #333399; font-weight: bold”>int</span> lMax<span style=”color: #333333″>;</span> <span style=”color: #888888″>// max sum begins with the leftmost element</span>        <span style=”color: #333399; font-weight: bold”>int</span> rMax<span style=”color: #333333″>;</span> <span style=”color: #888888″>// max sum ends with the rightmost element</span>        <span style=”color: #333399; font-weight: bold”>int</span> sum<span style=”color: #333333″>;</span> <span style=”color: #888888″>// sum of all elements</span>
    <span style=”color: #333333″>}</span>
    <span style=”color: #008800; font-weight: bold”>public</span> ArrayContext <span style=”color: #0066BB; font-weight: bold”>getArrayContext</span><span style=”color: #333333″>(</span><span style=”color: #333399; font-weight: bold”>int</span><span style=”color: #333333″>[]</span> nums<span style=”color: #333333″>,</span> <span style=”color: #333399; font-weight: bold”>int</span> l<span style=”color: #333333″>,</span> <span style=”color: #333399; font-weight: bold”>int</span> r<span style=”color: #333333″>)</span> <span style=”color: #333333″>{</span>        ArrayContext ctx <span style=”color: #333333″>=</span> <span style=”color: #008800; font-weight: bold”>new</span> ArrayContext<span style=”color: #333333″>();</span>        <span style=”color: #008800; font-weight: bold”>if</span> <span style=”color: #333333″>(</span>l <span style=”color: #333333″>==</span> r<span style=”color: #333333″>)</span> <span style=”color: #333333″>{</span>            <span style=”color: #888888″>// only one element</span>            ctx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>max</span> <span style=”color: #333333″>=</span> nums<span style=”color: #333333″>[</span>l<span style=”color: #333333″>];</span>            ctx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>lMax</span> <span style=”color: #333333″>=</span> nums<span style=”color: #333333″>[</span>l<span style=”color: #333333″>];</span>            ctx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>rMax</span> <span style=”color: #333333″>=</span> nums<span style=”color: #333333″>[</span>l<span style=”color: #333333″>];</span>            ctx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>sum</span> <span style=”color: #333333″>=</span> nums<span style=”color: #333333″>[</span>l<span style=”color: #333333″>];</span>        <span style=”color: #333333″>}</span> <span style=”color: #008800; font-weight: bold”>else</span> <span style=”color: #333333″>{</span>            <span style=”color: #333399; font-weight: bold”>int</span> m <span style=”color: #333333″>=</span> <span style=”color: #333333″>(</span>l <span style=”color: #333333″>+</span> r<span style=”color: #333333″>)</span> <span style=”color: #333333″>/</span> <span style=”color: #0000DD; font-weight: bold”>2</span><span style=”color: #333333″>;</span>            ArrayContext lCtx <span style=”color: #333333″>=</span> getArrayContext<span style=”color: #333333″>(</span>nums<span style=”color: #333333″>,</span> l<span style=”color: #333333″>,</span> m<span style=”color: #333333″>);</span>            ArrayContext rCtx <span style=”color: #333333″>=</span> getArrayContext<span style=”color: #333333″>(</span>nums<span style=”color: #333333″>,</span> m <span style=”color: #333333″>+</span> <span style=”color: #0000DD; font-weight: bold”>1</span><span style=”color: #333333″>,</span> r<span style=”color: #333333″>);</span>
            <span style=”color: #888888″>// the max sum of sub array  would be the max of:</span>            <span style=”color: #888888″>// 1. max of the left sub array</span>            <span style=”color: #888888″>// 2. max of the right sub array</span>            <span style=”color: #888888″>// 3. rMax of the left sub array + lMax of the right sub array</span>            ctx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>max</span> <span style=”color: #333333″>=</span> Math<span style=”color: #333333″>.</span><span style=”color: #0000CC”>max</span><span style=”color: #333333″>(</span>Math<span style=”color: #333333″>.</span><span style=”color: #0000CC”>max</span><span style=”color: #333333″>(</span>lCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>max</span><span style=”color: #333333″>,</span> rCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>max</span><span style=”color: #333333″>),</span> lCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>rMax</span> <span style=”color: #333333″>+</span> rCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>lMax</span><span style=”color: #333333″>);</span>            ctx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>lMax</span> <span style=”color: #333333″>=</span> Math<span style=”color: #333333″>.</span><span style=”color: #0000CC”>max</span><span style=”color: #333333″>(</span>lCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>lMax</span><span style=”color: #333333″>,</span> lCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>sum</span> <span style=”color: #333333″>+</span> rCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>lMax</span><span style=”color: #333333″>);</span>            ctx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>rMax</span> <span style=”color: #333333″>=</span> Math<span style=”color: #333333″>.</span><span style=”color: #0000CC”>max</span><span style=”color: #333333″>(</span>rCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>rMax</span><span style=”color: #333333″>,</span> rCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>sum</span> <span style=”color: #333333″>+</span> lCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>rMax</span><span style=”color: #333333″>);</span>            ctx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>sum</span> <span style=”color: #333333″>=</span> lCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>sum</span> <span style=”color: #333333″>+</span> rCtx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>sum</span><span style=”color: #333333″>;</span>        <span style=”color: #333333″>}</span>
        <span style=”color: #008800; font-weight: bold”>return</span> ctx<span style=”color: #333333″>;</span>    <span style=”color: #333333″>}</span>

    <span style=”color: #008800; font-weight: bold”>public</span> <span style=”color: #333399; font-weight: bold”>int</span> <span style=”color: #0066BB; font-weight: bold”>maxSubArray</span><span style=”color: #333333″>(</span><span style=”color: #333399; font-weight: bold”>int</span><span style=”color: #333333″>[]</span> nums<span style=”color: #333333″>)</span> <span style=”color: #333333″>{</span>        <span style=”color: #008800; font-weight: bold”>if</span> <span style=”color: #333333″>(</span>nums<span style=”color: #333333″>.</span><span style=”color: #0000CC”>length</span> <span style=”color: #333333″>==</span> <span style=”color: #0000DD; font-weight: bold”>0</span><span style=”color: #333333″>)</span> <span style=”color: #333333″>{</span>            <span style=”color: #008800; font-weight: bold”>return</span> <span style=”color: #0000DD; font-weight: bold”>0</span><span style=”color: #333333″>;</span>        <span style=”color: #333333″>}</span>
        ArrayContext ctx <span style=”color: #333333″>=</span> getArrayContext<span style=”color: #333333″>(</span>nums<span style=”color: #333333″>,</span> <span style=”color: #0000DD; font-weight: bold”>0</span><span style=”color: #333333″>,</span> nums<span style=”color: #333333″>.</span><span style=”color: #0000CC”>length</span> <span style=”color: #333333″>-</span> <span style=”color: #0000DD; font-weight: bold”>1</span><span style=”color: #333333″>);</span>        <span style=”color: #008800; font-weight: bold”>return</span> ctx<span style=”color: #333333″>.</span><span style=”color: #0000CC”>max</span><span style=”color: #333333″>;</span>    <span style=”color: #333333″>}</span></pre></div>

 
Posted in algorithm, Java, leetcode | Tagged , , , | Leave a comment

元宵节

  转眼16年的元宵节都要过去了,本来说两周内更新一次博客,结果一过就是一个多月,不过过年也的确是懒散了许多。新工作也快半年了,工作状态维持的尚可,学习状态却是不太找的到了,哎。昨天收拾房间,发现以前买的几本书,发现还有好多东西没有看。今年准备休学一年,事情实在有些多,项目赶得要死,需求还不明确。家里装修,小宝要上课,我也没帮上她什么,想着自己学学前端可以教教她,总发现现在的时间不像以前那么好挤出来。越是这样,还越是发现自己是个小菜鸟啊。以前还有空抽抽时间写点技术类的博客,搞点总结,现在却发现自己花了很多的时间在工作上,困在了业务里,技术的学习却少了,或许生活学习的习惯的确变差了。

  小宝在上课,也不太想回家,我倒是挺享受这样的时刻。公司人也不多,也没人打扰,手头没有特别紧急的事,可以听着歌写写博客,总结下自己最近一段时间的状态,做点小规划。我其实挺喜欢做这种事,不过这种时间貌似不是那么好找。或许我应该定期找个晚上,跑到一个没人的地方去写点东西,恩,good idea。哎,实在不擅长文字表述,最近又tm没什么技术研究,博客挂在这边老是不写又感觉自己有点费,dt。

   元宵节,祝大家节日快乐吧。希望小宝能在学校学到东西,顺利找到工作;我今年可以level up;装修顺利,买车顺利,感情顺利(本来想打个emoji,果然数据库存不了)

Posted in Life | Leave a comment

There is always a way

  2015过的太快,一眨眼,换了几次工作,进了阿里,领证了,买房了。。。2015年的元旦过的很愉快,第一次去了北方城市,第一次和老婆去远方旅行,愉快而轻松。今年的元旦过的算是“别有风味”吧,在医院打了四天的点滴,2016年的开始就泡在医院了。小宝也是忙的不行,每天单程两小时去市区上课,还要忙着装修。2016,总感觉这个开头很tough。

  前段时间得了肺炎,每天都没精打采,不想上班,不想写代码,不想看书,不想上课。我感觉自己很忙,很累,有着做不完的事情,有时却不知道为什么要做这些事。时常和小宝吵架,她说我不懂得生活,我说她不知道我有多忙多累,甚至交流都成了问题。回想起来,是我做的不好,任何事物都不该成为我们之间的隔阂。

  15年过年来了老婆就催着我去找工作,当时不知道为什么,并不是很想换工作,可能是懒,也可能是觉得自己并没有准备好。等到年终奖发下来,等到调薪结果出来,感觉完全就是被公司耍了(如果以后有哪个程序员看到这篇Blog,一定要记住,宁愿找个小一点累一点的私企,不要去做外包),连我这种情商为负值的人也感觉忍无可忍了,于是开始了毫不给老大面子的请假,连续两个星期,每天最多上半天班,想想那种不用给任何人面子的感觉真TM爽!面试了好多公司,没有一个满意的,其实爱奇艺面的还挺不错的,但是像我这种半路出家,还是Java为母语的程序员,终究算法是软肋,哎,这也是我报交大在职研究生最大的原因吧。但是离职都提了一个月了,也不能死赖着不走,虽然William和Rose都极力的想留我,可没有正式员工的HC,留下来终究也不会改变什么。拿了几个差不多的Offer,最终去了花旗,工资还可以,加班少,假期多,我会有很多时间做自己想做的事。其实最重要的原因是,买房有一些补贴,因为那个时候其实已经开始和老婆在上海看房,看的都是些上班要一个多小时的郊区。结果上班几个月,一直感觉很不爽,限制太多!一个做技术的,连自己电脑的Admin权限都没有,我心里过不去这道坎。突然有了个阿里内推的机会,之前一直没投阿里,因为我心里没底,感觉自己没准备好。等到阿里的一面下来,我能感觉到的是,其实我的能力已经够进阿里,缺少的是准备准备准备。后面除了最后的非技术面,都还算得心应手。

  九月阿里的Offer拿到,人生又面临着抉择。去了杭州,我的工资涨了,老婆的工作要丢,总体上来说,家庭收入并没有增加。当然,去余杭的话,买房的压力会瞬间小很多,去了阿里我的发展也会好很多,虽然是个内部的部门。小宝的损失很大,要辞了一份非常轻松工资尚可的工作,一切重新开始,来杭州我亏欠最多的就是她。其实我已经预见了一些进阿里的得与失,所以如果当初她说不愿来杭州,我也可以接受。谢谢小宝最终只吃了我。进阿里的节奏一下快的让我有些迷失,上班一周的时候我已经开发了一个小功能并且上线。一方面我有些骄傲,毕竟接触的一切都是新的,webx、TDDL、HSF、Diamond、notify。。。一堆的新东西,但我很快就找到了工作的切入点,我一直觉得自己的适应性非常好,无论怎样的工作模式,我可以很快上手。另一方面,我其实已经开始有些担心,我担心的不是自己跟不上这种快节奏,这种高强度的工作——上班这几年我从来没有因为工作的事情感觉到困扰,我担心的是我怎么权衡好工作和家庭生活。加班成了常态,周末要回上海上课,几乎没什么时间陪老婆,我这种情商又低的人,怎么让生活过的精彩些,怎么让老婆不觉得孤单,不觉得来杭州是个错误的决定。I am so worried. 虽然我的所作所为不像是我很care这些,但是其实我真的很担心。接着的日子,也验证了我的担心,我几乎所有的时间都花在了工作和上学,真的抽不出时间陪老婆。她经常骂我,说我忘记了生活的意义,忘记了工作赚钱的目的。我知道她说的是对的,但是我有些无奈:刚来一个新公司,工作随便应付一下吗?上学,交了那么多的钱,已经付出了这么多精力,放弃吗?后来甚至有些麻木了。我觉得自己能做的就是,她想要任何东西都尽量去满足她,这样或许可以让她开心一些。

  这些天肺炎基本好了,人也有了精神,不知道为什么,突然感觉到,其实我的处境并不是那么困难,是长期的劳累让我的心智也跟着疲惫,麻木。人在遇到困难的时候,禁忌的就是让负面情绪腐蚀了自己,开始变得麻木,开始抱怨周围的事物。There is always a way。我把每件事情都抓的太紧,什么都想要,却忽视了最该抓紧的。工作也并不是别人叫你做什么你就一定要给别人做,要权衡自己从中受益,不要沦为工作的机器。上学原本是真的想好好学点东西,但其实发现工作已经那么累,已经接受了那么多的东西,你真的可以再全盘接受那么多东西吗?学自己该学的东西,不需要的可以混过去,毕竟我从小到大都不适合课堂教育。现在我的想法应该有所改变,工作抓住收益最大的,上课并不是每周都一定要去学校,获取些有用的知识,拿到毕业证目的就已经达到了。这样,我就可以抽出时间多陪陪小宝,多规划规划自己的生活,做些自己想做的事情。

   2016年,要做生活的主人!

 

 
Posted in Whatever | Leave a comment

Check List for 2016

  1. 一年不玩游戏,最难做到的,也并不是必要的,但是人做事,总得有点决心才可以。
  2. 锻炼,坚持锻炼,不超过一个星期不锻炼。
  3. 代码,继续topcoder,不超过一周无任何github记录。
  4. 吉他,不超过两周不碰它。
  5. blog,心得,不超过两周不更新。
  6. 学习,看书看视频,只要不是加班特别晚,不超过三天不看书或者学习视频。
  7. 暂时列出这些,后面想到再补上!
Posted in Whatever | Leave a comment

One Person’s Dream

18岁的时候觉得自己最对不起的是母亲,25岁的时候越来越认识到自己亏欠最多的是父亲。

现在还记得小的时候,很小的时候,甚至记忆还很模糊的时候,家里人给我算了个命,算命先生说:这匹马将来是一匹千里马,他不甘受到限制,他会去到很远很远的地方。我忘记了了那个年纪的大多数事,却不知为什么很清楚的记得这句话,甚至依稀记得算命先生的语气。

四五岁的时候来了一次上海,除了动物园、地铁和外滩,没有太多记忆。十岁的时候又来了一次上海,依旧去了动物园,这次还去了东方明珠,住了高档一些的酒店,认识了一些不一样的人事物,认识到了这个城市的一些繁华和发达。等到选择大学的时候,发现自己除了上海,几乎没有考虑过其他的城市,我那时以为自己可以“征服”这座城市。

大学四年一晃就过去了,在这个城市呆了四年,说不上自己受益多少,但是眼界毕竟是不一样。四年过得悠然自得,知道谈论买房前,也从没觉得自己比同学差什么。毕业后毅然决定留在上海,其一,对我来说,这里是全中国最有机会的地方;其二,回去?在我从一个只知道学习玩耍的学生逐渐走到社会,对社会的概念逐渐形成的时候,我是在这个城市度过的,回去,我不见得可以接受另一套社会法则,而且我认为这里的法则跟适合我些。等到你要开始工作结婚买房,你又突然发现,这个城市给予了你很多,要的也不是一般的少。

等意识到自己的决定给我生命中的一些人带来巨大的压力,仿佛这只是我一个人的梦想,父母、女朋友还有其他的家人,他们都只是在跟我承受着代价。突然觉得亏欠他们很多。

这个时候父亲说,人知道上进是好事,我们以你为荣。

一个不太跟你推心置腹的人,一个总是默默为这个家奉献的人,一个总是愿意担起责任的人。25岁,亏欠父亲太多太多。

我不会让你们失望!

Posted in Whatever | Leave a comment

New Beginning?

 

工作终于定下来了,说不上高兴不高兴。薪资待遇还可以,至少短期可以缓解生活压力,工作内容应该也还不错,但是工作的限制实在太多,让人很是不爽!话说回来,谁不想有一份干着又爽薪资又高又不用死命加班的工作,可是很多时候,只能在某些方面compromise一下。

三月底开始找工作,有时七点起床晚上十一二点到家,累成狗。面试了十来次吧,电话面试估计几十次了,心仪的几个结果都挂了,唉,拿了六个都差不多的offer。有一个做旅游到D轮的,两个创业的,一个做支付,一个做互联网金融,还有一个bank的。旅游的这个感觉公司发展挺快,但是给人的感觉公司管理很乱,典型的暴发户感觉。两个创业的一个做图片分享app,一个做淘宝卖家服务。前者不是非常看好,类似的app较多,而且没有直接的金钱来源,做了四五年团队也不是很大。后者是杭州的一家公司,算是一大半的offer在手吧,说起来很奇怪,我本来是不考虑这些处于创业期的小公司的,但是跟这个公司的技术很聊得来,而且驱使我请了半天假去杭州,然后甘愿晚上十一点多才赶回上海的重要原因是:面试官看了我的blog。真的,我觉得这一点真的很重要,至少反映出公司对技术员工的重视程度和面试官的工作态度,我投出的每一份简历都有我的blog地址和git地址,却几乎没有面试官提及这些东西。但是毕竟从上海搬去杭州代价太大,女朋友过去的话也要换工作,最终放弃了。做支付的这个,线下支付居多,现有模式和发展都不看好。互联网金融这个是p2p,大公司背景,但是招聘流程忍不住要吐槽。技术面和hr面加起来才半个多小时吧,而且感觉hr比技术问的还多。定工资竟然要薪资证明或者拉银行流水,然后就按上家的薪资和上家公司的等级给你定薪资,有点呵呵吧。bank这个是所有的中月薪资最高的,而且毕竟是500强子公司,待遇也还不错。应该是manger比较喜欢我吧,面试的流程也非常的顺利,就是等offer等的吐血,四月初定的口头offer,五月初才拿到纸面offer,昨天才正式入职。听说很多外企招聘的流程都是很慢,但是至少也让人感觉的这种巨型传统行业的笨重感。

三月末才开始找工作的时候,发现自己很多东西都忘了,一筹莫展。等到手里有几个offer了,却又很是懈怠,最终也没能拿到一个令自己很满意的offer。其实进不了BAT等级的公司,其他的感觉都差不多,这个时候的选择,无非就是看薪资和发展。当然,对于现阶段的我来说,薪资和稳定更加重要些。我不是鼠目寸光,我也有自己的理想,我也知道自己的选择将会带来什么,但是当你不是一个人,当你要承担起家庭的责任而没有足够的资本的时候,稳定可能是最好的选择,所以我选择去了bank。

为什么程序员都想去BAT,因为如果去得是BAT,这篇blog就可以叫New Beginning,但是现在却要加个“?”。

Posted in Whatever, 求职 | Leave a comment

Properties 和 Jsp Compile Nullpointer


1.发现问题

之前在碰到一个bug,email service的smtp服务由于没有设置timeout,当和服务器连接失败时,会永远hang在那里。然后就在代码里加上了time out。

1 private static final int MAIL_SMTP_TIMEOUT = 300000; 2 Properties props = System.getProperties(); 3 props.put("mail.smtp.timeout", MAIL_SMTP_TIMEOUT); 4 m_session = Session. getDefaultInstance(props, null); 5

 

但是却发现,这样修改后jsp会随机的出现无法compile的情况,报错如下:

HTTP Status 500

The server encountered an internal error () that prevented it from fulfilling this request.
        org.apache.jasper.JasperException: Unable to compile class for JSP
        org.apache.jasper.JspCompilationContext.compile(JspCompilationContext.java:520)
        org.apache.jasper.servlet.JspServletWrapper.service(JspServletWrapper.java:295)
        org.apache.jasper.servlet.JspServlet.serviceJspFile(JspServlet.java:292)
        org.apache.jasper.servlet.JspServlet.service(JspServlet.java:236)
        javax.servlet.http.HttpServlet.service(HttpServlet.java:802)
root cause: java.lang.NullPointerException
        java.util.Hashtable.put(Hashtable.java:396)
        org.apache.tools.ant.PropertyHelper.setProperty(PropertyHelper.java:335)
        org.apache.tools.ant.Project.setPropertyInternal(Project.java:460)
        org.apache.tools.ant.Project.setSystemProperties(Project.java:800)
        org.apache.tools.ant.Project.init(Project.java:261)
        org.apache.jasper.compiler.Compiler.getProject(Compiler.java:116)
        org.apache.jasper.compiler.Compiler.generateClass(Compiler.java:320)
        org.apache.jasper.compiler.Compiler.compile(Compiler.java:472)
        org.apache.jasper.compiler.Compiler.compile(Compiler.java:439)
        org.apache.jasper.compiler.Compiler.compile(Compiler.java:451)
        org.apache.jasper.JspCompilationContext.compile(JspCompilationContext.java:511)
        org.apache.jasper.servlet.JspServletWrapper.service(JspServletWrapper.java:295)
        org.apache.jasper.servlet.JspServlet.serviceJspFile(JspServlet.java:292)
        org.apache.jasper.servlet.JspServlet.service(JspServlet.java:236)
        javax.servlet.http.HttpServlet.service(HttpServlet.java:802)

 具体就是由于ant在set properties的时候出现了null pointer, 导致jsp的编译失败。

 

  2.寻找错误

起初并没有怀疑是代码的问题(真莫有一点怀疑啊…),因为这次修改只是加了这个属性以及升级了mail的jar包,而没有可能引入任何null值。

于是有了两种猜测,一种是新的jar包造成的,一种是有人动了server的环境。

对环境进行了仔细的检查,甚至对prod环境进行了jdb调试,折腾一天无果。

后来经过不断的重启service,发现一个规律:

如果在服务起来后,如果首先访问jsp页面,那jsp就可以编译出来;如果在反问jsp前先访问了某些其他服务,则会nullpointer。然后自然就想到,这个某些其他服务应该就是这个smtp服务。

 

3. 看源码

由于email service是很多年前写的,所以用的tomcat版本比较老(5.0的), ant jar包的版本是1.6.4

于是去看了源码,发现如下:


1.6.4

public void setSystemProperties () {
        Properties systemP = System. getProperties();
        Enumeration e = systemP.propertyNames();
        while (e.hasMoreElements()) {
            String propertyName = (String) e.nextElement();
            String value = systemP.getProperty(propertyName);
            this.setPropertyInternal(propertyName, value);
        }
}

1.7.1

public void setSystemProperties() {
           Properties systemP = System.getProperties();
               Enumeration e = systemP.propertyNames();
                 while (e.hasMoreElements()) {
                    String propertyName = (String) e.nextElement();
                      String value = systemP.getProperty(propertyName);
                       if (value != null) {
                           this.setPropertyInternal(propertyName, value);
                      }
                  }
         }

原来在ant的1.7.1之前,一直没有做nullpointer的检测,就直接赋值到一个hashtable里面,之后的版本已经改了这个bug。但是Properties本身就是个hashtable,放进去的指不可能有null值,为什么拿出来的时候怎么可能有null值,我第一反应是,添加进去的时候是好的,后来由于调用了某些服务,使其中的某个或某些值变为null。后来看了下Properties的源码,也是醉了………….

 

public String getProperty(String key) {
     Object oval = super.get(key);
     String sval = (oval instanceof String) ? (String) oval : null;
      return ((sval == null) && ( defaults != null)) ? defaults. getProperty(key) : sval;
    }

 尼玛,只要不是String的拿出来都妹的是null啊,晕啊,你说你个Properties,只要是Object的都能放的进去(Properties extends Hashtable<Object,Object>),偏偏getProperty的时候你只能拿String的值,toStirng都不尝试下!!!你如果只能放String那你就改为Properties extendsHashtable<String,String>啊,真的不是很理解。后来在stackoverflow上看到一个大牛的话:from a design perspective, the Properties class is considered to be one of the “mistakes” of java.

 

4.还有问题 

但是还有问题,我在一个测试环境测试(也是tomcat5.0)过这个改动,并没有出现nullpointer的情况,后来检查了下,tomcat版本虽然相同,但是测试环境的ant却是1.6.1的,更奇怪了,旧版本是好的,1.6.4反而坏了,看看源码:


1.6.1
public void setSystemProperties() {
        Properties systemP = System. getProperties();
        Enumeration e = systemP.keys();
        while (e.hasMoreElements()) {
            Object name = e.nextElement();
            String value = systemP.get(name).toString();
            this. setPropertyInternal(name.toString(), value);
        }
}

         这里虽然也没有做null 检查,但是用的是get方法,然后做的toString操作。其实这里没做null检查应该也很容易报nullpointer ,估计1.6.4是为了做优化改为了String value = systemP.getProperty(propertyName);

5. 教训

终于,都清楚了!

prod环境用的是1.6.4版本的ant,没有做null检测,但是getProperty的时候又会把非String的值作为null返回,所以报了nullpointer;而1.6.1的版本虽然没有做nullpointer检测,但是用的是hastable的 get方法 和 Object toString方法,所以即使put进去了非Stirng的值,也不会报nullpointer。

其实我改的这段代码感觉有个很不好的地方,是用到了Properties props = System.getProperties();这样一来,我改错的地方不仅会影响我自己的服务,甚至会影响整个jvm的环境。但是这个是原来前辈写的,而且他估计考虑到是配置已经写到系统变量之类的情况吧,总之就不方便改了。


教训:
     以后报bug首先还是检查代码,不行就直接看源码,不要自己觉得不会错就一定不会错,尤其是自己没看过源码的东西;
     能用HashTable的东西就别用Properties了,用Properties就只放String或者load吧,安心。。。
    
    
    
Posted in algorithm, JS | Tagged | 1 Comment

第一份摄影作业

女朋友出去有事,回不了家,苦b留在公司也没啥事,就把之前拍的照片po过来玩玩。

我以前觉得自己是个很没美感的人,拍出来的照片完全像翔一样的。不过女朋友很喜欢拍照,经常因为不能帮她拍出好照片而吵架,所以以后准备每周稍微花一点时间在摄影上面。这是我的第一次作业,拍了上百张吧,就这几张感觉还不错的。

同济1
同济2
同济3

Posted in 求职 | Leave a comment

To the Year of Young

     本命年就要过去了,过去的一年总结的话,总体感觉就是so-so,或者说跟自己想的比实在是马马虎虎。二十岁的时候想着,二十五岁的时候,自己应该是个很牛的人,应该有一份不错的工作,生活应该可以比较自由的掌控了,离自己的初步理想也很近才对。可不得不慢慢接受现实,不管是生活还是工作,都没有想的那样容易。

   以前觉得自己很聪明,不管什么只要想学,都能很快学会。孰不知,这也就是自己以为而已,比自己学的快学的好的人多的数不清,而且学会和学好根本就是两个概念。更可怕的是,有些我现在才学会的东西,很多人在多年前就已经学好了!井底之蛙,接触的越多,越感觉自己有那么多东西要学。过去的一年,接触了一些新鲜的东西:linux服务器的常用操作(ps,aux,grep,tail,awk,netstat等等),dns负载均衡,数据库sharding,消息中间件(tibco, disruptor),多线程的实际应用,aws,wordpress…有些只是了解,有些有点应用基础,但依然是缺乏深入的了解。越要去学习新的东西,越感觉基础不够扎实。所以从羊年开始,要稳稳的打牢基础!明年的学习focus在c++和算法,接下来的至少三年都要打牢基础,算法、操作系统、tcp/ip。

  才工作不到两年,就感觉有些职业病了—经常感觉脖子和腰酸痛。所以羊年还有一个目标就是要坚持锻炼,再加上明年周末要上交大的在职硕士,如果不坚持锻炼加强体魄,明年肯定坚持不下来。

  要说去年一年里也有觉得不是特别马虎的事情,就是顺利的跟女友度过了这一年:-D 想想原来天天要靠别人照顾的,现在算是可以照顾另一个人了,也算是有些成长吧。而且长跑也有九年了,辛酸什么的感觉都忘的差不多,离修成正果也不远了。年少时的一些梦想,感觉最难最渴望的一个慢慢就要实现了。

   再过几天就是羊年了,希望女朋友在本命年里顺顺利利,依然很young。父母可以依然身体健康,可以更多的回报他们。自己工作顺利,更多的学习,争取能有一些质的改变!

Posted in 美女 | Leave a comment

Disruptor 学习之MultiBuffer, WorkerPool ,Priority

自从之前在并发编程网上看到一片关于Disruptor的文章,然后就着迷了,由于能力有限,看了好多天Disruptor的源码才感觉自己稍微有一点点理解(有些对于底层的优化,实在不太直观,还有待研究),然后联系工作的需要,自己就想到写一个: 拥有多个RingBuffer, 支持WorkerPool 模式,支持Priority的disruptor。黑喂狗!

一、对Disruptor的认识

之前看了一些帖子,然后看了一段时间源码,我总体的感觉是:

  1. Disruptor存储数据的结构叫做RingBuffer,是一个固定长度的数组,我们的元素都是存放在数组里,同时由于取数组时我们进行取余操作,数组使用起来就像是一个环形结构。往RingBuffer中放入元素时,只是把相应index的元素做更新。
  2. RingBuffer包含一个Sequencer,这个Sequencer里面包含了生产者当前的下标,以及所有的消费者的下标。生产者可以根据最慢的消费者下标知道下个index是否可更新,消费者可以根据生产者下标知道自己可以处理到哪个index。
  3. 生产者和每个消费者都只是自己持用自己的数组引用,而彼此之间的引用只是可读。

上面只是简单的说一下自己总体上的理解,以后会根据源码写一点具体的细节。

二、WorkerPool 模式

我的应用场景是这样的,有一个地方可以不断的向queue里放如元素,又有多个线程同时去拿这些元素,每个元素只能被处理一次。开始我的想法是,在每个元素里加一个标志位,每个线程拿到元素都去做判断是否已经被处理。但是后来发现这样浪费资源都不说了,还可能会出错(比如一个元素被处理了多次)!后来万能的google给了我答案,这个哥们跟我的需求一样,开始的想法和我也一样,结果人家Disruptor的开发人员早就想到了各种各样的情况。WorkerPool模式就是解决了这种问题!

大致说下WorkerPool的原理:

  1. 生产者的行为不需要做任何改变;
  2. 对于属于一个WorkerPool的消费者,他们除了维护自己的index外,还需要额外维护一个共有的workSequence,这个Sequence里面记录了这个WorkerPool里所有消费者拿到的最大的index。
  3. 当一个消费者处理完了当前的元素,会根据这个workSequence,而不是根据自身的sequence去拿下一个元素。

Disruptor的源码里面就已经提供给我们了很多的模式,包括MultiBuffer和WorkerPool。我只是在这个基础上稍微做了一点点小修改。

三、实现

1. MultiBufferWorkProccesor

1 private final AtomicBoolean running = new AtomicBoolean(false); 2 private final Sequence[] sequences; 3 private final DataProvider<T>[] providers; 4 private final SequenceBarrier[] barriers; 5 private final WorkHandler<T> handler; 6 private final ExceptionHandler exceptionHandler; 7 private final Sequence[] workSequences; 8 private final AtomicBoolean[] processedSequences; //用于记录当前sequence对应的元素是否已经处理过 9 private final MultiBufferProcessStrategy strategy; 10 11 public MultiBufferWorkProccesor(final DataProvider<T>[] providers, 12 final SequenceBarrier[] barriers, final WorkHandler<T> handler, 13 final ExceptionHandler exceptionHandler, 14 final Sequence[] workSequences, 15 final MultiBufferProcessStrategy strategy) { 16 this.providers = providers; 17 this.barriers = barriers; 18 this.handler = handler; 19 this.exceptionHandler = exceptionHandler; 20 this.workSequences = workSequences; 21 this.strategy = strategy; 22 final int ringNum = providers.length; 23 sequences = new Sequence[ringNum]; 24 processedSequences = new AtomicBoolean[ringNum]; 25 for (int i = 0; i < ringNum; i++) { 26 //processor 对每个RingBuffer都维护一个sequence 27 sequences[i] = new Sequence(Sequencer.INITIAL_CURSOR_VALUE); 28 processedSequences[i] = new AtomicBoolean(true); 29 } 30 } 31 32 @Override 33 public void run() { 34 if (!running.compareAndSet(false, true)) { 35 throw new RuntimeException(Already running); 36 } 37 for (SequenceBarrier barrier : barriers) { 38 barrier.clearAlert(); 39 } 40 notifyStart(); 41 while (true) { 42 try { 43 //这一部分以后会考虑写成Strategy 44 while (true) { 45 process(0, Long.MAX_VALUE); 46 process(1, Long.MAX_VALUE); 47 process(2, Long.MAX_VALUE); 48 Thread.sleep(100); 49 } 50 } catch (AlertException e) { 51 if (!running.get()) { 52 break; 53 } 54 } catch (InterruptedException e) { 55 e.printStackTrace(); 56 } catch (TimeoutException e) { 57 e.printStackTrace(); 58 } catch (Exception e) { 59 e.printStackTrace(); 60 } 61 } 62 notifyShutdown(); 63 running.set(false); 64 } 65 66 //index表示当前处理那个RingBuffer的内容, times表示最多处理多少个元素(没有可处理元素会跳出,同时记录当前sequence的元素是否已经被处理) 67 private void process(int index, long times) throws Exception { 68 long nextSequence = sequences[index].get() + 1; 69 boolean processedSequence = processedSequences[index].get(); 70 long i = 0; 71 long cachedAvailableSequence = Long.MIN_VALUE; 72 73 while (i++ <= times) { 74 if (processedSequence) { 75 processedSequence = false; 76 do { 77 nextSequence = workSequences[index].get() + 1L; 78 sequences[index].set(nextSequence 1L); 79 } while (!workSequences[index].compareAndSet(nextSequence 1L, 80 nextSequence)); 81 } 82 83 cachedAvailableSequence = barriers[index].waitFor(nextSequence); 84 85 // have available event 86 if (cachedAvailableSequence >= nextSequence) { 87 handler.onEvent(providers[index].get(nextSequence)); 88 processedSequence = true; 89 } 90 // no event to process currently 91 else { 92 System.out.println(cachedAvailableSequence= 93 + cachedAvailableSequence + nextSequence= 94 + nextSequence); 95 break; 96 } 97 } 98 99 processedSequences[index].set(processedSequence); 100 } 101

这个类最主要的就是process(int index, long times)方法,index是RingBuffer的index,times是表示处理元素的个数。通过这两个值我们可以实现对各个RingBuffer的priority的操作,比如我的例子中就会是按照index是1、2、3的顺序,consume完每个RingBuffer所有的元素才consume下一个RingBuffer,回头我准备写一个Strategy然后更好的调用这个方法。

 

2. MultiBufferWorkerPool

1 private final AtomicBoolean started = new AtomicBoolean(false); 2 private final Sequence[] workSequences; //每个RingBuffer对应一个workSequence 3 private final RingBuffer<T>[] ringBuffers; 4 private final SequenceBarrier[] sequenceBarriers; //每个RingBuffer对应一个sequenceBarrier 5 private final MultiBufferWorkProccesor[] proccessors; //每个WorkHandler对应一个MultiBufferWorkProccesor 6 private final ExceptionHandler[] exceptionHandlers; //处理Exception 7 private final WorkHandler<T>[] workHandlers; //对RingBuffer中的元素的具体处理 8 9 public MultiBufferWorkerPool(final RingBuffer<T>[] ringBuffers, 10 final SequenceBarrier[] sequenceBarriers, 11 final ExceptionHandler[] exceptionHandlers, 12 final WorkHandler<T>… workHandlers){ 13 this.ringBuffers = ringBuffers; 14 this.sequenceBarriers = sequenceBarriers; 15 this.exceptionHandlers = exceptionHandlers; 16 this.workHandlers = workHandlers; 17 18 final int bufferNums = ringBuffers.length; 19 workSequences = new Sequence[bufferNums]; 20 21 for(int i = 0; i < bufferNums; i++){ 22 workSequences[i] = new Sequence(Sequencer.INITIAL_CURSOR_VALUE); 23 } 24 25 final int workerNums = workHandlers.length; 26 proccessors = new MultiBufferWorkProccesor[workerNums]; 27 for(int i = 0; i < workerNums; i++){ 28 proccessors[i] = new MultiBufferWorkProccesor(ringBuffers, sequenceBarriers, workHandlers[i], exceptionHandlers[i], workSequences, new PriorityProcessStrategy()); 29 } 30 //把对应的gating sequences 传给的RingBuffer 31 for(int i = 0; i < bufferNums; i++){ 32 ringBuffers[i].addGatingSequences(getGatingSequencesForBuffer(i)); 33 } 34 } 35 36 public Sequence[] getGatingSequencesForBuffer(int bufferIndex){ 37 final Sequence[] sequences = new Sequence[proccessors.length + 1]; 38 for (int i = 0;i < proccessors.length; i++) { 39 sequences[i] = proccessors[i].getSequenceForBuffer(bufferIndex); 40 } 41 //gating sequences中包含对于的work sequence 42 sequences[sequences.length 1] = workSequences[bufferIndex]; 43 44 return sequences; 45 } 46 47 //通过Buffer的index拿到对应的Sequence 48 public Sequence getSequenceForBuffer(int bufferIndex) { 49 return sequences[bufferIndex]; 50 }

这个worker pool中包含了多个RingBuffer 以及多个MultiBufferWorkProccesor,每个RingBuffer会对应一个work sequence,用于记录这个RingBuffer消费者位于的最大的index。

 

四、结尾

对于Disruptor底层的优化还有一些问题:比如说RingBuffer中存储的是对象数组,那RingBuffer中padding(protected long p1, p2, p3, p4, p5, p6, p7;) 起了什么作用?对象数组的引用在内存中是如何的形态?等等

同时Disruptor的源码里面还有很多很好的模式也值得去学习。

 

这个只是一个Draft的版本,而且我也只是简单的测过,后面整理和修改好了会上传到我的github。对于一些错误的地方,希望大神可以指出来,轻点拍砖。。。

Posted in C, JS, Uncategorized | Tagged | 1 Comment