这个周末很颓废，几乎什么也没干。谴责一下自己。题目:http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1036这题就是要求一个稠密图上的最小生成树，并且求在这个生成树上的一个点，要求这个点到其余所有点的距离和最小。题目条件保证生成树唯一。解法：首先求最小生成树，用prim。每加入一个新的节点时，计算这个点到已经加入的所有点的距离。因为最小生成树中任意亮点的通路唯一，因此可以直接与prim中pre数组中的点到其余点做和求出。代码:依然点击这里下载

昨儿看某小孩状态，关于雷全胜老师的星座问题。怀疑雷全胜老师的星座到底是不是金牛的。我也很好事，所以干脆也Google了一下，果断打开Google.com，敲进“雷全胜”，回车。得到的结果中除了第一条收录来自评师网，其余大多与”纳达尔膝伤复发落后退赛穆雷全胜首入澳网四强”有关。如图：

搜索引擎对动态页面不是很友好，像我的博客之前显示文章都是用article.php带查询方式，也就是形如article.php?a=12的方式。但是搜索引擎对后面的查询字段通常忽略，把所有article.php当作一个页面，因此多个页面无法被搜索引擎捕获。我们可以通过重写url将地址静态化，改成12.html等形式，这样浏览器就可以很容易的区分不同页面从而抓取。伪静态方法有很多，我这里用的是.htaccess方法，利用apache的rewrite模块进行，里面涉及到非常简单的正则表达式知识。这个方法主要是创建并编辑.htaccess文件。一、创建.htaccess因为我通常在linux下开发web因此没有无法生成.htaccess文件的困扰。对于windows用户，可以新建xx.htaccess然后在cmd里copy xx.htaccess .htaccess得到这个文件。这个文件可以用任意一款文本编辑器编辑。二、书写rewriterule这里首先打开.htaccess文件，然后输入如下文本：RewriteEngine OnRewriteBase [path]RewriteRule [from] [target]其中[path]是指从web根目录开始，要重定向的文件所在目录，比如本站，article.php在blog目录下因此[path]写成/blog。[from]是你希望用户在浏览器里输入的url形式，比如我这里希望用户输入 一些数字.html的形式，那么[from]写成^([d]+).html。这里的^表示目标串的开头，表示从开头匹配，一对圆括号的作用是今后引用它，而一对方括号的意思是将它包括的东西算作一组，后面的加好表示前面的一个或一组模式出现1次或以上次。因为.在正则表达式里有特殊含义，因此要加将其转义。[target]是要转向的文件，因此[target]在我这里是article.php?a=$1。这里的$1就是对前面的小括号的模式的引用，前面如果出现多个小括号就是匹配第一个，$2就是第二个，以此类推。值得注意的是，如果页面内大量链接以及图片的引用用的是相对路径形式，如x.jpg，需要保证重定向后目录层级不变，否则会造成链接失效，图片无法显示的问题。这个问题很容易理解，因为重定向发生在服务器端，因此浏览器并不清楚目前的目录到底在哪里比如在浏览器里输入地址www.domain.com/a/b/c.html并在服务器端指向www.domain.com/index.php?a=a&b=b&c=c文件，这是就会出现问题。原因是浏览器在查找相对路径x.jpg时，会在www.domain.com/a/b/目录下查找，而事实上并不存在这样一个目录。这个问题的另外一个解决办法是所有的链接都采用绝对路径形式，不过这样对今后网站转移和维护都会造成困扰。如果网站会频繁转移，又想用绝对路径，那就只能定义一个全局变量或者常量使其值为”http://www.domain.com/”这样，只要把这个变量在需要链接的位置的相对路径前输出即可。网站转移的时候只要修改这个全局变量。三、上传.htaccess文件书写好这个文件之后需要将这个文件上传到服务器。目前国外的linux主机几乎都支持这个功能，因此只要把这个文件传到想要作用的目录下即可。四、.htaccess的其他功能这个文件功能其实很强大，也可以自定义404错误等各种错误页面。网上这些资料很多。这段时间我会将站内几乎所有的链接都静态化，这可能会导致很多错误，因此只能在错误中前进了。

libevent是个事件驱动库，网上关于它的文章很多，这里就不再多说了。如果你搜到这篇东西，一定是想要在你的ubuntu10.10下面安装/使用它，或者说你遇到了问题。这个问题很可能就是你遇到了段错误。通过gdb调试后发现问题出在libevent中。然后你很无奈。其实问题不在libevent上，而在安装libevent的过程本身。我是采用源码的方式安装的libevent。http://monkey.org/~provos/libevent/在这里下载到你想要的版本后，转到你下载文件保存的目录，tar -xzvf 你下载到的文件名。然后进入解压出来的那个目录。之后./configure，然后make，sudo make install。顺利的话你就安装完成了，看起来很平常。但是当你使用它的时候就会出现问题。这很可能是段错误。问题的原因我现在就开始解释。ubuntu10.10默认会安装一个libevent1.4.2版本的libevent在你的系统里，这个版本的libevent在/usr/lib目录下有个libevent.so.2的文件。而你用源码安装的libevent的so文件保存在/usr/local/lib目录下，这样当你在用编译器选项-levent的时候，系统就在/usr/include，/usr/lib，/usr/local/lib三个目录下寻找libevent.so这样的文件作为连接时候用到的目标文件。问题就出在这里，系统首先找到的是/usr/lib/libevent.so.2这个文件而不是你安装的/usr/local/lib这个目录下这个版本对应的目标文件，于是连接产生的程序就会读取一段不应该读到的内存，于是bug就产生了。因此，在安装libevent之前，首先确保你的系统里是否已经安装了其它版本的libevent，如果发现有安装，那么果断卸载之。 更新：libevent的official site上的document说struct event需要分配到heap（堆区）。如果分配到stack，当临时变量神马的用多了会导致很多意想不到的问题，博主这两天就深受其害。

好吧，不得不承认，23三周岁的生日来了。时间过得飞快，一转眼，我就已经超过天朝的法定适婚年龄一年，上大学三年，高中毕业四年，成年五年了。仔细想想，在飞逝的时光里，我已经很久没有停下埋头前进的脚步，好好看看自己，想想过去了。因为最近我时常觉得，自己突然过丢了好多年，怎么都回忆不起有关一段时间的任何事情。今天，我23周岁了，23年前的今天不知是北京时间的几点几分几秒，我出生了。出生时候的事情我不记得了，只知道奶奶在得知我是个男孩的时候说了句有关一种很有力量的家畜的话。从那个时候起，我成了我们家这一代的第一个男孩，至今没变。后来我在洗衣机的甩干筒里看老妈做家务，去托儿所看一个小光头以一种可笑的姿势用勺子吃饭而我用的是我的“小龙叉”，领着走路像企鹅的小朋友到家里玩录音机录下了一些跑调的儿歌，把自己反锁在防盗门里打不开门。再后来，搬家了，听了很多故事，背了很多故事，成了故事大王。直到前两天看到一篇有关小孩记忆力的形成的文章，才知道，3-6岁这一段时间如果背诵很多故事，十分有利于记忆力的开发。谢天谢地。再再后来，上小学，上初中，上高中，复读。大学这三年，我觉着自己变化不小，虽然高中毕业的时候我也这么想过，上大学之前我也这么觉得过。当然，也有很多没变的地方，嘴损说话直没变，不爱学习没变，小心眼没变，从前交下的很多好朋友没变，身高也没变。大一的时候总觉得自己的梦想跟现实越来越远，说过这么一句话：梦越追越远。经常喝酒，经常喝多，经常喝多了就胡闹，丢人丢到不知哪里去了。后来闹够了，也冷静了，传说中的大学的迷茫就这么一折腾就过去了。后面的生活很平淡，没啥惊喜也没啥打击。一转眼就到了今天。23岁生日前一天，早上来实验室完成了一组实验，晚上得知，那组实验的结果很好，可以进一步进行更大规模的实验了。中午睡了很久，开了组会，听了TAMU的一个老师的讲座，讲座结束后，都老师跟我说：他们做的这个方向跟我们今后的研究方向很契合，当然你这段时间很忙，等过了这段……我突然觉得，即使这篇TPDS完成了，我是还会继续很辛苦。23岁前一天已经在我敲这篇东西的时候画上了句号。23岁开始的第一天，我要通宵做机械设计的课程设计。写这篇东西之前，我总觉得这么久不写字了，会有很多话滔滔不绝的跳到屏幕上，结果我一字一顿的写到这一行就已经没什么好说的了。我觉得，这可能就是我的变化了。不过在结尾的这个地方，总要给自己打打气。记得大学前的那个暑假，我在清华门口逛了一圈，当时看着清华的校门跟主楼，就在想，这个地方离我实在太遥远了。不过就在刚过去这个暑假，直到今天，我每天进出当时自己感慨的校门，每天在那座主楼里的一张桌子前工作。想想这些，我觉得自己已经在路上走了很远了。希望明年的这个时候，我能在大洋彼岸CMU的某个实验室里，写出相同的句式。很久不这么写字了，就到这里吧。祝我生日快乐。

这个问题折腾了我有一个星期了，因为最近一直在搞有关磁盘的I/O的测试，因此需要绕过或者关闭VFS的cache直接对磁盘进行读写。Google过之后发现基本上想要关闭cache是不可能的，只有想办法绕过了。于是很自然的想到了write()和read()这两个东西，可是当时并没意识到buffer跟cache并不是一个东西。write()跟read()虽然叫直接I/O但事实上他们只是绕过了buffer，也就是说在读入跟输出的时候不进行任何的缓存，但VFS本身的cache仍然存在，VFS仍然会选择在合适的时候将cache的数据写入磁盘。 于是找了很多方法，有的是通过drop cache的方法，就是”echo 1 > /proc/sys/vm/drop_caches”这样的方法，不过这种方法只能清除一次cache，读写一次，很是麻烦。于是果断放弃了这种不靠谱的方法。 后来想到了APUE上没有提到的一个O_DIRECT flag（因为APUE讲的是UNIX编程，当然没必要照顾到GNU Linux特有的东西）。具体怎么用呢，下面就来说说。 首先在文件头需要定义 #define _GNU_SOURCE 然后，这个东西用在open()获得文件描述符时所填写的第二个参数，也就是open(path,flag,mode)的第二个参数。比如你要以写方式创建一个路径为”/home/user/test.test”新文件，并且要直接I/O绕过cache，就可以这样写： int fd=open(“/home/user/test.test”,O_WRONLY|O_CREAT|O_DIRECT,S_IRUSR|S_IWUSR); 之后在你需要read()或者write()的时候，传入的buffer的首地址，以及buffer的大小都必须跟文件系统的page size对齐。这个page size可以通过getpagesize()获得。memalign()可以用来得到这样一个buffer： int buffersize = getpagesize()*page_num; int pagesize=getpagesize(); char * buffer = memalign(pagesize, buffersize); 之后你就可以用这个buffer来read()或者write()了。如： read(fd,buffer,buffersize); 要注意的是，在2.4以前的kernel里，buffersize必须是页大小的整数倍，并且buffer指向的地址也必须是页大小的整数倍。用上面的简单计算就可以得到满足条件的buffer。之后的I/O便是完全绕过cache的direct I/O了。 PS:完成这个之后，周末就可以放心的回家了，很开心。

没想到会这么快就被和谐了，贴个youtube的链接吧，有条件翻墙的童鞋们自己去看吧。http://www.youtube.com/watch?v=bXJJjoJ9cMI

终于成功的将主机迁移到EcVps上了，用清华的网络访问速度不错，唯独可惜的是在北邮的素的仍然不够理想。迁移工作比较顺利，只是因为这是第一次在vps上搭建LAMP环境，还是花了一些时间在这上面的。问题主要是虽然Ubuntu/Debian的包管理功能很强大，但对于Apache2和PHP5的配置来说，就显得有些麻烦。之前一直用虚拟空间，因此不用自己操心它们的配置，而在自己的电脑上折腾时，因为除了MySQL之外我都是用源码安装的，因此配置文件位置相对集中，比较容易管理。有空会写写有关Ubuntu/Debian下的Apache2和PHP5的配置方面的东西。心情不错，所以要给EcVps打个广告。这家提供商是香港人的，因此很好的支持了中文订单，以及支付宝付款。对于我这种懒人来说还是很好的福利。Ticket处理速度也很快。官网上声称在一直不间断使用的情况下永不涨价。除此之外，这家提供了OpenVZ和Xen两种方式的vps，选择余地不错。网上关于这两种方式的讨论很多，这里就不多介绍了。我本身选择的是Xen方式，主要是因为Xen方式提供了swap，对于很耗内存的程序来说支持较好。这里补充一点是从价格上来看这家的OpenVZ方式的vps并没有较Xen方式的便宜，而且他们也声称自己不会超售，所以购买OpenVZ vps也是不错的选择。这个页面提供了一些下载测试用的链接，可以测试一下。我选择的机房位于拉斯维加斯:10MB : http://72.46.135.3/10mb.zip100MB : http://72.46.135.3/100mb.zipping大概在200ms左右，还是很满意的，下载速度平均在400Kb/s左右。最后，介绍下本站的新功能glype网页代理。可以用来访问一些在功夫网之外的东西。因为这个东西的官方于2009年就不再更新了，所以对于功夫网近期的更新来说，不进行配置的glype是没办法翻墙的。还是，有空的话，我会写写glype的配置以及它的代码。PS:周末一个人在实验室里呆着的孩子伤不起啊。。。PS after PS:不过好处是得到了个清华百年校庆的mark杯，灭哈哈。

这篇东西不是教程，也不确保一定成功，写出来当作是科普了。我是不喜欢写这类东西的，不过为了赚取点击，就写这么一篇东西吧。之前在北邮人论坛看到这么一个帖子，标题是：听说方滨兴院士是贵校校长。进到帖子里发现内容是：特来鄙视。我本人虽然对校长没啥特别情感，但是毕竟是我亲爱的校长，您确实不至于这么直接的来找事吧。讨厌GFW，来骂人，来鄙视也是没用的，不如自己翻墙。翻翻更健康。不过翻墙出去看什么，这个我确实管不了了就。那些个XV男女主角之间的爱情动作片其实完全没必要翻墙出去看么，直接点这里去看吧，也不用那么麻烦继续往下看了。好吧，软文到此结束，下面是正文。这里要介绍的是用ssh通道翻墙的方法。ssh的全称是Secure Shell，也就是安全shell的意思。本质上来讲，它就是用来跟远程计算机传输数据的，至于什么数据，看用户的具体应用了。比如你要翻墙，那它就传送html等网页相关的内容。要想这么做，首先你得有个可以接收你ssh连接，并且接入了墙外网站的服务器。你可以自己购买vps，可以用你的个人网站的虚拟空间提供的ssh，或者到这里领取免费的ssh帐号。有了帐号密码之后，如果你是windows用户，需要到这里下载Tunnelier (SSH Client)这个东西。之后就是安装。装好之后打开它，在打开的窗口中找到Login选项卡，填写下面的内容：host(你的ssh的地址)，port(一般情况下默认为22，可以根据你的ssh的实际情况填写),username(你的ssh的帐号),password(你的ssh的密码)。之后到Options选项卡下取消Open Terminal和Open SFTP这两项前面的对勾。在Services选项卡下勾选SOCKS/HTTP Proxy Forwarding下面的Enabled前面的选项。之后点左面的Save Profile As，随便取个名字存到一个随便的地方。之后点Login，在弹出的对话框里点Accept and Save，之后你会发现下面的Login按钮变成Logout了。这就说明你的ssh通道已经做好了。如果你是Linux用户，就比较方便在终端输入这行命令：sudo ssh -qTfnN -D 7070 username@yourhost7070是socket的端口号，默认7070就好，username是帐号，yourhost是密码。回车后输入你的管理员密码，再输入你ssh的密码，就做好通道了。下面你要做的就是给你的浏览器设置代理，IE的设置方法是在工具－Internet选项－连接－局域网设置下面，勾选“为LAN试用代理服务器（这些设置不用于拨号或VPN链接）(X)”，然后点击高级，在弹出的对话框里的套接字那栏输入“127.0.0.1”，后面的端口输入“1080”。点击确定。Linux用户设置Firefox代理比较方便，可以下载个AutoProxy插件，简单设置后就可以用了。现在看看YouTube是不是可以访问了。如果仍然不能访问，你可能遇到了DNS污染，解决方法是更改你的DNS服务器，到一个比较干净的DNS上，比如google的DNS：8.8.8.8和8.8.4.4。