拜texlive、ubuntu的开发人员和apt所赐，现在在Linux上使用LaTeX已经变得非常方便了。只需要敲击如下命令就可以安装上latex环境和中文支持了： $ sudo aptitude install texlive latex-cjk-chinese texlive-latex-extra 默认会安装arphic的几种中文字体。如果觉得不够漂亮，我这里有一些已经生成的 中文字体包（水木TeX版的某大侠制作，适合打印，应该是我06年从他发布的某个包里提取出来的 ~110MB；如果你喜欢自己生成字体，参考附录第二篇文章），可以直接解压到HOME目录使用，包括了7种常用的中文字体：仿宋 fs, 黑体 hei, 楷体 kai, 隶书 li, 宋体 song, 宋体粗体 songb, 幼圆 you。使用有问题请更新目录索引信息，运行如下命令： $ update-updmap 安装完后，测试是否可以正确输出UTF8中文文档： \documentclass{article} \usepackage{CJK} \begin{document} \begin{CJK*}{UT ...

蓄水池抽样是一个online sampling问题，还有更复杂的带权重的蓄水池抽样算法，可以参考：Weighted Random Sampling (2005; Efraimidis, Spirakis) 问题描述 问题：有个n行的文件，如何逐行读取并随机采样k行，使得它们是完全随机的。 其中：n很大且大小未知，只能流式读取一次one pass，k一般较小。 方法：所谓的蓄水池抽样还是很形象的，蓄水池就是这个k容量的池子，新来的第i号元素总是以k/i的概率替换掉池子里的元素，可以证明最后的k个元素是以等概率k/m留在池子里（当然，如果最终文件从头到全部读完，即m=n，则等概率为k/n）。 注意：问题的表述，必须是整个文件从头到尾n行都读完，才能保证蓄水池里的留下来的元素是等概率k/n。如果是完全没有头尾的流式数据，那么只能保证你读取过数据里是等概率的，比如读取了m行，那么就是等概率k/m。理解了这个样本总体的概念才能理解证明。 算法伪码 i = 0 reservoir[] for ( filestream >> x) i++ if i<=k ...

一致性问题 一致性(consensus)问题是指分布式系统中的节点如何就某些东西达成一致，可能是一个值，一系列动作，也可能是一个决定。通常有如下应用场景： 决定是否将一个事务提交到数据库 对当前时间的界定达成一致以实现同步化时钟 执行分布式算法的下一步 选择一个leader节点 一致性是一个重要的问题，实际上大多数的分布式系统都是构建在它之上：Group membership systems, fault-tolerant replicated state machines, data stores 这些典型的分布式系统都在某种程度上依赖于一致性问题的解决。同时该问题与另一个经典问题(atomic broadcast，即能在一个网络内将消息可靠的完全有序的传递给其他节点)本质上是同构的。 拜占廷将军问题 拜占廷将军问题(Byzantine Generals Problem)是Lamport对分布式计算一致性问题的一个描述。在分布式环境中，有可能出现疏漏型的错误，比如系统崩溃、消息丢失、消息重复等；也可能出现误导型的错误，比如消息篡改、状态错误等。所有这些错 ...

HA Cluster/Failover Cluster HA Cluster必须能够使用共享存储（NAS/SAN）， HA Cluster的几种配置，参考Pacemaker的配置： Active/Active 两台主机通过负载均衡同时提供相同服务。 Active/Passive 备机做完整的冗余备份，主机宕机时，备机替代主机上线。 N+1 提供一台备机，但这台备机能够cover所有的服务（一般适用提供多种独立服务的Cluster），当N=1时，退化成Active/Passive。 N+M 当N+1配置里的一台备机无法cover所有服务时，考虑增加备机到M。 N-to-1 备机只是临时使用，当主机恢复后，服务还是自动切换到主机。 N-to-N 这是Active/Active和N+M的组合模式。 DRBD DRBD (Distributed Replicated Block Device) 是一个用软件实现的，无共享的，服务器之间mirror块设备内容的存储复制解决方案（可以看做网络上的RAID-1）。 DRBD is a RAID-1 styl ...

部署一份Hadoop系统做一些探索，当然只是toy，不是生产环境。确认jdk的版本在1.5以上，推荐1.6。如果在redhat上，装完后可以可能还需要设置环境变量： export JAVA_HOME=/usr/java/jdk1.6.0_18 export PATH=$JAVA_HOME/bin:$PATH export CLASSPATH=.:$JAVA_HOME/lib/dt.jar:$JAVA_HOME/lib/tools.jar 使用一台机器作为namenode和jobtracker是为master，其他几台机器作为datanode和tasknode是为slaves 这里这样配置：机器Node1作为master，机器Node3和Node4作为slaves。 首先，为所有机器建立同一用户名，比如hadoop，为了部署方便，可以通过设置authorized_keys保证master和slaves之间ssh调用不需要输入密码。 然后，解压下载的apache-hadoop-r0.21.0.tar.gz包到主目录，为了维护方便，链接到 ~/hadoop， 为了升级后不影响配置 ...

介绍 一个软件项目的开发一般包括文档管理、代码管理、版本管理、进度管理、bug管理等，这方面的支持工具也很多。我觉得Trac是一个很优秀的代表，用它搭配SVN作为前端工作，差不多可以把这些任务都顺利解决了。Trac有如下一些特点： ticket Trac利用ticket的概念，把feature提交、task分配以及bug管理很完美的整合到了一起。 可以设置ticket的优先 ticket和roadmap结合，并且能够图形化显示项目进度 自定义条件生成bug报告 wiki wiki功能贯穿在整个工具里，可以很方便的组织说明文档。同时增加了许多bug管理的专用标记，能方便的创建到ticket、代码行甚至修改历史的链接。 subversion Trac可以作为subversion的前端，和svn搭配得很好。比如可以在timeline中看到所有的提交记录，可以在source view里方便的对比历史版本，并且具备语法高亮。 部署 Trac是基于python的，安装它之前需要python、apache、subversion、openssh、sqlite、swig等一坨软 ...

multiprocessing 可以通过派生multiprocessing.Process来构造一个子进程： class MyProcess(multiprocessing.Process): def __init__(self, name): super(MyProcess, self).__init__(name=name) def run(self): // 进程实际的逻辑 print 'Worker: %d. pid: %d' % (num, os.getpid()) 再通过p.start()来启动子进程，然后通过p.join()方法来使得子进程运行结束后再执行父进程。 jobs = [MyProcess(str(i)) for i in range(5)] for p in jobs: p.start() for p in jobs: p.join() multiprocessing.Pool Pool对Process做了进一步封装，它默认按照CPU的数量创建子进程。 p = ...

终端提示符 bash if [ "$(/usr/bin/id -u)" != "0" ]; then export PS1='[\[\033[01;31m\]\u\[\033[00m\]@\[\033[01;32m\]\h\[\033[00m\]:\[\033[01;34m\]\w\[\033[00m\]]$ ' else export PS1='[\[\033[01;32m\]\h\[\033[00m\]:\[\033[01;34m\]\w\[\033[00m\]]# ' fi csh set colordefault = "%{\e[0m%}" set colorblack = "%{\e[30m%}" set colorred = "%{\e[31m%}" set colorgreen = "%{\e[32m%}" set colorblue = "%{\e[34m%}" set prompt="[$colorred%n$colorblack@$colorgreen%m$colorblue %c$colordefault]%% " ...

精确的字符串匹配算法有 单模匹配算法，比如，KMP、BM算法等；和 多模匹配算法，比如，Wu-Manber、AC算法等。 AC算法(Aho-Corasick)是KMP算法向多模式串情形的扩展，该算法使用一种特殊的自动机，即AC自动机。AC自动机由一组模式串P生成，是trie的扩展。 先回顾一下KMP算法。 每读入一个字符，KMP算法更新 既是模式串的前缀、同时也是已读入文本的后缀 的最长字符串的长度。设字符串vβ是下一个 既是模式串p的前缀、同时也是已读入文本t1…ti+1的后缀 的最长字符串。可以看出：对模式串当前已匹配前缀u来说，v既是u的一个后缀、也是u的一个前缀，并且字符β一定与ti+1（即σ）相等。这里，称v是u的一个边界。 KMP算法： 首先，预处理得到模式串p的每个前缀u的最长边界b(u)=max(v)，即得到所谓的next数组。 然后，设当前文本位置为i，对新读入的字符σ=ti+1，按照如下步骤计算新的最长前缀： 如果σ=p|u|+1=α，那么新的最长前缀是up|u|+1，计算结束； 如果σ≠α，设置u为最长边界b(u)，跳转到步骤1；如果u ...

Trie(Retrieval Tree)又称前缀树，可以用来保存多个字符串，并且非常便于查找。在trie中查找一个字符串的时间只取决于组成该串的字符数，与树的节点数无关。因此，它的查找速度通常比二叉搜索树更快。trie的结构很简单，每条边表示一个字符，从根节点到叶节点就可以表示一个完整的字符串。所以，如果用trie表示一组英文单词，就是一颗26叉数；表示一组自然数，就是一颗10叉树。直观上，实现trie很简单，比如实现英文单词的trie，使用如下的节点构造树： struct node { char chr; struct node *edges[26]; }; 这样做虽然简单，但没有很好的利用内存，edges数组肯定很多都是闲置的，如果使用到更多字符的话，这种浪费会更严重。这里介绍一种基于数组结构的trie实现方式，不仅节省内存，而且查询速度更快。基于数组查表的时间复杂度为O(|P|)，基于平衡树的时间复杂度为O(|P|log|Σ|)，其中，P表示查询的字符串长度，Σ表示字符集合。 基于数组的实现方式，把trie看作一个DFA，树的每个节点对应一个DFA状态，每 ...