2016-02-22

在外的元宵节

　　春节假期转眼就过去了，感觉是过得最快的一个春节。马上又面临新的挑战，正处在一个学习
和工作的过渡期，莫名的烦心事和压力随之而来。开学时间很早，之前所有相聚的年轻人一股脑儿
全离开了，为了明年的春节聚首又回到城市奋斗，看得让人心慌，想到未来我在哪里，是否也像他
们一般匆匆来去?现在的娱乐方式多不胜数，但是人的情绪来源越来越少，仿佛只有通往金钱的道路
才能让人心旷神怡，只有人人羡慕的生活才是成功的人生。在这种环境下，假期像是一场鸵鸟的避风
动作，暂时没有烦恼，心却没有安宁下来。于是，剩下的日子，终于像风一样迅速消失在心灵的沙漠
中。
　　元宵节之前的几天，我就已经来到了实验室，开始了日复一日的工作，和同年人继续没有交流却
保持默契地竞争。突然发现，原来节日本为人带来欢乐的意义就是这样丢失的。你还有很多工作，前方
还有许多美好的憧憬在你到达之后才能实现，于是你忽略了路边的景色，着急地向目标走去。然后终于
到了这个目的地，但是你却发现，抑或是有人告诉你，前方有更漂亮的风景，你如果到达那里，人生会有
更精彩的不同……如此这般循环几个光景，你的人生就这样匆匆而去而鲜有发自内心的愉悦。
　　春节期间看到了一个讽刺的帖子，其中最主要的内容是:”真正好的办法是巧妙引导，控制节奏，让
臣民们始终保持一种奋斗的状态。20出头，头十年，让他们去为房子，车子，娶妻生子忙，第二个十年，
让他们为房贷，车贷，子女教育经费去忙，等到了第三个十年，就得为老来医保，儿女成人等做准备而继
续忙。如此一来，人生最黄金的三十年不经意间弹指而过。在臣民们为自己所谓生活而忙碌时，就不太会
有人能静下心来质疑苏丹统治的正当性，合法性等等命题。”
　　这其中，有多少人不是我们自己给自己定义的成功标准，或者在外在的氛围和期望的影响下，进行自我
审查和个性阉割，从而成为“成功”这条路上的一个急匆匆的行者的呢？

2016-02-22

进展汇总,新阶段计划

年前的自我安慰

新年之前，给自己画了很多美好的期许，如同中学生涯的放假期间，带回去很多课本和试卷，
结果又原封不动地带回学校一样，这些定下的计划鲜有完成。大概也就是没有手生而已。我把
这种现象叫做心理上的自我安慰。

第一次开会之前的补救

半个月过去了，我又回到那个朝九晚十的生活轨道，赶紧在进度报告之前，完成一些工作。经过
几天的不断写代码和测试，也算是完成了以下任务:

实现了文件按数据块的对称加、解密
理解了一部分冗余分散加密的原理
再加上一些研究过程中的速记note,应该可以进行下一步的工作了。

下一步的工作

这大概是我学习生涯以来，如此有总结性和计划性的时刻，办公的电脑桌面文件夹里，都是各种各
样的todo-list和note。
下一步主要就是实现caont-rs冗余加/解码了，因此需要了解迦罗瓦运算，详细地阅读原作者的
实现了。
过渡期就是如此麻烦，还需要留心即将到来的暑期实习招聘，一边需要做准备了。毕竟不想再经历本科
毕业时候的迷茫和毫无准备的仓促。

2016-01-29

写在放假之前

匆忙与无所适从之间

　快到猴年春节了，这一年过得很累，发生了太多的事，压力也大了起来，未来的工作，现在
的生活…都交织在我的脑海里。很想回去舒服地躺在床上看看书，或者就是发一下午呆。可
惜时间不等人，两周里还有很多要完成的事。
　不过，能过第一个想回家吃妈妈做的菜的春节，我的心情还是有些愉快迫切的、　

假期的遐想

　最近的两周老板也没怎么来，我手头的事情也比较棘手，有些像刺猬无从下嘴的感觉。检讨
一下工作就是零星做了些面试算法题，leetcode英文题对于目前浮躁的我来说有些难，DP、背包
也没有看，回家需要复习一下算法了。文件系统，加密模块,也需要做个雏形出来。
　很想潇潇洒洒地在家里四处游荡，和朋友去爬山，然后静静坐在山峰最高处，静静地注视着芸
芸众生、人间烟火，做着无边无际的梦。

2016-01-21

leetcode-319的算法思考

题目

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3.

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].

So you should return 1, because there is only one bulb is on.

题目含义

就是说给n个开关分别对应控制这n个灯泡的亮灭，步骤如下:

开始时开关都是关的，为方便叙述，位置从1开始
step=1,将所有位置的开关打开
step=2,将所有位置为2的倍数的开关转换状态
…
step=n,转换完开关后,统计还有多少灯泡开者

解法

1.直观解法

思路

分析完题目后,首先想到的就是把开关这些控制流程自己模拟
一遍，用布尔数组模拟开关，最后统计为true的开关数就可以
了。

那就开始写吧，leetcode支持c/c++，感觉够了，至于能不能
用STL库还不清楚，自己动手写一些常用数据结构，虽说性能有
损失，但是为了AC,也只能自己注意性能了，尽量不要手动分配
大的数组。

int bulbswitcher(int n){
    //c99支持的关键字_Bool,ansi不支持,leetcode测试通过
    _Bool *p=(_Bool *)malloc(sizeof(_Bool)*n);
    if(p==NULL){
        exit(-1);
    }
    //全为false,避免求反时未定义
    memset(p,0,sizeof(_Bool)*n);
    
    for(j=0;j<n;++j){           //step 1->n
        for(i=j;i<n;i+=j+1){    //对应的开关,每次跳跃的间隔j+1
            *(p+i)=!(*(p+i));   //不知道编译器是否会优化，所以采用这种直接寻址方式
        }
    }
    
    //统计为true的开关,如果有c++的accumulate更好
    sum(p,n);
}

上传到leetcode jude,不一会儿出现了Limit except，发现它的测试数是10000000,
总用时1+s,这么大数字居然超时了.我自己在线下测试的结果：

普通编译:
开启-O2 优化

可以发现这种算法复杂度O(n^2),数字一大性能就不行了。普通编译结果也是超过1s,看来leetcode没有做优化,并且超时时间设置1s,
如此只能再想其他解法.

2.进阶方案

总觉得这样转换的状像是符合某种数学规律，也许是常年的理工教育培养了这种直觉，
我就试一试究竟有没有规律,基于现有代码很好改动。

void test(int max){
    for(int i=0;i<max;++i){
        printf("%3d:%3d\n",i,bulbswitcher(i));
    }
}

打印结果:
leetcode-3

居然有这么多一样的，看起来像台阶一样，必须满足某种条件才能增加一级.
那我再改进一下试探方法,为了一查究竟这么多相同的数字有什么关系，以及开关
数n和最后结果的关系，采用哈希表去做，c没有，其实开个大数组也行，我这里用
的是Go。

func test(n int){
    m:=make(map[int]int,n)
    for i:=0;i<1000;i++{
        m[bulbswitcher(i)]++
    }
    
    //无序表，对key排序    
    sort.SortInts(map_keys)
    for _,k:=range map_keys{
        fmt.Printf("%3d:%3d\n",k,m[k])
    }
}

运行结果:
leetcode-4

果然有关系!原来最后的结果对应的原始开关数n是一个奇数等差数列:

第i级,ret表示n在这一级内，则最终的结果
cnt表示有多少个n是对应ret这个结果的，也就是n的范围
关系如下:
       2*ret+1 = cnt 
=>     ret = (cnt-1)/2

现在我们只要求出这个范围cnt就行了。由于k对应的最后的结果，而v对应n,表明我们需要判断这个n落在哪一级内，
也就是将v加起来，直到加到第i级超过n的值，那么n就是在这一级内。
基于这种思想有代码:

int magic(int n){
    if(n<=0){
        return 0;
    }
    int i,cnt=0;
    for(i=3;cnt<n;i+=2){ //第i级所包含的原始开关数范围,cnt统计n之前的数量
        cnt+=i;
    }
    return (i-3)>>1;//因为数列没有cnt=1对应的ret
}

改进之后算法复杂度为O(n/2)=>O(n)，现在上传改进的代码,这次通过了，耗时0s,但是在分布图里，
居然只打败了同样用C的6.83%,看来很多人结果比我好啊，也不知道
它的测试数字是不是都是一样的。

看一下能不能继续改进。对了，奇数等差数列不是有求和公式吗?我们知道n，直接求它在那一级的范围
内，不就是ret的值么?避免了一个个去加然后判断,这就是最终版本的方法。

3.最终解法

因为奇数2n-1的求和公式:

对于上面的关系有:

         sum = (2*ret+1+3)*ret/2
     =>      =  ret*ret + 2*ret

所以反推有:     
     ->    n <= ret*ret
     =>   ret = sqrt(n) 向下取整

这种解法C函数表示就是floor(sqrt(n))
所以改进的代码:

int final_magic(int n){
    if(n<=0){
        return 0;
    }
    return floor(sqrt(n));//隐式转型
}

这样简单多了。然后上传leetcode测试结果,35个测试全部通过，
耗时0ms，居然还是打败6.88%,郁闷

4.三种解法的单元、性能测试

为了测试的方便，我将代码改写成go，然后使用自带test，之前2方案
比较快，所以以它为基准测试其他2种正确性。开始的时候都是手写的测试
case,用map去对比,本想设置测试上限10000000，但是超过了10分钟，出
现了panic，10万以上第一种方法就很慢了。
测试代码部分:

const(
    MAX = 10000   //测试范围
)

//通用测试方法，传入测试函数参数
func test(t *testing.T,Func func(int) int){
    for i:=0;i<=MAX;i++{
        if Func(i)!=Magic(i){
            //结果出错
            t.Errorf("%3d:%3d calc failed.",i,Func(i))
        }
    }
} 

TestCommon(t){
    test(t,Common)
}

TestFinalMagic(t)

性能测试，代码类似:

//通用性能测试方法
func bench(b *testing.B,Func func(int) int){
    for i:=0;i<=MAX;i++{
        Func(i)
    }
}

BenchmarkCommon(b)
BenchmarkMagic(b)
BenchmarFinalkMagic(b)

测试结果:
leetcode-5

总结

第一种最符合程序员解决问题的思维，也很容易理解。后面的方法已经脱离了问题，变成了纯粹的数学问题
无奈第一种性能要差得多。这大概就是提醒我们，抽象生活问题成数学问题，然后去解决它吧。很惭愧，我
没有通过分析问题去提炼其中的数学规律，而是凭感觉试出来的，
最后，学到的是go中的函数参数了，顺便复习了C语言的一些内容。

后记

未改进的版本相比改进版本来说，主要的耗时操作是两重循环，一个是O(N^2),一个是O(1);因此只有在n比较小
时，下文针对未改进版本优化才有价值
对于这种状态转换问题，可以使用bitset解决，由于STL对位图的优化，每个状态位只占1个bit,比bool变量都
快，而且调式更为方便，效率也比数组高很多。
针对每个数字，能被整除的相应位置反转状态，最后只需要统计其中为1的数量即可
n值小的时候，性能比直接找出规律的方案差不了多少，主要的耗时操作是两重循环，所以这种方案也只有n较小
才可行，题目的目的是让我们找出规律，使用O(1)的算法。
最后，代码如下:

2016-01-21

2016年第一场雪想到的

早上一如既往的起床洗漱然后出门，走到楼道口才发现今天居然下雪了，