111111

六一儿童节恩。

因为虚拟空间问题，所以认为修改了日志时间，以此来纪念这个悲催的六一：

 

你怎么就这么忍心离我而去了呢！

过去的四年，一起去实验室，一起上课。你陪我去过清华园火车站，去过家乐福。你怎么说走就走了呢？连一声道别都没来得及说出口。

——致那些年，我骑过的自行车。

伪物语

借用了一个动画的名字，但这篇日志却并不是说观后感的。
而是说我这个人。
该怎么评价我自己呢？得出的一个结论，就是伪物语。
伪硬件控：作为一个学CS的，对于硬件有一定的偏好也是很正常的。然而，却是伪的。也许我可以头头是道说出这个显卡不行，这个CPU性价比低等等，但是距离真正的硬件控，那些发烧玩家而言，却差了很远。
伪火车迷：从小就喜欢交通工具，比如还记得6岁的时候夏天每天早上5点起床去看家门口128路公交车终点站的发车情况，也总是可以算准头班车的时间。喜欢坐火车，然而，仅此而已。对于真正的火车迷而言的运转，却是一次也没参与过。
伪数据控：喜欢收集数据，经过我硬盘的数据很少有删掉的，特别是动画、电影。然而，却不是真正的数据控，电影、动画的存量相比那些收集控而言只是零头而已。
也许我做过很多事情，但终究没一样做到极致的。比如体育课，明明选过棒垒、击剑、地板球、素拓，高中学过网球、乒乓球、羽毛球，真的跑去打了，估计只有被虐的份。
比如写过c++，写过java，写过php、vb、js、object-c，编过android、CUDA、MPI、hadoop，却终究没有一样精通。
比如偶尔打打游戏，玩玩NFS，开得过电脑，却总也没法取得全部的白金奖杯。
比如小时候就开始打牌，到现在也就初学者的水平，牌好打得一般，牌差就一泻千里了。
比如搞竞赛，化学看上去还不错，终究只拿了个市三等奖，而且只不过是安慰性质的。
比如喜欢动画，看过不少，却总也没法像元火众一般能够聊得起来。
不胜枚举。
所以说，到头来发现，自己终究不过是个伪物。什么都接触一点，什么都拿不出手。
也于是乎，写下了这什么都不算的日志。

备案备案

之前的虚拟空间放在香港，总觉得需要国际网网关才能连接有点小不爽，于是在美橙买了个虚拟空间，结果不备案都不让绑定域名。。于是就着手备案，过了25天（4月10号美橙提交备案至北京管局），备案终于下来了~于是哥的网站也正规合法了~（虽然主页不能放blog，因为没有blog专项备案，这个因为有评论功能所以得有计算机安全员证书，真麻烦……）
anyway，好好建设自己的网站吧~

2012校园招聘–求字符串的最长重复子串问题

问题概述：

输入一个字符串，如何求最长重复出现（至少出现2次）的子字符串呢？比如输入ttabcftrgabcd，输出结果为abc，canffcancd，输出结果为can？

http://hi.baidu.com/zhang_daxia/blog/item/c9ea38f24e3bf39eb801a040.html中间给了一个后缀树的方法，但是其算法复杂度是O(n^2*log(n))（因为中间的qsort中间的strcmp的复杂度也是O(n)），实际上这样的题目最多O(n^2)就可以了，如果借鉴KMP的方法则可以达到O(mn)，其中m是最长重复的子字符串。下面是我的算法，其实很简单，类似拉链那样逐位比较就行了，注意字符串不能重叠（比如ababa，则最大重复则为ab而不是aba）。因为对KMP不熟悉，所以就没有放上O(mn)的算法。。

C++语言: 高亮代码由发芽网提供

#include <iostream>

#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define LEN 1000
void work(char *s)
{
    int i,j;
    int len=strlen(s);
    int al,ar,bl,br;//left right of the simistring
    int maxlen = 0;
    char maxstr[LEN];
    for(i=0;i<len;i++)
    {
        al = 0; ar = 0; bl = i; br = i;
        for(j=i;j<=len;j++)
        {
            if(ar-al>maxlen)
            {
                maxlen = ar-al;
                memset(maxstr,0,LEN);
                strncpy(maxstr,&s[al],ar-al);
            }
            if(j==len) break;
            if(s[j-i]==s[j])
            {
                ar++;
                br++;
                if(bl>=ar)    continue;
            }
            bl=br=j+1;
            al=ar=j+1-i;            
        }
    }
    cout << maxlen << " " <<  maxstr << endl;
}
int main()
{
    char s[LEN];
    while(cin>>s)
    {
        work(s);
    }
    return 0;
}

深度优化：学习SSE指令

程序跑的太慢怎么办？之前我给出的答案是：用x64环境编译执行程序；用多线程、多进程模式；用CUDA加速。而现在，又有了一种新的解决方案：用CPU的SSE、SSE2等指令集。

因为处理图像数据时大量用到浮点数操作，而且都是一连串一起使用的，所以，用SSE2加速可以取得较好的效果。参见http://dev.gameres.com/Program/Other/sseintro.htm的相关代码，自己模仿了一下，发现很容易写：

int calc_simi(float *feat)
{
int i,j;
float *a,*b,t;
float min_dst = 99999;
float dst;
int id=0;
for(i=0;i

其中dic是一个二维矩阵，目的是求出当前feat向量和二维矩阵中哪一行向量的差最小，返回这个id。calc_simi是普通的实现，calc_simi_sse是利用sse2指令集实现的。

废话不多说，看时间测试时间：

x86 x64
precise 1224 371
fast 301 302
precise_sse 146 114
fast_sse 148 119

其中，precise和fast对应编译器选项当中浮点数精度要求（因为发现结果木有差异。。），_sse代表利用了sse指令集（编译器优化当中不要选使用sse2，这样会变慢……），x86和x64代表编译环境，由此可以发现，sse会快，而且在x64下比fast浮点运算还快了2.5倍左右！因为sse2每次处理4个浮点数，所以最多也就快4倍，效果很显著了~

so，最终版的优化看来会结合sse2、多线程技术吧（因为CUDA和sse2冲突，而sse2稳定……）

关于停自行车的一件小事

今天实习回来，考虑到学校已经没有食物供应了（后来才发现学一小白房还开着……），于是去西南门外觅食。停自行车的时候，想起上次在48楼（西南门口的寝室楼）前停车的事情。

那天中午停车的时候，突然一个大妈模样的人冲我问：“同学，你是在这停车嘛？”我当下就心一惊：这边不能停车么？不对呀，边上都是自行车呀；找我来收费？这是学校又不是家乐福呀；女生楼前禁止男生停车？。。。还在犹豫着到底犯啥事了，那大妈对我说：“谢谢你啊，把车停到黄线以内”。。。于是我彻底无语了，只能笑笑。。原来这是48楼的楼长，估计是刚吃好饭回来；至于为什么对我这么说么，估计是平时大家停车的时候比较随意往外一放吧。。。

关键是，这还没完。因为要等的人没来，我就在西南门口等人，结果那楼长在门口看到一个同学随意停车，就对那人说：“同学，停车请停到黄线内，要像那位同学学习”顺便指了指我，顿时好冷啊。。

其实，这篇日志的主要思想是：小汤圆小浩浩王胖胖你们快回来啊！一起去fb吧！我可不想再去木桶三国那样的快餐店了，又难吃又烫（。。。）居然还没倒闭。。

想做的事太多，于是就什么都不想做了。。

这两天发现，自己有太多的事情想做了：

想学html5，想做出绚丽的网页，并且把自己网站这个大坑填了；

想学android编程，想把人肉系统移植到手机上，这样就能实时人肉了。。；

想减肥，面对即将1:1的身高体重比，实在是心情复杂啊。。；

想看各种电影美剧，寒假刚把tbbt从头看到现在，还想看各种经典的美剧英剧啊~；

想弄完opencv的实例，这个是数字媒体助教需要完成的任务（所以不能算是“想”了吧。。）；

想好好搞搞研究，早点发一篇paper，这样就可以安心度过研究生生涯了；

。。。

但是，纵使有着这样那样想做的事情，真正空闲下来了，却一件也不会去干（看电视剧倒是会看的，但是看着看着就累了。。于是上会网，时间又过去了）。我发现，自从换了手机可以用wifi上网之后，人人、微博对我的毒害加深了很多，经常毫无意义的就去刷新人人、微博。估计一天花在这些无意义的sns上的时间都得有两三个小时了吧。

但就是不想做别的。

天杀的，我这究竟是怎么了。。。

告别旧手机

虽说G12买来已经有三个月了，但当时6120c里面的数据并没有复制出来。因为快要回北京了，所以花了一个晚上倒腾旧手机，算是完成了原有手机数据的备份。

第一个备份是通讯录，这个问题不大，全选、复制、保存到sim卡，然后复制到新手机即可。

第二个是短信，这是一个大头。自从08年8月买了6120c之后，收到的短信除去垃圾短信，基本都没删过，还给每个人设了一个单独的文件夹保存。于是乎，对于手机内的短信，通过nokia的PC套件复制出来，结果发现是unicode编码的。。找了几个软件不好用之后，决定自己写程序来改编码。。这时候，之前写的“成语典故”程序就发挥了作用，因为主要是unicode转ansi，所以有现成的代码可以用了。所以说，程序员是一个积累的过程。。。存储卡内的短信则相对简单，用“短信管家”这个应用能很方便地转成txt，而且是一个文件夹一起转，所以重复了几十次机械操作。。

第三个是日历项，这个nokia的pc套件也有相应的复制功能。

第四个是记事本，这个没办法读出来，于是用蓝牙发送到G12，然后存到电脑，把文件名改为记事本当时的日期，over（发现了很多有意义没有意义的记事本项……）

这样折腾了一个晚上，终于把6120c里面有信息量的数据全部复制了出来。本来还想把6120c升级到7.02版本的，无奈刷机教程都不好使，所以只能作罢。

————————————————

顺带怀念一下之前用过的手机吧~

最早的手机是老爸用过的摩托罗拉V998+（初三-高一），当时算是很热门的手机了，只不过各种问题，因为是翻盖的，所以最终的结局是屏幕线坏了。

之后买了一个新的手机，诺基亚6100（高一-大一），当时也要1000元了吧，低端手机，128×128的分辨率，65536色，优点是耐摔，缺点是没什么游戏，而且当时也不知道用网络，此外也不能拍照。最终的结局是用得不想用了，还没坏。。只不过电池有点鼓起来了

大一暑假买了新手机，诺基亚6120c（大一-研一），当时1250元，外加一块电板一个存储卡，一共1500吧。算是用得很顺的手机，因为功能强大，而且价格便宜，在塞班论坛上也是很热闹的，当时买来也各种研究折腾。优点还是耐摔，而且运行流畅（比N73流畅多了），而且可以上网，当时各种安装游戏来玩，不亦乐乎。缺点是摄像头摄像不给力，虽然照相可以到1600×1200，但是摄像只有320×240而且还是15帧的，所以基本上看不清拍了什么。。对于我等偷拍达人自然是不顺手啦。。结局是用到11年11月，然后闲职，现在给老妈用。

研一买了HTC的G12（研一-？），加上电池存储卡一共2600元，挺贵了。不过运行很流畅，而且触感不错，而且还默认解锁了。因为是android的手机，所以装软件很方便，用个豌豆荚什么都解决了。 优点是配置较高，运行流畅，想要的功能都有了，摄像头500w像素而且支持720p摄像，已经很符合我的口味了（虽然成像质量一般）。缺点是电池不耐用。没办法，谁让它是android呢。。

从这为数不多的手机使用历史来看，手机产业还是发生了很大的变化的，从最初的黑白手机到彩屏到触摸屏；从发短信打电话的基本功能到网络到各种应用、游戏。可以说，正是手机丰富了我们的日常生活，但是同时也浪费了我们大把的青春岁月。。想当年高中的时候我的手机只是每天给老爸打个电话而已。。大一的时候手机甚至不是每天开机的，而现在手机已经24小时不关机了。这其中的变化，估计未来的小朋友是不能理解的了。