完美迷宫生成算法

Perfect maze

Perfect maze又称standard maze,指没有回路,没有不可达区域的迷宫。用图论的语言来说,就是可以用spanning tree表示的迷宫,保证迷宫中任意两个格子间都有唯一的路径。本文旨在探讨如何随机生成棋盘状perfect maze。迷宫格子的邻居的定义采用von Neumann neighborhood,即水平竖直方向相邻的四个格子。

变形Kruskal算法

说得通俗点,就是“随机拆墙”。

Read More

自然语言处理之词语抽取

多日之前看到了Matrix67的《互联网时代的社会语言学:基于SNS的文本数据挖掘》,文中提到的方法是无监管的,而且无需词典就能提取词语,要素概括起来有两点:词的凝聚力,以及左右邻字的信息熵。今天把这个方法实现了一下。

对于凝聚力,我的理解是可以用词前后两部分的pointwise mutual information来描述,比如对于“博物馆”一词,考虑“博”与“物馆”之间,以及“博物”与“馆”之间的pointwise mutual information,两者取较小值作为“博物馆”这个词的凝聚力。

Read More

Force-directed算法(1)——Fruchterman-Reingold

简介

Graph drawing即根据顶点和边的拓扑关系,将这张图展现出来。很明显,表现的形式种类是非常多的,如果精确到每个顶点的座标,那么方案有无穷多种。Graph drawing 目标是画出一张美观的图的布局来。美是个见仁见智的概念,何谓美?“每个本质在于旺盛的生命力,美的形象能够感染人的情感和鼓舞人心”,展现出来的图是否美每个人的看法可能都不一样,但有一些通用的要素是大家一般共同认可的,比如边的两端不能靠得太近也不能离得太远,相交边的数目要尽量少,有对称性等等。

Read More

并行N-body模拟

缘由

和专业有关系的第一门有趣的课结束了,觉得有必要记录些什么。这篇文章就用来纪念我觉得最有意义的一次作业。

要求

需要分别编写MPI、Pthreads、OpenMP的并行实作。

层次

我不愿意把代码重复三份,分别为三种并行库编写程式,所以就用 autotools 管理项目,用不同的选项来启用不同的功能。这样做的另一个好处是很容易支持MPI+Pthreads或者MPI+OpenMP甚至是MPI+Pthreads+OpenMP,尽管这样混用不会带来性能上的提升。

Read More

SVT13117ECS上Gentoo安装记(含内核配置)

购买

我需要一台散热小一点的笔记本,i5 ivy bridge,4G RAM,13.3/14 英寸,madper 推荐了款 HP 的 ultrabook,那东西卖得很畅销,早已没了,我就选了这个 SVT13117ECS。回家后第二次用附带的 Windows,也是最后一次使用,把硬盘驱动等信息截图用 nc 传给了我的 Gentoo 台式机。还是要吐槽一下 OEM Windows 7,500G 的硬盘只设置了三个分区,两个是还原什么的作用,隐藏的,留下一个400多GB的C盘。假使我使用 Windows 也免不了要重装呢。

Intel(R) Core(TM) i5-3317U CPU @ 1.70GHz MemTotal: 3952624 kB

Read More

8门编程语言的设计思考

今天参加了SHLUG的月度技术分享会,见到了三个同学的同学(呃~精确描述的话可能得写成这样:其中一个是同学A的同学,两个是同学B的同学)。

我就不同编程编程语言的设计思考为主题做了一个分享。之前在学校里做过类似的分享,这次把它搬到SHLUG上来了,对之前的幻灯片又修修补补,增添了一些内容(把之前Prolog、OCaml纸上谈兵的部分加了些代码,丰富了内容……当前,也可以把整张幻灯片看作纸上谈兵)。

之前“80分钟8语言”这个标题感觉有些误导人,毕竟读者的第一反应很可能是认为这是在介绍语法,第二反应是80分钟甚至无法把一门语言的语法给讲清楚,如何能把八门语言交代清楚。而且之前在学校分享时和另一位同学肖骐一共讲了两个半小时的样子,远远超出了80分钟。题目的用语想了一会儿,决定改为设计思考(design thinking)。

Read More

80分钟8语言

今天要做一个关于不同编程语言的演讲,我介绍了Scheme, Smalltalk, Lua, Perl, Ruby, Prolog, Erlang, OCaml, Haskell,其中Perl是作为反例出现的。这些语言大多是这一年用零碎时间学的,像Lua、Prolog、Erlang、OCaml都只是看完了一两本入门的书,对它们的特点、优点短处、擅长领域有了个比较粗浅的认识;Scheme、Smalltalk则是一本书都没看完,理解就更为肤浅了;Haskell虽然看过两本入门教材,也翻看过不少文章,但它博大精深,广博之处只能窥见一二,精妙之处也无法领会太多,但还是列出了一些我所知道的。

Read More

Evil--在Emacs中模拟Vim

这篇文章过时了,参见皈依Emacs,现在我对操作方式有较大调整。

Vim模拟

平心而论,Vim的modal editing确实比Emacs强,而Emacs默认的按键绑定设计不好,不适合使用,要让它适合做工作环境往往要改大量按键。“一千个读者心中有一千个哈姆雷特”,Emacs的配置也确实大相径庭。

Read More