发表于
2013-11-20 00:00:00
拓扑排序
发表于
2013-10-05 00:00:00
Do Presentation like a Geek
很多程序员不喜欢做PPT之类的东西，我也不喜欢。这有另外的原因是一直没找到一个合适的工具，Linux下PPT是个悲剧，Latex学习成本又大了点。
上次在公司分享的时候偶然找到了这个叫做showoff的工具，熟悉了大概半个小时就上手了，迅速把自己的PPT完成。showoff是Ruby写的一个适合程序员写PPT的工具，你可以用类似Markdown的语法编辑文本文件，同时在terminal下开一个服务，浏览器访问localhost:9090可以预览的成果。这个过程非常类似用Jekyll来写博客。当然最后可以导出成PDF格式的，或者直接在浏览器上展示。安装Showoff安装非常简单:$gem install showoff$git clone(ppt-repo)$cd(ppt-repo)$showoff serve使用我觉得showoff一些特别好的特点是:纯文本编辑 (对程序员有吸引力)嵌入代码方便，高亮代码嵌入图片方便可执行内嵌Javascript，Coffeescript 或者Ruby代码，并显示结果。(对程序员来说很不错)一些显示特效赶快看看example目录吧，你就能上手了。
...继续阅读
(15)
发表于
2013-10-02 00:00:00
Testing Prose-io
发表于
2013-09-26 00:00:00
初到美国
发表于
2013-08-24 00:00:00
Metaprogramming Ruby
发表于
2013-07-14 00:00:00
Learning Ruby with Ruby Warrior
Ruby上总有好玩的东西，偶然看到这个RubyWarrior，玩了一把感觉还有些意思。这个有些像我原来介绍的RubyRobot,
不过更像之前的Wumpus，看来我对这种游戏有些兴趣。Ruby新手边玩边熟悉了语言。需要代码的可以clone下来看看，如果只是玩可以gem装上，然后运行rubywarrior就开始练级了。gem install rubywarrior我现在只是完成了初学者模式，这里的AI还比较简单，主要实现一个函数就行了。分为两种模式，第一种只用对付当前的场景，第二种为epic(史诗?)模式，要从1~9连续闯关。我的平均成绩是C，所有级的代码放在Github上了。Level Score: 27
Time Bonus: 18
Level Grade: F
Total Score: 374 + 45 = 419
Your average grade for this tower is: C
Level 1: S
Level 2: C
Level 3: B
Level 4: B
Level 5: D
Level 6: F
Level 7: B
Level 8: F
Level 9: F中级模式是二维的地图，所以更有挑战。这里有一个前端，不过我还没用过。这还有人用神经网络的方法来做的，可以学习一下，:)。
...继续阅读
(14)
发表于
2013-07-06 00:00:00
初学Rails
我在2012年左右开始关注Ruby，平时有的时候会用Ruby写一些脚本。这是一个很活跃的社区，Ruby火起来也不是最近的事。可贵的这里总是有一些新的东西出来，比如我现在的这个博客是基于jekyll和Github的。
Ruby的迅速崛起更多的还是因为Rails，所以学习Rails也是了解Ruby的一个好方法。最近为公司内部所配置的GitLab是Rails开发的。另外我自己也在公司做一些Web程序，其实是很简单的东西，就是把每天晚上跑的程序各种测试结果展示出来(nightly/weekly/coverage等等)。我选用Rails来开发，果然一个最初的版本很快就做出来了。在初学Rails的过程中让我体会到了一些web开发的乐趣。Rails适合小团队的快速开发，其中的一些理念是：Encourage Agility --鼓励敏捷开发Convention Over Configuration --约定高于配置DRY --不要重复自己Less Code --更短小的代码正是这些开发原则使得Rails开发如此简单明了(当然前提是你按照Rails约定的方式来)。
我原来做过一些web开发服务器方面的工作，在那种模式下开发需要每个人各司其责。
但是Rails不同，在ActiveReco
...继续阅读
(18)
发表于
2013-05-18 00:00:00
高效的Crit-bit Tree
发表于
2013-05-09 00:00:00
迁移到Git
公司这群人终于打算从CVS迁徙到Git上了，CVS这套公司用了六年。CVS这是90年代的东西，我们不能因为年代久远而嫌弃这，只是CVS这东西对于一个比较大的项目来说创建分支是相当漫长，大多数程序员都没有耐心的。
迁徙计划虽然纸上谈兵了很长时间，直到现在才终于打算行动。上午把Git在服务器上搭建好，主要卡在一个Git的命令上，因为一些权限问题。git init --bare --shared=group;--shared=group forget thisGit的web接口是用的是ViewGit，自己做了一些修改，加上GeShi来高亮代码，并使用了GitStats来做代码统计。GitStats统计的项目非常多，看起来很直观。稍微记录一下常用的一些git命令。这里有一个最直观的Git学习的地方leanGitBranch。检出仓库git clone repo更新git pull提交到远程git push提交到本地git commit -am"log message"创建branchgit branch branch_name切换branchgit checkout branch_name合并branchgit merge branch_name图形界面gitk解决冲突git mergetool撤销上一次commitgit revert HEAD撤销上上次commitgit revert
...继续阅读
(36)
发表于
2013-04-17 00:00:00
一些包管理命令
包管理器是Linux上一个经常用的东西，我觉得下面这几个命令是非常有用的，便于查询包的状态，或者搜索我该安装哪些包。apt-cache用来根据名字查询软件包，比如apt-cache search vim查询vim相关的。apt-file用来根据某个文件查询软件包，这在编译程序的时候非常有用，可以通过所需要的头文件去查询要安装的东西，可以避免去Google了。注意使用之前需要安装并update。sudo apt-get install apt-file
sudo apt-file update比如我在编译某个软件的时候找不到readline.h>，使用下面的命令来查询一下：sudo apt-file readline.h结果中有这么一行，那么我就知道继续安装libreadline5-dev库就行了。dpkgapt是基于dpkg开发的，dpkg是更古老更底层的一套工具，Debian系统管理器的基础。dpkg -l 列出所有已经安装的包
dpkg -s vim 列出包vim的状态
dpkg -L vim 列出本地所有vim相关联系的文件
dpkg -S vim 搜索所属包的内容brewMac下推荐Brew来替代apt，大部分的开源包都有对应的地址源了。我没使用过MacPorts，无法比较这两套的差别。
不过我个人很喜欢的一点是brew所有安装的东西都在brew -prefix/Cella
...继续阅读
(28)
发表于
2013-04-11 00:00:00
巧妙的XOR Link List
XOR Link List, 只用一个附加的变量来实现双向链表。首先xor本身是个稍微有点难理解的操作。xor有下面的一些特性:A ^ 0 = AA ^ A = 0A ^ B = B ^ A(A ^ B) ^ A = B(B ^ A) ^ B = A注意最后两条，这是XOR Link List的关键，这也是通过xor操作来实现swap的关键。voidxorSwap(int*x,int*y){if(x!=y){*x^=*y;*y^=*x;*x^=*y;}}这里注意需要判断x!=y，否则如果传入的是相同的指针，最后所指向的变量被设置为0了。通过最后两条联想到双向链表中的两个指针的实现，一般如下图所示：...ABCDE...–>next–>next–>next–><–prev<–prev<–prev<–如果把next和prev用一个变量替换还能实现前向和后向遍历，那就节省了一个变量的空间。...ABCDE...<–>A⊕C<->B⊕D<->C⊕E<->比如当前在B节点，其pointer变量为A⊕C，如果前面的A地址保存下来然后做运算(A⊕C)⊕A -> C，这样就得到下一个节点指针，反向遍历同样如此。当然其缺点是逻辑复杂了，删除其中的某一个节点也不方便(删除头和尾要好点)，遍历的时候需要保存上一个节点。这样看来为了省一点点空间这样实现似乎有点不值，在大部分情况下这样的一个pointer的
...继续阅读
(19)
发表于
2013-03-03 00:00:00
Jekyll使用MathJax来显示数学式
使用Jekyll写作文章的时候有可能需要内嵌一些数学公式,MathJax就是用来干这个的，试用了一下感觉非常方便。步骤如下:修改html头部。在每个页面开头加上这么一句，在Jekyll下可以通过修改default.html加上。script>本地安装kramdown。因为rdiscount和默认的markdown在解析带公式文件的时候都会出现一些问题，所以最简单办法还是安装kramdown。
` $ gem install kramdown`修改_config.yml，把markdown选项修改为:markdown: kramdown然后在发布的时候就可以使用$$来把需要显示的数学式子扩起来。像这样：$$a^2 + b^2 = c^2$$发布出来就是漂亮的公式了。一些更酷的例子：不过我可能永远用不到这么复杂的表达式 :).另外今天找了一个markdown-mode.el，在Emacs下编辑Markdown文件又方便了不少。
Mac下的Markdown编辑器Mou也是非常不错的。
...继续阅读
(14)
发表于
2013-02-15 00:00:00
读bootstrap scheme
发表于
2013-01-27 00:00:00
Emacs会说话
出来工作之前我从来没认真考虑过我的英语口语问题，大学时候的四级口语考试C级也没让我意识到自己的发音比较烂。学了好多年哑巴英语，又因为本人生性有点害羞经常不好意思开口说英语，悲剧早就注定。其实我的英语阅读能力还是可以的，不过工作之后同事们都嘲笑我口语听起来像印度人，据说发音极其古怪。在Mac下有一个叫做say的命令行程序，我有时候会用来听单词单词发音。这个程序加上-f参数也可以用来朗读整个文件。say hello wrold
say -f demo.txt前几天突然觉得如果写个Emacs Minor Mode，能在边写单词的时候Emacs就把你写的朗读一遍就好了，Emacs号称能煮咖啡，这点小事当然不在话下。其实除了在公司我也很少写英文，不过这个想法看起来比较好玩，于是动手做了一下。预想的基本功能是实现了，我把它叫做EmacSay-mode，意为在Emacs+Mac+Say下实现的，所以这东西可能不能在Linux下运行。这也是我第一次学着写一个minor mode，实现起来也很简单。整个不到100行elisp代码。基本思路就是如果当前输入的字符是空白(或者其他非字母字符)，寻找前面一个字符串，格式化成一个命令行，用start-process或者shell-command来调用。
注意start-process会fork出来一个子进程来执行命令，在书写过程中最好还是使用start-p
...继续阅读
(28)
发表于
2013-01-22 00:00:00
迟到的POJ 500
我发现自己有了很重的拖延症，一个表现就是在2011年3月定下的目标POJ 500最近才完成。这一页500道题耗费了我很多时间和精力，同样也带给了我很多知识和乐趣。当然工作后毕竟还是没有学校的时间充足了，现在还花时间来做题似乎显得很悠闲，这500题最后十个是在元旦的几天假期里完成的。我是从2010年的4月份开始在Poj上做题，那天偶然发现自己原来2006年还注册过账号，于是做了两题试试，没想到后面就竟然沉迷其中，一直到自己从学校毕业出来。这两年强度还不算大，平时还是要在实验室做做项目的。我没参加过专业队的训练，不过参加过一次学校的比赛，和王骆驼两个人一个下午做出来五道，比较悲剧的是差一道没进决赛。不过当时还是挺欣慰的，毕竟自己还是不算专业选手啊。这一年多静下心来写程序收获很多，因为体会到了写程序的乐趣，有时候在睡觉的时候脑袋也在不知不觉地想问题。有时候我选择按不同的数据结构或者算法思想来选题做，有时候就在线上泡着看排我前面的人在做什么，然后自己也跟着做，这真写的是寂寞啊。不过现在回想起来这一两年算是最自由、最充实的写程序的日子了。像ACM题这些东西最好还是大学开始接触，在开始学习基本算法和数据结构的时候就开始进行训练是最好的。当然如果大学能进专业队训练就更不错了，如果只是业余拿来练练手也是大有裨益的。也许我们做不到专业队哪些人写代码就像秀肌肉一样，体会到其中的乐趣就够了。在我开始做P
...继续阅读
(18)
发表于
2013-01-04 00:00:00
获取挂掉程序的栈信息
在程序挂掉的时候最好还是留点有用的遗言，特别是对于一些比较难重现的Bug，也许这些信息会成为解决问题的关键。下面这个技巧可以让程挂掉的时候打印出来栈信息。这个办法来自这里, 我觉得把SIGABRT、SIGBUS信号加进去也挺好的，在此做了点修改。曾经尝也试过glibc的backtrace函数，，但是给的信息不全(没有行号)，对此做得最好的还是gdb。 在终端可以用gdb获取某个进程的当前栈：$ gdb -p 5595 -batch -ex bt
0xb7fb4410 in __kernel_vsyscall ()
#0 0xb7fb4410 in __kernel_vsyscall ()
#1 0xb7dc2d50 in nanosleep () from /lib/tls/i686/cmov/libc.so.6
#2 0xb7dc2b87 in sleep () from /lib/tls/i686/cmov/libc.so.6
#3 0x0804874f in main () at print_stack.cc:64那么一个好的办法就是在程序开始的时候设置好信号，绑定SIGSEGV和SIGABRT到DumpBackTrace()函数，DumpBackTrace函数fork出来一个新进程，运行上面的命令来获取调用栈。#include#include#include#inc
...继续阅读
(24)
发表于
2012-12-26 00:00:00
Browser objs and class hierarchy in Ruby
发表于
2012-12-16 00:00:00
Clang is Making Emacs Smarter
在Emacs下自动补全总是个问题，对于同一个buffer内的基于symbol补全auto-complete-mode做得非常好了，但是因为没有进行代码的分析，所以像结构体的成员变量或者类的成员函数的补全是不可能的。当然你可能试过这个号称最智能的GCCSence,但是我觉得这个东西够复杂的，在使用之前还需要用户手动运行一个命令来用Gcc处理一遍，它还会把一些东西放在sqlite数据库里面。这大概是因为Gcc不编译做静态分析工具造成的，在这里、这里、这里有讨论，Google的一个静态分析的项目从Gcc迁移到LLVM，重点是这:The gcc version has been difficult to support and maintain, due mainly to the fact that the GIMPLE intermediate language was never designed for static analysis. The abstract syntax tree provided by Clang is an easier data structure to work with for front-end analyses of this kind.这个thread挺好玩的，后面变成了一大群人争论functional programming和Imperati
...继续阅读
(30)
发表于
2012-12-13 00:00:00
Have a try on Ninja
发表于
2012-11-22 00:00:00
Ruby Robot AI
发表于
2012-11-14 00:00:00
Ruby\'s Block and Proc
Callable objects在Ruby当中一切都是对象，但是有一个例外，那就是block。Block和Proc类似，但是还是有稍有差别的，Block更常用一些。最近在看《Metaprogramming Ruby》，在这节中有个例子是这样的。require 'highline'
hl = HighLine.new
friends = hl.ask("Friends?" , lambda {|s| s.split(',' ) })
puts "You're friends with: #{friends.inspect}"
⇒
Friends?
Bill,Mirella,Luca
You're friends with: ["Bill", "Mirella", "Luca"]这里看起来hl.ask把Proc当作参数来传递，而不是接受了一个block，接受Block是另外一种使用模式：require 'highline'
hl = HighLine.new
new_pass = hl.ask("password: ") { |prompt| prompt.echo = false }在highline代码可以看到相应的处理方式，第一种方式lambda构造成的Proc其实传递给了answer_type，而yield来处理block。def initialize( question, a
...继续阅读
(15)
发表于
2012-11-08 00:00:00
丽江印象
发表于
2012-11-05 00:00:00
Emacs iedit/occur 插件
发表于
2012-10-29 00:00:00
调优的小工具RunLim
在公司有同事用这个小程序RunLim来调试程序的内存问题。刚开始以为是我们上海的一个同事写的，就弄来看了看。后来发现是公司一个早期同事Armin Biere写的，还开源了，debian的源里有这个东西。我在公司维护的一部分代码是这个人写的，据说厉害的程序员，他现在在学术圈里。用这个小程序来测试程序跑的时间和内存，用法很简单:./runlim prog.exe
比如：
kang@ubuntu:~/download/runlim-1.7$ ./runlim sleep 1
[runlim] version: 1.7
[runlim] time limit: 311040000 seconds
[runlim] real time limit: 311040000 seconds
[runlim] space limit: 4294966090 MB
[runlim] argv[0]: sleep
[runlim] argv[1]: 1
[runlim] start: Tue Oct 30 00:02:52 2012
[runlim] main pid: 22546
[runlim] end: Tue Oct 30 00:02:53 2012
[runlim] status: ok
[runlim] result: 0
[runlim] children:
...继续阅读
(14)
发表于
2012-10-16 00:00:00
Ruby vs C++ for delegation
下班之前同事BigBird给我show他的一段C++代码，对于我等拿C++当作C来用的未入门者实看起来实在是炫丽。虽然比较冗长晦涩，不过还是能看懂个大概，然后觉得这对于动态语言是非常容易实现的。 于是晚上回来用Ruby来搞搞，弄出下面这么段代码。C++版本在这里https://gist.github.com/3900077。
可见动态语言和编译型语言实现起来效率还是好太多了，同时代码也好理解。
再次我讨厌C++类型推导，^_^。Ruby实现这个方式很多，另外Ruby的库包含SimpleDelegator的，将调用的方法直接传递到其他对象。#!/usr/bin/ruby
class Delegate
attr_reader :proc_list
def initialize()
@proc_list = []
end
def add(*proc)
proc_list.push(proc)
end
def eval(obj)
for e in proc_list:
if obj.respond_to?(e[0])
if e.size == 1
obj.__send__(e[0])
else
obj.__send__(e[0],
...继续阅读
(17)
发表于
2012-09-27 00:00:00
UbiGraph动态显示Python函数调用
发表于
2012-09-18 00:00:00
A*算法解决kth-shortest路径问题(2)
我之前写过一篇图文并茂的文章来介绍这个算法，有好几次有朋友反馈说对自己有帮助，深感荣幸。这次再次写这个也是因为帮忙于一个朋友解决这类问题，这里再成一篇，稍显罗嗦。问题描述无向图G，需要求出S->T点的前k短路径，要求路径中没有环。(所有的边的权值不为负)A*算法求解kth-shortest问题A*算法已经被广泛运用于路径规划问题中，同时A*算法作为一种启发式算法的框架，可用于多种搜索问题，还是先回顾一下A*的基本符号：f(s)=g(s)+h(s)，其中h(s)<=h*(s)，h*(s)是某点到终点的真实代价，h(s)是估计代价，并且对s的任意后继t有：h(t)+w(s,t)>=h(s)，其中w(s,t)是从s转移到t的代价，符合这条件的评估函数f(s)可以得到正确的最短路径。而这里评估函数f(s)是A*算法的关键，其效率都取决于此,退化的A*算法就是宽度搜索(即启发函数h(s)为常数)。另外A*算法的最优性证明在这篇论文里有阐述。所以如果能确切的计算出来h*(s)，那么评估函数f(s)将是s点的最短路径，这可算是一个最优的启发函数。可以利用Dijkstra算法来求解出各个点到T点的最短路径，假设第i个节点到T的最短路径计为Dist_T(i)，Dist_T(i)作为A*函数中的启发函数h(s)，从S开始搜索，因此算法描述如下：intAstar(){if(dist[S]==INF)re
...继续阅读
(29)
发表于
2012-09-13 00:00:00
换域名了cyukang.com
昨天晚上突然发现自己的域名moorekang.com不能用了，上午问了一下域名提供商Bloghost，原来因为双方沟通上的问题导致我的域名没及时续费，甚至进入了赎回期，在这个时候只有这么几种选择：换一个域名赎回自己原来的域名，价格不太便宜，国际域名和国内域名也有差别，我的需要150美金等域名过了赎回期再重新购买，期间需要等待40来天左右所以，血的教训啊，及早续费自己的域名，免得面临这么一个窘境。无奈，我选择了换域名，虽然原来那个稍显长的域名已经用了近两年多。稍微找了一下，觉得这个域名cyukang.com还比较短，于是就申请了下来。国际域名不用各种备案，所以几分钟就下来了。另外对于Jekyll和GitPage这样的组合，换域名是多么的简单，几分钟就搞定了，所以这次折腾也没花多少时间。另外我觉得twitter这个主题已经够简洁了，今天稍微做了一下改动，用我仅有的一点css知识让顶部的导航栏固定下来。有我链接的麻烦换一下，呃，其实也没几个人用我做友链:)，不过还是得喊一声的。–
...继续阅读
(16)
发表于
2012-08-19 00:00:00
OS dev的Bochs调试
最近在弄一个自己的hobby OS，作为菜鸟在调试时候积累一些经验，记录一下。Bochs调试Bochs自带调试功能，但是如果你是apt装上的是不行的，下源码来自己编译，编译选项为：./configure --enable-debugger --enable-disasm这个我只是尝试过，在OS的loader阶段可能会用到，当如果进入C语言实现部分的代码如何调试?我希望看到C的源码级别调试，而不是汇编的。Bochs + gdb调试同样需要在编译的时候加上选项，这个选项必须注意，否则在gdb调试的时候会出现”Cannot find bounds of current function”之类的问题。./configure --enable-debugger --enable-disasm --enable-gdb-stub诡异的是这个–enable-gdb-stub选项和上面的 –enable-debugger选项只能二选一。也行，编译出来后重命名吧。编译完成后在Bochs的配置文件.bashrc中加上这么一行:gdbstub: enabled=1, port=1234, text_base=0, data_base=0, bss_base=0另外注意kernel的代码也需要加入-g编译选项。最后在编译完成后的文件是带调试信息的，但是我们在用Bochs启动的img文件不需要这些，现在比如
...继续阅读
(26)
发表于
2012-08-09 00:00:00
Linux下快捷切换屏幕
