[Linux]Squid--便捷的Proxy Server

unbuntu下安装squid

sudo apt-get install squid

接着对/etc/squid/squid.conf作如下修改

http_port 8888   #设定proxy的端口为8888
acl homenet src 98.219.0.0/16     #把访问proxy的机器的网段设为homenet
http_access allow homenet         #所有从homenet定义的网段的访问许可设为允许

[数学]停车问题

Mathproblem上看来的问题. 一条街长度为4,最初这条街是空的.大家都开着长度为1的车子来来往往,寻寻觅觅.一旦发现街上有足够大的长度空着, 就会把车停下来.糟糕的是大家停车的时候在所有可能的泊车位随机的挑选,丝毫不会去为后面的人考虑.那么这条街,平均能停几辆车.

Sol:假设f(x)是在一条长度为x的空街上平均能停的汽车数目,当x>1的时候

f(x) = 1+\frac{\int_0^{x-1}[f(t)+f(x-1-t)]dt}{x-1} = 1 + \frac{2}{x-1}\int_0^{x-1}f(t)dt

不难得知

• 0<x<1: f(t)=0
• 1<x<2: f(t)=1
• 2<x<3:
  

  f(t)=1+2\frac{\int_0^{t-1}f(u)du}{(t-1)} = 1+\frac{2(t-2}{t-1}
  

所以

f(4)=1+\frac{2}{3}[\int_0^{1}f(t)dt + \int_1^{2}f(t)dt + \int_2^{3}f(t)dt] = \frac{11}{3} - \frac{4}{3}ln 2

[Emacs]一个locale引起的emacs中文输入问题

突然发现我的emacs-snapshot 23里无法呼叫出ibus中文输入法了.网上查了一下,说是LC_CTYPE环境变量应该设置为zh_CN.UTF-8. 于是在/etc/environment中修改完毕,结果还是没有效果.回想起升级到ubuntu9.10后, 总是碰到"locale: Cannot set LC_CTYPE to default locale: No such file or directory"这个错误信息.于是用locale -a 查看了一下系统支持的locale,不知道为什么没有zh_CN.UTF-8, 于是就用sudo locale-gen zh_CN.UTF-8 一下,再用locale -a查看zh_CN.UTF-8已经赫然在列了,那个错误信息也不再出现了.同时emacs 23里面也恢复了输入中文的功能.

[Python]抓取豆瓣电台里被标记喜欢的歌曲名称

一段时间前开始使用豆瓣电台,很喜欢一个功能就是听到一个好听的歌就可以标记上.以后就可以从我的音乐里看到按标记时间排列出的所有曾经标记过的歌曲.但是有个功能豆瓣电台还不支持,就是按照专辑来对所有标记的歌曲分类.因为我想看一下哪一张专辑我标记的喜欢的歌曲最多. 所以就用python写了下面的脚本. 使用的时候不要忘记把下面源码里 current_url里面的apc字串换成你的用户名, 并且登录豆瓣.

#!/usr/bin/python
from urlparse import urlparse, urljoin
import urllib, sgmllib
from HTMLParser import HTMLParser
import re, sys

class MyParser(HTMLParser):
    def __init__(self):
        HTMLParser.__init__(self)
        self.num = 0
        self.albums = {}
        
    def parse(self, url):
        req = urllib.urlopen(url)
        self.state       = 0
        self.raw_text = req.read()
        self.feed(self.raw_text)
        
    def handle_starttag(self, tag, attrs):
        #print "Encountered the beginning of a %s tag" % tag
        try:
            if self.state == 0:
                if  tag == "table" and dict(attrs)["class"] =="olts":
                    self.state = 1
                    self.row = 0

            elif self.state == 1:
                if  tag == "tr":
                    self.row += 1
                    self.state = 2

            elif self.state == 2:
                if  tag == "td":
                    self.state = 3

            elif self.state == 3:
                if tag == "a":
                    self.state = 4
                else:
                    self.state = 1

            elif self.state == 4:
                self.state = 1
        except KeyError:
            pass

    def handle_endtag(self, tag):
        #print "Encountered the end of a %s tag" % tag
        if self.state >= 1 and tag == "table":
            self.state = 0

    def handle_data(self, data):
        if self.state == 3:
            if self.row > 1:
                print "%d title"%(self.num), data[:-2],
                self.num += 1
                self.title = data[:-2]
        elif self.state == 4:
            if data.strip():
                print "album", data
                try:
                    self.albums[data].append(self.title)
                except KeyError:
                    self.albums[data] =  [self.title]
            
        
numsongs   = int(raw_input("How many songs do you have?"))
myparser    = MyParser()
base = 0
while base < numsongs: 
    current_url = "http://www.douban.com/people/apc/songs?start=%d"%(base)
    print current_url
    myparser.parse(current_url)
    base += 20
print "done, all together %d songs"%(myparser.num)
al = myparser.albums.keys()[:]
al.sort(cmp= lambda x,y: len(myparser.albums[x]) - len(myparser.albums[y]))
for a  in al:
    print a, "%d songs"%(len(myparser.albums[a]))

我输出的结果是这两张专辑我标记的最多:
Schindler's List 6 songs
Le Fabuleux destin d'Amélie Poulain 9 songs
辛德勒的名单的OST以及天使爱美丽的OST. 我果然是个电影控.

无比强大的绘图脚本Asymptote

未完
写paper就免不了要绘制一些示意图,而且又需要是矢量图.其中的一些简单的也就用ppt之类的对付了.还有一些对于位置或者每个部分的尺寸精度要求比较高,更适合用脚本来生成.曾经用过一段时间metapost.但是它古怪的语法最后还是让我放弃了.之后便一直忍受着Visio或者用tgif这样的古董.直到我发现了Asymptote.这是一个用于绘制矢量图的脚本语言.其语法一方面继承了很多metapost的优秀的部分,另一方面又加入了一些类似于Python等现代脚本语言的特性.所以上手起来很快.最让我惊奇的是asymptote这样一个用于制图的语言还支持面向对象,high order function以及匿名函数这样的功能.不得不赞叹:asymptote 麻雀虽小五脏俱全.

这里有一个Gallery(link),大家可以看看这个语言的强大.

基本用法是

$asy inputfilename

inputfilename是你的asy输入源文件名称.如果它是helloworld.asy,那么asy就把这个源文件编译,输出为helloworld.eps.可以用-o选项指定输出文件名.

这里是我总结的Asymptote中最常用的命令和语法
在指定位置绘制一个点:

• 在(0,0)这个坐标处绘制一个点
  
  

  dot((0,0));

• 在(0,0)这个坐标处绘制一个蓝色的点
  
  

  dot((0,0), blue);

给定两个点,绘制直线:

• 直线
  
  

  draw((0,0)--(2,1));

• 带Arrow的直线
  
  
  

  draw((0,0)--(50,0),BeginArrow);
  draw((0,-10)--(50,-10),MidArrow);
  draw((0,-20)--(50,-20),EndArrow);
  draw((0,-30)--(50,-30),Arrows);

  这里设置arrow的参数可以为None(没有箭头,默认), Blank (不但不画箭头,线都不画), BeginArrow(箭头在起始端), MidArrow(箭头在正中间), EndArrow(箭头在末端,也简写成Arrow), 以及Arrows(两端都有)
• 带Bar的直线
  
  

  draw((0,0)--(2,1),Bar);

  这里的参数还可以是None, BeginBar, EndBar (或者等价的简写为Bar), Bars(两端都是Bar)

在制定位置写文本:

• 可以与LaTeX配合,写数学公式:
  
  
  

  unitsize(1cm);
  draw(unitsquare);
  label("$P_{0,0}$", (0,0), SW);
  label("$P_{1,1}$", (1,1), NE);

调整图的大小:
asymptote中用直角坐标绘图,默认时候一个点的大小是1/72 inch. 所以从(0,0)到(0,72)的线段长度是1 inch.有两种方法可以调整图的尺寸:

• 设置单位长度
  
  

  unitsize(1cm);

  这样(0,0)到(0,72)的距离就是72 inch而不是1 inch
• 设置最大尺寸
  
  

  size(100,200);

  这样所画的图会被自动scale到100*200这样的大小. 如果使用
  
  

  size(0,200);

  x轴方向上不scale而在y方向上scale到200个pt

调试:

write(a)

输出a的值,

例子:
我作业中要画的马尔科夫链

size(400,200);
import flowchart;
block state0 = circle(" $0$ ", (0,0));
block state1 = circle(" $1$ ", (10,0));
block state2 = circle(" $2$ ", (20,0));
block state3 = circle(" $3$ ", (30,0));
block state4 = circle(" ... ", (40,0), fillpen=invisible, drawpen = invisible);

draw(state0);
draw(state1);
draw(state2);
draw(state3);
draw(state4);

add(new void(picture pic, transform t) {
    real r = 0.4;
    //state0
    draw(pic,"$\lambda$", state0.position(2-r, t){NE}..{SE}state1.position(r,t),0.5*N, Arrow);
    //state1
    draw(pic,"$\lambda$", state1.position(2-r, t){NE}..{SE}state2.position(r,t),0.5*N, Arrow);
    draw(pic,"$\mu$",state1.position(-r, t){SW}..{NW}state0.position(2+r,t),0.5*N, Arrow);
    //state2
    draw(pic,"$\lambda$", state2.position(2-r, t){NE}..{SE}state3.position(r,t),0.5*N, Arrow);
    draw(pic,"$\mu$",state2.position(-r, t){SW}..{NW}state1.position(2+r,t),0.5*N, Arrow);
    //state3
    draw(pic,"$\lambda$", state3.position(2-r, t){NE}..{SE}state4.position(r,t),0.5*N, Arrow);
    draw(pic,"$\mu$",state3.position(-r, t){SW}..{NW}state2.position(2+r,t),0.5*N, Arrow);
    //state4
    draw(pic,"$\mu$",state4.position(-r, t){SW}..{NW}state3.position(2+r,t),0.5*N, Arrow);
});

参考

• 官方文档Asymptote: the Vector Graphics Language
• 一个比较简短的tutorial Asymptote (Vector Graphics Language)

[数学]挑西瓜 (optimal stopping problem)

有N个房间,每个房间有一个西瓜,需要你挑出最大的那个西瓜.你需要按着房间顺序一个房间一个房间的查看西瓜.每当你看完一个房间的西瓜后,你需要立即决定是(1)挑选当前的西瓜还是(2)接着往下看.如果挑了当前的西瓜你就不能看后面其他房间.如果往下看了就要放弃当前西瓜而只能选择后面房间里的西瓜.使用怎样的策略能够让你最大化自己挑到最大西瓜的概率.

Sol: 这是传说中的Secretary Problem. 一个众所周知的算法是: 对于前s个房间只用于观察,我们记下前s-1个房间最大西瓜的尺寸.然后从第s+1个房间开始,一旦碰到比我们记下的尺寸还大的,就挑选之.如果一直没有碰到,就挑选最后一个房间里的.记Pr(s)为挑到最大西瓜的概率.

Pr(s) = \sum_{j=s}^n \frac{1}{n}\frac{s-1}{j-1}=\frac{s-1}{n}\sum_{j=s}^n \frac{1}{j-1}

这里1/n 是最大西瓜在第j个房间的概率,(s-1)/(j-1)是之前j-1个房间中最大的西瓜在房间1到房间s-1的概率. 可以证明s取n/e的时候这个概率取最大值.


Odds算法是该题另一种解法,事实上它的实用性更广.

[Linux]在ubuntu上安装/使用Chrome

1 获取并安装:

安装Chromium: http://www.ubuntugeek.com/how-to-install-chromium-google-chrome-in-ubuntu-using-deb-package.html
安装Google Chrome: http://dev.chromium.org/getting-involved/dev-channel

二者稍微有一些区别.Chromium是Google主持的开源项目. 任何人都可以去www.chromium.org去下载并编译Chromium. Google从Chromium获取源码后加入一些东西比如Updater然后以Google Chrome的名字发布.外观上二者图标颜色不一样.

2 字体小:
我在Ubuntu上运行的Chrome中文字体偏小.
在～/.config/google-chrome/Default路径下修改Preferences. 加入了红色显示的两行后,字体就正常了.

"webkit": {
      "webprefs": {
         "default_fixed_font_size": 16,
         "default_font_size": 16,
         "fixed_font_family": "Microsoft YaHei",
         "minimum_font_size": 16,
         "minimum_logical_font_siz": 16,
         "sansserif_font_family": "Microsoft YaHei",
         "serif_font_family": "Microsoft YaHei"
      }
   }

[数学]连续两天降雨的概率

问题:(from mitbbs) Weather forecast: 50% chance of rain tomorrow, 75% chance of rain the day after tomorrow. What is the chance of rain for both tomorrow and the day after tomorrow?

Sol: 50%*75%? 这并不是一个严谨的答案.因为明天降雨和后天降雨未必是两个独立事件. 所以应该给出的是一个界

1/4=max{0, P[明天降雨]+ P[后天降雨]-1}< P[明天降雨 and 后天降雨] < min{P[明天降雨], P[后天降雨]}=1/2

[数学]阿里巴巴开门

问题:阿里巴巴试图潜入山洞。在山洞入口处有一面鼓。鼓的侧面有四个一模一样的小孔，组成正方形的四个顶点。在每个孔的里面各装有一个开关。开关有“上”“下”两种状态。(注意：眼睛看不见！)如果四个开关的状态全都一致，洞门即可打开。现允许将手指伸入任意两个孔，触摸开关以了解其状态，并可随自己的意改变或不改变其状态。但每当这样做了之后，鼓就要飞快地旋转，以至在停转之后无法确认刚才触动了哪些开关。证明：阿里巴巴至多需将手指伸入五次，就可以进入山洞。

Sol: 友情鸣谢X公子&S太后奉献的答案! 撒花~~
将开关状态设为A,B两个状态，并用连续四个字母表示当前鼓上四个开关按照顺时针方向排列的状态。由于每次操作后鼓都会旋转，可以认为每一步只有两种可能的操作：选一条边上两个开关（下称“边”）或者选一条对角线上的两个开关（下称“对角”）

第一步：对角。若不一致则调为一致。此时若门没开，则只可能有两种状态：AAAB或者ABAB。

第二步：对角。分两种情况：
1）手伸入时状态一致，则一起翻转状态。若之前为ABAB状态则门开。若门没开，则之前为AAAB状态，翻后仍然为AAAB状态（A,B对称）。
2）手伸入时状态不一致，则之前为AAAB状态。保持原样。
第二步结束后可知此时状态为AAAB。

第三步：对角。分两种情况：
1）手伸入时状态一致，则翻转其中一个。可知结束时为AABB状态。
2）手伸入时状态不一致，则翻转其中一个。若门没开，则结束时为ABAB状态。

第四步：
（若上一次结束时知道是ABAB状态，跳过这一步，直接进入第五步）
上一次结束时知道是AABB状态，则选边，无论状态如何同时翻转两个开关。分两种情况：
1）手伸入时状态一致，则一起翻转，门开。
2）手伸入时状态不一致，则翻转后变成ABAB状态。

第五步：对角。同时翻转两个开关。由于之前状态为ABAB，则翻转后门开。

[SVN]SVN速查

参考

---

SVN refence
SVN: How to resolve a conflict

常用命令

---

1 创建工程myproject1

svnadmin create /home/svn/myproject1

在/home/svn目录底下, 你可以看见每个工程都对应一个目录. 目录里存放的是改工程的相关数据库.每个工程有不同的设置,也有自己独立的commit number.

2 导入目录mydir1进入myproject1

$ svn import -m "New import" /path/to/mydir1 file:///home/svn/myproject1/mydir1
Adding         mydir1/file1
Adding         mydir1/file2
…
Transmitting file data .........
Committed revision 1.

3 检出工程

svn co file:///home/svn/myproject1

或者

svn co svn+ssh://hostname/home/svn/myproject1

4 添加文件或者文件夹

svn add newfile

如果要添加文件夹newdir,但是不包括newdir底下的已有文件(默认是递归添加的)

svn add --depth empty newdir

5 提交更改

svn commit -m "add newfile"

6 查看本地或者网络svn工程目录的情况

svn list http://192.168.61.79/repos/server
svn list -v http://192.168.61.79/repos/server

7 查看服务器端foo.c的内容,保存到当前目录的foo.c.tmp中.

svn cat foo.c > foo.c.tmp

查看foo.c在111版本时的内容

svn cat foo.c -r 111

8 检出某一版本的工程文件

svn co http://192.168.61.79/repos/server -r 4

9 改变当前已存在的工程文件到某个版本

svn update -r 4

10 删除某个文件或者目录

svn delete foo.c

11 查看当前目录或者网络上的svn工程的情况

svn -v status

12 查看工程的更新信息

svn log
svn log http://192.168.61.79/repos/server

13 只更新某个文件(比如foo.c)

svn update foo.c

14 放弃foo.c中的地修改，将其恢复到服务器上的版本

svn revert foo.c

15 消除foo.c的conflict标记

svn revert foo.c

冲突解决

---

多人使用svn合作的时候,常常发生对文件修改的冲突.比如user1 checkout了foo.c的一个版本后,做了本地修改, 然后commit. 但是user2 在user1 commit之前也checkout 了foo.c.等到user2来commit的时候就会被告知:

svn: Commit failed (details follow):
svn: File or directory 'foo.c' is out of date; try updating
svn: resource out of date; try updating

user2这个时候运行

svn up
Conflict discovered in 'foo.c'.
Select: (p) postpone, (df) diff-full, (e) edit,
        (mc) mine-conflict, (tc) theirs-conflict,
        (s) show all options:

这是因为svn发现了conflict, 需要user2采取措施解决. user2可以采取的动作总共包括

(e)  edit             - change merged file in an editor
(df) diff-full        - show all changes made to merged file
(r)  resolved         - accept merged version of file

(dc) display-conflict - show all conflicts (ignoring merged version)
(mc) mine-conflict    - accept my version for all conflicts (same)
(tc) theirs-conflict  - accept their version for all conflicts (same)

(mf) mine-full        - accept my version of entire file (even non-conflicts)
(tf) theirs-full      - accept their version of entire file (same)

(p)  postpone         - mark the conflict to be resolved later
(l)  launch           - launch external tool to resolve conflict
(s)  show all         - show this list

这里我们的选择包括

• 如果接受user1的版本而放弃本地修改,选择tc或者tf. 使用tf的话会整个文件一起使用user1的版本,哪怕中间有不冲突的部分.
• 如果坚持本地修改,选择mc或者mf. mf就整个文件都使用user2的版本
• 如果想要手动修改解决冲突,就使用e (edit)
• 如果暂时不做决定,等一会再说, p (postpone)

[数学]比较两个随机数大小

问题:(zz from mitbbs)在两张纸A,B上分别随机写两个数字，两个数字不相等。所以猜对哪个大的概率为1／2。现在随机翻开A或者B，再猜A或者B上哪个数字大。设计一种策略使得你猜对的概率大于1/2。

答案:不妨设A,B都为[0,1]之间的均匀分布.如果我们在猜之前知道A=x,那么当x<1/2的时候我们以概率(1-x)猜测B大,如果x>1/2我们以概率x猜测A大.采用这种随机策略,我们可以获得准确率:

\int_{x=0}^{1}x^2+(1-x)^2 d x = \frac{2}{3}

[TeX]TDS: TeX文件目录结构

本篇尚未完成

理论篇

什么是TDS

TeX系统目录结构（TeX Directory Structure）简称 TDS,是 TUG（TeX Users Group）主持制定的标准,目的在于方便TeX的开发者和用户.目前流行的 MiKTeX 套装和 TexLive 套装都支持 TDS.

TEXMF树

TEXMF = TeX + MetaFont
texmf树,由于其不必要的庞大和复杂,而被诟病.但是它也带来了一些好处.比如你可以在不同的树下,分开安装维护不同版本的TeX.
一般我们同时拥有好几棵texmf树,它们有大致相同的组织结构,被委以不同的职责

1. TEXMFMAIN:主要的树
2. TEXMFLOCAL: 通常是对TEXMFMAIN的补充,
   
3. HOMETEXMF:通常可以用来存放一些非public的(不是所有用户都可以使用的).比如只有你个人拥有许可的包, 或者你正在开发的包.
   

每棵树的组织结构大致如下:

.sty, .cls or .fd: $TEXMF/tex/<format>/<package>/
.mf:   $TEXMF/fonts/source/<supplier>/<font>/
.tfm:  $TEXMF/fonts/tfm/<supplier>/<font>/
.vf:   $TEXMF/fonts/vf/<supplier>/<font>/
.afm:  $TEXMF/fonts/afm/<supplier>/<font>/
.pfb:  $TEXMF/fonts/type1/<supplier>/<font>/
.ttf:  $TEXMF/fonts/truetype/<supplier>/<font>/
.otf:  $TEXMF/fonts/opentype/<supplier>/<font>/
.pool, .fmt, .base or .mem: $TEXMF/web2c

实战篇

找到你自己的${TEXMFMAIN}

kpsewhich -expand-var='$TEXMFMAIN'

在我的MacTex(基于TeX Live)上结果为/usr/local/texlive/2010/texmf

找到自己的texmf.cnf

kpsewhich texmf.cnf

metapost中使用label, 用gsview 来preview的时候报错: "undefined cmr10"
这是因为mpost 对*.mp 处理后得到的图形是 PS 格式,但是是没有嵌入字体,所以gsview无法显示

参考

[1]LaTeX之TeX系统目录结构
[2]A Directory Structure for TeX Files
[3]一个很不错的TeX笔记blog
[4]TDS in TeX Live

[数学]The Ballot Problem

问题:在2009步步高音乐手机快乐女生的PK环节里,芒果台设定江小花得A票,喻娘娘得B票.因为芒果台是邪恶的,所以A>B.请问导演能设计出多少种投票方法能够让投票环节里,江小花一直领先?

答案:

\frac{A-B+1}{A+1}{A+B \choose A}

The Ballot Problem
http://webspace.ship.edu/msrenault/ballotproblem/
http://mathworld.wolfram.com/BallotProblem.html

[数学]一辆需要猜测位置的车

We have a infinity road and a car whose initial position(at time t=0) is some integer coordinate which you don't know.The car is running at a fixed velocity of some other integer per second which you do not know neither. You even do not know the car is running towards +infinity or -infinity.

What you can only do is at a single integral time point you can make a query like this: Is the car at point x now? (you can choose the integer x).You can do query only once at a time and will be given the answer "yes" or "no" based on the truth.

Design a query strategy such that you can guarantee you will get a "yes"
answer in finite time.

Sol: Hint Cantor Paring Function:

Mathematica速查

自定义函数:

In[1]:= f[x_]:=x^2+1

求解方程:

In[1]:= Solve[x^2+2x-a == b, x]

求极限:

In[1]:= Limit[Sin[x]/x, x->0]
In[2]:= Limit[1/x, x->Infinity]

求导数:

In[1]:= D[Exp[x],x]

二阶导数

In[2]:= D[Exp[x],{x,2}]

求和:

In[1]:= Sum[a^i/i, {i,1,M}]

绘图:

In[1]:= Plot[Sin[x],{x,0, Pi}]
In[1]:= Plot[{Sin[x], Cos[x]},{x,0, Pi}]

删除符号的赋值:

In[1]:= M=.

删除符号:

In[1]:= Remove[M]

导入数据:

In[1]:= Import["foo.dat","Table"]

拟合:

In[1]:= Fit[{{1,10},{2,25},{3,31},{4,40}}, {1,x}, x]
In[1]:= Fit[Import["foo.dat","Table"], {1,x}, x]

多项式展开:

In[1]:= Expand[(1 + x + x^2) (1 + x)]
Out[1]:= 1 + 2 x + 2 x^2 + x^3

分解因式:

In[1]:= Factor[1 + x^3]
Out[1]:= (1 + x) (1 - x + x^2)

多项式化简:

In[1]:= Simplify[(1 + x)^2 - (1 - x)^2]
Out[1]:=  4x

gnuplot速查

绘制曲线

---

1. 绘制预定义的函数:
   

   plot sin(x)+exp(x)

   除了sin(x)外, 还支持的其他函数包括: abs(x),acos(x),asin(x),atan(x),cos(x),cosh(x),erf(x),exp(x),inverf(x),invnorm(x),log(x),log10(x),norm(x),rand(x),sgn(x),sin(x),sinh(x),sqrt(x),tan(x),tanh(x).
2. 绘制自定义函数:当预定义的函数不够用的时候,我们可以自己定义函数
   

   y(x)=x**2+log(x)
   z(x)=x**3-x

   gnuplot还支持?:这种C风格的函数.比如
   

   f(x) = x < 1 ? 1
        : x < 2 ? 3
                : 5

   就是f(x) =1 if x<1, =3 if 1<=x<2 =5 otherwise
   然后绘制上述两自定义函数的图像:
   

   plot y(x), z(x)

   还可以直接这样作:
   

   plot y(x) = x**2+log(x), y(x), z(x)=x**3-x, z(x)

3. 从文件中读取数据并绘图:
   使用foo.dat第1列(作为x)和第2列(作为y)来画图
   

   plot "foo.dat" using 1:2

   使用foo.dat第1列和第2列作为数据,但每2行skip掉一行
   

   plot "foo.dat" using 1:2 every 2

   使用foo.dat第1列(作为x)和第2列(作为y)做第一条曲线,使用foo.dat第1列(作为x)和第3列(作为y)做第二条曲线
   

   plot "foo.dat" using 1:2, "foo.dat" using 1:3

   foo.dat第3列作为errobar:
   

   plot "foo.dat" using 1:2:3 with yerrorbars

   foo.dat的第二列除以第一列作为y值
   

   plot "foo.dat" using 1:($2/$1)

   foo.dat分为若干个block(block之间用两行回车隔开), 使用第2个block绘图
   

   plot "foo.dat" index 1 using 1:2

4. 重绘:
   

   replot

5. 指定曲线的名称:
   

   plot "foo.dat" using 1:2 title "sample curve"

曲线样式设定

---

1. 指定曲线种类
   曲线种类包括`lines`, `points`, `linespoints`, `impulses`,
   `dots`, `steps`, `fsteps`, `histeps`, errorbars, `xerrorbars`,
   `yerrorbars`, `xyerrorbars`, errorlines, `xerrorlines`,
   `yerrorlines`, `xyerrorlines`, `boxes`, `filledcurves`, `boxerrorbars`,
   `boxxyerrorbars`, `financebars`, `candlesticks`, `vectors`
   

   plot "foo.dat" using 1:2 with lines # 用线条画图
   plot "foo.dat" using 1:2 with points # 用点画图
   plot "foo.dat" using 1:2 with linespoints # 用点线结合的方式画图
   plot "foo.dat" using 1:2 with boxes # bar-chart
   plot "foo.dat" using 1:2:(sprintf("%.2f", $2)) with labels # 在图上标注数字
   

   更多的曲线样式比如financebars等 参见Plot Style , errorbars
   

   plot  "foo.dat" using 1:2:3:4:(width)\
           with boxerror fs pattern 1 #x:mean:min:max:box_width

   
   给定了曲线样式, 它的还有四种参数可以自行设定:linetype, linewidth, pointtype, pointsize. 可以用test 命令查看所有支持的style.
   
2. 指定曲线颜色(linetype)
   

   plot "foo.dat" using 1:2 with lines linetype 1

   lt(linetype)指定点或者线的颜色-1=black 1=red 2=grn 3=blue 4=purple 5=aqua 6=brn 7=orange 8=light-brn
   或者通过更直接的linecolor方式指定颜色(gnuplot 4.2 or later),比如
   

   plot "foo.dat" using 1:2 with lines linecolor rgb "red" 
   plot "foo.dat" using 1:2 with lines linecolor  rgb "#ff0000"

3. 指定曲线宽度(linewidth)
   

   plot "foo.dat" using 1:2 with lines linewidth 6

4. 指定marker(pointtype)
   可以单独对每条曲线指定marker size,
   

   plot "foo.dat" using 1:2 with points pointsize 2

   也可以对所有曲线指定(默认大小为1)
   

   set pointsize 2

   如果使用points 或者linepoints画曲线的话,这里的piont相当于marker.可以用 pointtype和pointsize指定marker的样式和大小。
   pt指定marker的种类1=diamond 2=+ 3=square 4=X 5=triangle 6=*
   
5. 自定义linestyle
   如果觉得在plot语句中使用上述这些曲线修饰太麻烦,有碍观瞻,可以实现设定好一个linestyle, 然后在plot语句中指明使用该种style. 比如
   

   set style line 1 lt 1 lw 1 lc rgb "red"
   set style line 6 lt 2 lw 3 lc rgb "blue"
   plot sin(x) w l linestyle 1, cos(c) w lp linestyle 2

坐标轴设定

---

1. 设定坐标轴名称:
   

   set xlabel "time(t)"
   set ylabel "A"

   使用LaTeX数学符号:
   

   set ylabel "{/Symbol f_i}"

2. 设定坐标轴为logscale:
   

   set logscale x

   取消logscale的x轴
   

   unset logscale x

3. 坐标轴的刻度的格式
   
   每个刻度值后面加上百分号
   

   set format x  "%g%%"

   以指数形式表现, 比如10^1, 10^2,10^3而不是10, 100, 1000
   

   set format x  "10^{%L}"

4. 设置坐标轴的范围
   

   set xrange [-3:65]
   set yrange [ 4:14]

   也可以在绘制的时候指定：
   

   plot [-3:65] sin(x)

5. 指定坐标轴刻度
   

   set xtics ("x=1" 1, "x=10" 10, "x=100" 100)

6. 指定坐标轴刻度间隔宽度
   

   set xtics 100

7. 指定坐标轴刻度起始值和间隔
   

   set xtics 0, 100  #坐标轴小于0的部分就没有刻度了

8. 去除坐标轴刻度的mirror(x2,y2默认不在x,y上有mirror, 但是x,y默认在x2,y2上有)
   

   set ytics nomirror  #y坐标轴的tics在y2上没有mirror

9. 将X坐标值作为日期来显示
   

   set xdata time
   set timefmt "%s" #输入时间数据形式为time()函数返回值
   set format x "%b/%y" #输出时间数据形式为month/year

图例

---

1. 图例的位置可以是"left", "right", "top", "bottom", "outside" 和 "below",
   默认是"right top",
   

   set key left bottom
   set key outside

   也可以用坐标指定(这里的坐标是指图例中第一行文字和符号之间的中点坐标)
   如果你使用的gnuplot 4.6以下

   set key 100,40

如果你使用的gnuplot 4.6以上

set key at 100,40

图例字体大小不能单独设定,使用的是在set term中指定的大小

取消图例

unset key

输出

---

1. 输出显示在屏幕上:
   

   set term x11

2. 输出为eps文件(默认输出在stdout上,所以你将看见大批ps指令):
   

   set term postscript eps enhanced

3. 输出为png文件(默认输出在stdout上,所以你将看见大量binary被输出):
   

   set term png

4. 将输出放在文件上
   如果另存为eps文件
   

   set output "foo.eps"

   如果另存为png文件
   

   set output "foo.png"

图的大小

---

1. 设定X轴与Y轴的横纵比例为3:1
   

   set size ratio 3

2. 设定整个figure(包括了坐标轴以及边距)的横纵比例为2:1(默认值是1:1)
   

   set size 2,1

3. 生成figure的绝对大小是和terminal相关的

其他

---

1. 网格
   

   set grid
   set grid y
   unset grid

2. 边框. 边框的设定可见这里. 简单说来就是通过一个掩码来指定用哪几个边框1(bottom), 2(left), 4(top), 8(right)
   

   unset border # 没有边框
   set border 3 #只留下左边和下边的边框
   

3. 消除生成的eps周围过多的margin
   

   $eps2eps input.eps output.eps

4. 在指定坐标上绘制label
   

   set label center at 11.5,1.5 "My-Fav-Label!" font ",6"

5. 读取并执行一个gnuplot文件,比如把一些命令或者设定放在一个文件里
   

   load "your-gnuplot-file"

参考:

---

[1] 史上最好的gnuplot参考,有木有?
[2] set命令可以设定的参数
[3] gnuplot 使用技巧
[4] 和latex的psfrag配合使用
[5] Gnuplot tricks: 相当赞的一个帖子
[6] Gnuplot的demo,可以照着选自己需要的样式

[Linux]GDB笔记

本文参考了如下资源
GDB quick reference: 一个很不错的cheatsheet
RMS的gdb tutorial
中文的gdb教程

1 最基本用法

---

最基本的gdb用法可以帮助你找到程序里哪里出现segment fault。首先你要在gcc编译的时候加上-ggdb选项。假定你的程序名叫foo,你可以用如下命令进入gdb开始program进行debug：

$ gdb foo

gdb会在你出现段错误的地方停下来，你会看到是哪个程序哪行语句出了问题.
2 Core Dump

---

发现了segment fault的话,还可以使用core dump。这样不但可以很方便的找到出问题的代码. 还可以多次重现这个错误。 首先使用以下的命令允许系统生成core文件.

$ ulimit -c unlimited

然后运行你的代码,比如叫foo, 等到segment fault发生并异常退出以后， 你会发现在foo的同一个文件夹下多了一个名字类似core.1234这样的文件。这时候运行如下命令就可以重现案发现场了

$ gdb foo core.1234

3 普通用法

---

r [arglist]: (重新)运行程序
b [file:]line, b [file:]function: 设置断点在line或者function
c, continue: 继续运行程序
s, step: 单步执行, 进入函数
n, next: 单步执行, 不进入函数
finish: 执行完当前frame
kill: 终止当前程序
q, Ctrl-d: 退出gdb
p [expr]: 显示表达式expr. 比如var表示变量var的内容而 &var表示变量var的内存地址
bt: 显示当前调用栈(call stack)
set args [arglist]: 设置命令行参数,从而可以直接用r(run)来执行

4 断点(breakpoit)/观察点(watchpoint)设置与管理

---

b [file:]line, b [file:]function: 设置断点在line或者function
watch [expr]: 设置观察点，一旦表达式expr有变化就停下来. expr通常为一个变量或者内存地址
rwatch [expr]: 设置观察点，一旦被读就停下程序
awatch [expr]: 设置观察点，一旦被读或者被写都停下程序
比如你可以使用awatch *(long*)addr来监视内存地址addr是否被读或者被写
info breakpoints/watchpoints: 查看当前设置了的断点和观察点, info watchpoints是info breakpoints的alias
enable/disable/delete [n]: 激活/禁用/删除 编号为[n]的断点/观察点

5 程序栈

---

bt, backtrace: 显示当前调用栈(call stack),比如

(gdb) bt
#0  0x000000010005ea07 in init (ctx=0x100622070, opts=@0x10060d078) at Utils.cpp:1678
#1  0x00000001000149ad in main (argc=3, argv=0x7fff5fbffb30) at main.cpp:591

frame: 改变frame,比如

(gdb) frame 1
#2  0x8048414 in main (argc=1, argv=0xbffffaf4) at test.c:19
19        x = func1(x);

info frame: 查看当前frame的信息

(gdb) info frame
Stack level 2, frame at 0xbffffa8c:
eip = 0x8048414 in main (test.c:19); saved eip 0x40037f5c
called by frame at 0xbffffac8, caller of frame at 0xbffffa5c 
source language c.
Arglist at 0xbffffa8c, args: argc=1, argv=0xbffffaf4
Locals at 0xbffffa8c, Previous frame's sp is 0x0
Saved registers:
ebp at 0xbffffa8c, eip at 0xbffffa90

info locals: 查看当前frame里的局部变量

(gdb) info locals
x = 30
s = 0x8048484 "Hello World!\n"

info args: 查看当前frame的调用参数

(gdb) info args
argc = 1
argv = (char **) 0xbffffaf4

6 查看变量/函数, 改变变量值

---

如果有一个指针变量it指向一个struct item, 查看这个struct item的内存地址:

(gdb) p it
$1 = (item *) 0x100700060

查看这个struct的内容

(gdb) p *it
$2 = {
  next = 0x100700000, 
  prev = 0x0
}

如果你有如下数组

int *array = (int *) malloc (len * sizeof (int));

你可以这样来查看你的数组

p *array@len

有时候你知道一段二进制代码所属的函数和偏移, 查这段对应的源代码:

list *myfunc+0x16

改变一个变量a的值为10

set variable a=10

7 查看内存

---

用命令"x /nfu <addr>"
n表示要显示的内存单元的个数
f表示显示方式, 可取如下值
x 按十六进制格式显示变量。
d 按十进制格式显示变量。
u 按十进制格式显示无符号整型。
o 按八进制格式显示变量。
t 按二进制格式显示变量。
a 按十六进制格式显示变量。
i 指令地址格式
c 按字符格式显示变量。
f 按浮点数格式显示变量。
u表示一个地址单元的长度
b表示单字节，
h表示双字节，
w表示四字节，
g表示八字节

8 其他

---

info source: 查看当前frame对应的源文件信息

(gdb) info source
Current source file is shared_ptr.hpp
Compilation directory is /usr/local/include/boost/smart_ptr
Located in /usr/local/include/boost/smart_ptr/shared_ptr.hpp
Contains 712 lines.
Source language is c++.
Compiled with unknown debugging format.
Does not include preprocessor macro info.

info threads: 查看当前线程数目以及状态

(gdb) info threads
       Id   Target Id         Frame
       3    process 35 thread 27  0x34e5 in sigpause ()
       2    process 35 thread 23  0x34e5 in sigpause ()
     * 1    process 35 thread 13  main (argc=1, argv=0x7ffffff8)
         at threadtest.c:68

[数学]三个囚徒的问题

从mitbbs上看到这道题,并查了wiki,觉得挺有意思的. 特别是两个版本细微的差别就会导致结果的不一样.

版本1
一个国王决定从3个囚徒A,B以及C中释放一个,处决另外两个.国王告诉A说,处决的犯人中不是A的那个(如果两个都不是A,则随机说一个)是B.A在得知这个信息以后,他被处决的概率是多少?
SOL: 1/3

版本2
一个国王决定从3个囚徒A,B以及C中释放一个,处决另外两个.国王告诉A说,处决的犯人包括B.A在得知这个信息以后,他被处决的概率是多少?
SOL: 1/2

用列举法来解释结果:

国王的决定	版本1国王告诉A	版本1可以排除掉	版本2可以排除掉
放A 杀B 杀C	B
放A 杀B 杀C	C	x
杀A 放B 杀C	C	x	x
杀A 放B 杀C	C	x	x
杀A 杀B 放C	B
杀A 杀B 放C	B

[TeX]关于Tex, Latex,以及**tex的一个小结

叫**TeX的东西太多了,我自己对它们的概念也很混淆.所以最近花了一些时间整理一下相关内容,作为笔记加深自己的理解.
名词解释:其实这里有一个很不错的TeX名词的分类解释:TeX Catalogue

• TeX: 所有**tex的源头,万物的本源. 它由Knuth爷爷用他自己钟爱的一种和Pascal很像的叫WEB的语言所编写的.由于年代的缘故,它有这样那样的局限性. 比如那个时候Knuth爷爷是为了给自己的巨著TAOCP(被视为Computer Science的圣经)排版所用,因此只考虑了支持英文.所以其输入必须是ascii编码的文本文件,而不能包括多字节的语言比如中文.再比如TeX的输出结果为dvi文件. dvi是"device independent format"的缩写.它使用点阵字体而不是轮廓字体.而点阵字体只有在特定大小的时候才最好看.
  Knuth爷爷拒绝对TeX再做改动,所以人们就对TeX作了各种各样的扩展.
  
• pdfTeX: 这是对Knuth的TeX的扩展,用于直接输出为pdf而不是dvi(TeX的输出).除此以外相对于TeX,它可以支持TrueType以及Type 1等轮廓字体.
  
• XeTeX: 对TeX最大的改进体现在支持unicode以及OpenType等现代字体. 因此对中文的输入的天然支持的.它的工作过程分为两步:第一步生成extended dvi文件(xdv);第二步再将xdv文件转为pdf文件. xelatex是使用XeTeX引擎来编译latex源文件的工具.
  
• luaTeX: 基于pdfTeX和Lua语言的TeX引擎. 同样也支持unicode.
• Primitive Tex: TeX原始命令.大约有300多个. 有兴趣的可以看一下这里 Primitive Tex.由于它非常的底层,所以一般人不会直接用它,而是用在它基础上的各种宏语言.
  
• plain TeX: Knuth自己创建的一种建立在Primitive TeX上的宏语言.大约有600多个命令.
  
我们来看一下用plain TeX所写的Hello World:

Hello, World
\bye

• ConTeX: TeX的另一种宏包.比如这是ConTeX 写的Hello World例子

  \starttext
  Hello, World
  \stoptext

  你可以在http://live.contextgarden.net/尝试在线编译ConTeX文件
  
• LaTeX: TeX的最为著名的一种宏包. LaTeX也是大有来头,它是由Leslie Lamport最初弄出来的.对于一般使用者,它比Knuth自己的plain TeX更加直观方便.版面配置的工作被相当大程度的减轻了,使用者可以更加专注在内容上.因此大获流行,比如很多(还是大多?)学术期刊或者会议都会prefer你用LaTeX来排版提交文稿.
  既然是宏语言,就实际上可以被替换成TeX可以理解的命令.同时你也可以在LaTeX文档中使用Primitive TeX的命令.LaTeX宏的格式定义在latex.fmt这个文件当中.遗憾的是它是一个二进制文件,无法直接阅读. 但是幸运的是我们可以从latex.ltx这个文件中看到我们所熟知的各种环境,比如tabular eqnarray等等.实际上latex.fmt正是从latex.ltx编译而来.
  LaTeX定义的标准命令和标准环境
  我们再来看一下用LaTeX写的Hello World程序.

  \documentclass{article}
  \begin{document}
  Hello, World
  \end{document}

• LaTeX distribution:为了用LaTeX来排版,你需要一系列工具,包括(1)编辑器(比如我用过vi, WinEdt, editplus, textwrangler,gedit,现在主要用emacs)(2)dvi浏览器(或者pdf浏览器)(3)最重要的:一套LaTeX发行.一个LaTeX发行通常要包括如下的程序:
  
  • tex: 把TeX 文件编译成DVI文件
    
  • pdftex: 把TeX 文件编译成PDF文件
    
  • latex: 最常用, 把LaTeX文件编译成DVI文件
    
  • pdflatex: 把LaTeX编译成PDF文件
    
  • dvi2ps: 把DVI文件转成PostScript文件
    
  • dvipdf: 把DVI文件转成PDF文件
    
  • dvipdfm: dvipdf的改进版本
    
• TeX live: LaTeX的一个跨平台的发行版, Win,Mac,Linux等主要平台上都有.
  
• MiKTeX: LaTeX在Windows平台上的发行版.在中国大家使用非常广泛的CTeX套装里就使用的是MiKTeX.

[Latex]Latex Cheating Sheet

常用环境
*一个空文档模板:

\documentclass[10pt,a4paper]{article}
\usepackage{graphicx}
\title{Empty Article}
\author{apc999}
\date{\today}
\begin{document}
\maketitle
Put your text here
\end{document}

*改变文档边距
在tex文档头部引用geometry宏包并加入边距参数:

\usepackage[top=1.0cm,right=0.5cm,bottom=1.0cm,left=0.5cm]{geometry}

*插入数学公式

\begin{eqnarray}
E=MC^2
\label{eq:relativity}
\end{eqnarray}

*插入图片
首先需要在tex文档头部引用graphicx这个宏包

\usepackage{graphicx}

在需要插入图片的地方:

\begin{figure}[h]
\centering
\includegraphics[width=0.8\textwidth]{foo.eps}
\caption{caption of figure foo}
\label{fig:foo}
\end{figure}

*插入子图
首先需要在tex文档头部引用subfigure这个宏包

\usepackage{subfigure}

然后在你需要插入图片的地方:

\begin{figure}
\centering
\subfigure[caption of foo]{
\label{fig:subfigure:foo}
\includegraphics[width=0.48\textwidth]{foo.eps}}\hfill
\subfigure[caption of bar]{
\label{fig:subfigure:bar}
\includegraphics[width=0.48\textwidth]{bar.eps}}
\caption{caption of subfigures foo and bar}
\label{fig:subfigure}
\end{figure}

** subfig包用法与subfigure基本一样,就是把\subfigure换成\subfloat
 **小的"花招":子图之间可以用\vline加一条竖线隔开,或者用\hfill,\hspace等命令控制间隔

*插入表格

\centering
\begin{table}[h]
\begin{tabular}{ll}
x & x \\
x & x
\end{tabular}
\caption{caption of table foo}
\label{tab:foo}
\end{table}

更多table的用法

*数学环境中大括号

\begin{eqnarray*}
y = \left\{ \begin{array}{ll}
a & \textrm{if $d>c$}\\
b+x & \textrm{in the morning}\\
l & \textrm{all day long}
\end{array} \right.
\end{eqnarray*}

实际上还有一个更简单的做法--用cases环境. 不过需要amsmath这个package

\usepackage{amsmath}

\begin{eqnarray*}
y = \begin{cases}
a & \textrm{if $d>c$}\\
b+x & \textrm{in the morning}\\
l & \textrm{all day long}
\end{cases}
\end{eqnarray*}

*贴源代码

\usepackage[]{listings}
\lstset{language=Python,tabsize=4}
\begin{lstlisting}
import sys
sys.stdout.write("Hello World")
\end{lstlisting}

*引用一段话

\begin{quote}
the quoted text
\end{quote}

*使用bibtex database file

\bibliographystyle{xxx} % 使用style文件xxx.bst
\bibliography{yyy}  %使用reference 数据库文件yyy.bib"

xxx可以为　IEEE，　acm，　plain，　abbrv等等
yyy为用户自己定制的bib文件
参考 BibTeX and bibliography styles

---

常用命令
\appendix: 这个命令本身不产生任何文本, 但是会改变其之后的section的标号
\hrule 产生一条水平线　http://www.personal.ceu.hu/tex/spacebox.htm
\gg,\ll 远远大于,远远小于

[Linux]字体配置

X下有两套字体系统:古老的X11 core font system 以及新的Xft and fontconfig.一般说来我们应该尽可能的使用后者.

1. Xft是"X FreeType"的缩写。当Xft被使用的时候,字体是由使用这些字体的应用程序来渲染,而不是像在X11 core font system中那样由X server负责渲染.
   
   在xft中用fontconfig库来决定字体该如何渲染.它包括系统定义的配置/etc/fonts/fonts.conf 以及用户自定义配置~/.fonts.conf.
   
   如果要自己添加字体,可以把字体文件或目录添加到/usr/local/share/fonts/.网上教程之类的通常是这样做.不过你也可以直接添加到~/fonts/这个路径下,该路径被/etc/fonts/fonts.conf默认的访问.所以你只需要把新添加的字体拷到~/.fonts就好了.比如我就把windows下的C:\WINDOWS\Fonts的simsun.ttc以及simshei.ttf文件考到了上述目录下.这样我就可以在linux中使用windows下的宋体,新宋和黑体.
   
   字体描述:采用如下格式[2]:
   

   <family>-<size>:<name>=<value>...

   比如
   

   times-12:bold:slant=italic,oblique

   
   常用命令:
   
   • fc-list pattern 显示符合指定条件的可用字体.比如
     "fc-list ":lang=zh-CN" family style weight file"就显示所有系统中可用的简体中文字体的名称,式样,权重以及包含该字体的文件的完全路径.
   • fc-cache option 为fontconfig系统建立字体cache
     "fc-cache -fv"强制(f,force)建立cache(哪怕之前的还up-to-date),v是verbose
     
2. X core font system
   
   字体描述: X logical font description (XLFD)[3][4].
   比如75-dpi, 12-point, Charter font的字体用XLFD格式描述出来便是：
   -bitstream-charter-medium-r-normal--12-120-75-75-p-68-iso8859-1
   
   常用命令:
   
   
   • xfontsel 选定并显示X字体的字符
   • xfd 显示指定X字体的字符
   • xlsfonts 输出匹配给定条件的X字体名称
   • mkfontdir 创建指定(默认当前)目录下X字体索引
   • mkfontscale 创建指定(默认当前)目录下矢量字体索引

参考
[1] Installing and Configuring Fonts
[2] An Xft Tutorial
[3] X Logical Font Description Conventions
[4] X logical font description -- wikipedia

[Latex]支持中文方案2:Xetex

比较了一下CJK和xetex,这两种最主要的Latex中文解决方案,还是xetex更完美.它可以使用系统中fontconfig支持的中文字体,你可以用

fc-list :lang=zh

来查看你当前系统中的中文字体.相比之下,texlive中自带的CJK只能支持区区几种.

CJK就好比是在Tex基础上为了支持unicode中文而打的补丁,而Xetex则是从根本上就支持unicode.所以应该是更有前途.我觉得可以视xetex为unicode版的tex,而xelatex就是对应着unicode版的latex.使用起来latex的基本语法几乎不用作改动, 你只需要加上若干针对xetex的命令在.tex源文件的前面

\documentclass{article}
%需要fontspec这个宏包设置字体
\usepackage{fontspec}
%指定文档的字体, 上面fc-list命令列出的中文字体都可以用在底下
\setmainfont[BoldFont=WenQuanYi Zen Hei]{SimSun}
%默认字体为SimSun,默认的bold(比如用在section title之类的地方)为文泉译增黑.
%还可以用\setsansfont, \setmonofont来设置文档的sans 和mono字体.

%针对中文设置下换行
\XeTeXlinebreaklocale "zh" %使用中文换行
\XeTeXlinebreakskip = 0pt plus 1pt %
% OK了,后面就和latex没有两样了

\title{Notes}
\author{apc999}
\date{\today}
\begin{document}
\maketitle
\section{中文}
你好,世界
\section{数学}
$$\sum_i x_i$$
\end{document}

把上面文件存为helloworld.tex.编译的时候就使用

xelatex helloworld.tex

结果如下:

Xetex在Mac上运行良好.不过在ubuntu 9.04上,我发现Xetex有一个bug.数学环境中的数学符号,比如\sum \alpha无法显示在编译出的pdf文档中.这里是我从网上找到的bug fix:http://www.mail-archive.com/debian-bugs-dist@lists.debian.org/msg631117.html按照这里说的更改以后就好啦!

[Latex]Paper中的作图+Latex相关

很凌乱的一些东西.在这里做个笔记.
====================第一部分 作图. ====================
作图工具很多,最最基本的包括excel, matlab.就不在这里复述.反正我都不爱用.excel的图太幼齿,matlab太笨拙.这里要提matplotlib以及gnuplot
(1) matplotlib
这是python的一个用于科技绘图的库.这个库比较神奇的一点是封装了一系列语法极其类似matlab的绘图函数在pylab这个文件中. 这样只要你安装了matplotlib,在一个python源程序当中import了pylab之后,就可以用诸如plot(X,Y)这样的matlab语法来绘制函数图像.实在是非常方便.
如果有python 和matlab的基本知识,上手时间几乎为0

由于图片在Latex文档中编译出来后通常会显得小, 先需要把默认字体增大:

import pylab
params = {'backend': 'ps',
'axes.labelsize': 14,
'text.fontsize': 10,
'lines.linewidth':2,
'legend.fontsize': 16,
'xtick.labelsize': 14,
'ytick.labelsize': 14}
pylab.rcParams.update(params)

(2) gnuplot
Unix世界中非常老资格的一个绘图工具.gnuplot的语法简单明了,学习曲线比较平缓.

gnuplot中有terminal这样一个概念.terminal其实是指输出设备.gnuplot支持接近80种不同的设备(或格式).我们常用的包括x11,png,postscript等等.选择x11的话就可以在X window中显示出我们要绘制的图像;而选择png, postscript的话则是告诉gnuplot你选择png 或者postscript格式的文件作为输出设备. gnuplot允许我们针对不同的输出设备做出统一或者不同的设定. 而且我们可以把设定写在~/.gnuplot当中让每次gnuplot启动的时候自动加载.比如我的设定包括

set terminal postscript eps enhanced color linewidth 2 font "Helvetica, 20"
set terminal x11 enhanced font "Helvetica, 15"

对于输出为eps的文件,我希望它字体大一些,线宽粗一些.通常paper里需要这样设定才能看得清楚.

绘图的基本用法包括
画一段sin(x)曲线

plot sin(x)

这里x取值范围默认是[-10,10],如果要改变x取值范围

set xrange [1:10]

如果要从文件里读入数据,比如用'data.txt'文件中第1列作x第3列作y作图,线段类型为"lines",这个curve取名为data1

plot 'data.txt' using 1:3 with lines title 'data1', 'data.txt' using 1:3 with lines title 'data2'

设置xlabel 以及字体(可选)

set xlabel "time t" font "Arial, 15"

设置输出文件名, 默认是STDOUT

set output "data.eps"

更新/重画

replot

(3) ploticus
一个商用绘图工具,不过好在免费.绘制出来的figure非常精美.但学习曲线非常陡.

================第二部分 Latex里插图================
(1)最基本的用法 无非就是先

\usepackage{graphicx}

然后在正文中需要插图的地方,

\begin{figure}[t]
\begin{center}
\showthe\columnwidth % Use this to determine the width of the figure.
\includegraphics[width=\columnwidth]{fig1.eps}
\caption{\label{fig:sin_cos} Plot of the sine and cosine functions.}
\end{center}
\end{figure}

如果是pdflatex, 可以支持png等非矢量格式图片

(2)使用psfrag这个包, 可以在latex文档中对插入的eps图片进行文字替换, 或者字体缩小/放大:

\begin{figure}[t]
\begin{center}
\psfrag{sin(x)}{$\sin(x)$}
\psfrag{cos(x)}{$\cos(x)$}
\psfrag{x (radians)}{$x$ (radians)}
\psfrag{y}{$y$}
{\footnotesize                  % Replace tick-lables with smaller font.
\psfrag{1.0}{1.0}
\psfrag{0.5}{0.5}
\psfrag{0.0}{0.0}
\psfrag{-0.5}{-0.5}
\psfrag{-1.0}{-1.0}
\psfrag{-8}{-8}
\psfrag{-6}{-6}
\psfrag{-4}{-4}
\psfrag{-2}{-2}
\psfrag{0}{0}
\psfrag{2}{2}
\psfrag{4}{4}
\psfrag{6}{6}
\psfrag{8}{8}
\showthe\columnwidth % Use this to determine the width of the figure.
\includegraphics[width=\columnwidth]{fig2.eps}
} % Note that the psfrag commands only work in the top-most environment.
\caption{\label{fig:sin_cos} Plot of the sine and cosine functions.}
\end{center}
\end{figure}

[数学]一道关于硬币的概率题

硬币不知道fair还是不fair,第一次扔是head,第二次让你赌,你赌哪个,概率多少? zz from mitbbs
SOL: 采用Bayes. 设硬币得到head的概率为p. 因为硬币不一定是fair, 所以这里p实际是一个随机变量. 在没有其他信息的情况下,我们假设p的先验是一个0到1之间的均匀分布,即U[0,1]. 这种情况下, 得到head的概率为:

P\{head\} = \int_{p=0}^1P{head|p}\mathrm{d}p = \int_{p=0}^1p\mathrm{d}p=\frac{1}{2}

投掷硬币得到head, 在这种情况下,p的条件概率密度函数f(p|head)就不再是U[0,1]. 这是因为p越大越容易得到head,因此得到head的时候以更大可能观察到比较大的p而不是等概率.f(p|head)的密度由下式求得.注意这里f(p)=1(均匀分布),以及P{head|p} = p.

f(p|head) =\frac{P\{head|p\}f(p)}{P\{head\}}=2p

所以给定head情况下,p的点估计:

\hat{p} = \int_{p=0}^1 2p p\mathrm{d}p = 2/3

再来一道类似的:6个小孩,3女2男,还有一个性别未知.随机选择6人中的一个,发现是男孩.那么未知的那个小孩是男孩的概率?
SOL: 假设未知的那个小孩是男孩的概率是p. 假定p=1/2
选出来的小孩是男孩的概率是
P{pick a boy}=P{pick a boy|unknown=boy}P{unknown=boy}+P{pick a boy|unknown=girl}P{unknown=girl}
=3/6*1/2+2/6*1/2=5/12

则
P{unknown=boy|pick=boy} = P{pick=boy|unknown=boy}P{unknown=boy}/P{pick a boy}=3/5

[Latex]支持中文方案1:CJK

update @ 2009/6/9:经过比较我还是觉得用xetex来支持中文更加简单.可以见本blog中的:Xetex起步
决定写一些中文文档，所以要装Latex的中文支持。在ubuntu上很简单：
我已经安装过了 texlive-full (没有的请先安装)，所以就只需要从源里安装latex-cjk-chinese(只针对中文，如果你还需要日文韩文，请安装latex-cjk-all)。
然后就可以试一下中文的latex文档了。
记住用

\begin{CJK}{编码种类}{字体种类}
\end{CJK}

把用到中文的地方包围起来就可以了。这里CJK环境可以换成CJK*环境，区别是CJK环境里中英文间会有空格而CJK*没有。编码种类可以是GB，Big5 也可以是UTF8，取决于你自己的locale设定。我是用的纯英文环境，所以都上的是UTF8。默认情况下字体种类选择不多，可以是gbsn(gb宋体)，gkai(gb楷体)，bsmi(big5宋体)，bkai(big5楷体)
可以实验一下这个文档：

\documentclass{article}
\usepackage{CJK}
\begin{document}
\begin{CJK*}{UTF8}{gbsn}
您好!
\end{CJK*}
\end{document}

[数学]一道小学应用题

近日，网友“跳水白菜”在天涯重庆上发帖，希望借网友的智慧，解答出一道小学六年级的数学题。

“一辆大客车和大货车分别从甲乙两地出发，经过7个小时相遇，然后仍按各自的速度前行，3小时后，大客车距乙地120公里，大货车距甲地 160公里，求甲、乙两地的距离是多少千米？”

解答出这样一道数学题，在最初回答问题的网友看来，似乎是一件很简单的事情。众多网友都给出了步骤和答案，但大多都采用了2元1次方程式，甚至3元1次方程式。有网友提出了尖锐的问题：小学生是没有学习过2元1次方程式的，更别谈3元1次方程式，这样的题目就不能使用这种方式解答。面对这样的题目，其内容和解答方式雷翻了众多的网友。

SOL:其实这道题不需要用到方程.我从小就喜欢把那些看似要用解方程才能做出来的题目硬是分步计算出来.这里给出这道题目的分步计算方法:
甲乙两地距离=甲速*7+乙速*7,同时又有 甲乙两地距离=甲速*3+乙速*3+120+160
我们可以得知 (甲速+乙速)*4 = 280 => 甲速+乙速 = 70 (公里/小时)
甲乙两地距离=70*7 = 490 (公里)

[算法]拳皇友谊赛

这两天看到的一道蛮好玩的题：
变态的比赛规则：为了促进各部门员工的交流，百度(baidu)举办了一场全公司范围内的"拳皇友谊赛"，负责组织这场比赛的是百度的超级"拳皇"迷W.Z. W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。

由于一些员工（比如同部门或者相临部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自己组成不同组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人则之间不会打任何比赛。

比如4个人，编号为1--4,如果分为两个组并且1,2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3,1 vs 4,2 vs 3,2 vs 4. 而如果是1,2,3一组，4单独一组，那么一共需要打三场比赛: 1 vs 4,2 vs 4,3 vs 4.

很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人,通过上面这种比赛规则，总比赛场数有可能为K场吗？比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛,如果分为三组则需要3场比赛。但是无论怎么分都不可能只需要1场比赛。

相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。

输入
每行为一组数据，包含两个数字 N, K

输出
对输入的N,K 如果N个员工通过一定的分组方式可能会一共需要K场比赛，则输出"YES",否则
输出"NO",每组数据占一行。所有的输入输出均为标准输入输出。

SOL:这道题是一道潜伏很深的动态规划。先建一下模：N个人，如果分成m组，每组x_i人，那么需要打的比赛场数是

\sum_{i\neq j} x_ix_j

。所以本题就是给定N,看是否能找到一个组人数划分使得上式等于K。

做一下变化:

K=\sum_{i\neq j} x_ix_j = \frac{(x_1+\ldots+x_m)^2-\sum_ix_i^2}{2}=\frac{N^2-\sum_ix_i^2}{2}

所以这里我们把这道题变成了如何找到m个数使得这m个数的和等于N，平方和等于N^2-2K。

令T(s)为所有"平方和为s的一组数的和"的集合，即:

T(s)=\{x_1+\dots+x_m|\forall \sum_ix^2_i=s\}

所以T(5)={3,5}，也就是说5可以分解为1+1+1+1+1也可以分解为1+2^2。
关于T(s)的递推式为

T(s)=\left\{\begin{array}{ll}
(\bigcup_{i=1}^{s/2} (\{t\} \cup T(i))\odot T(s-i)) & i=t^2\\
\bigcup_{i=1}^{s/2} T(i)\odot T(s-i) & \textrm{otherwise}
\end{array}
\right.

这里定义

A\odot B = \{ a+b | \forall a\in A, b\in B\}

边界条件: T(1)={1}

[算法]找树的重心

以前算法课作业做过这道题。今天在网上又碰到了。

给一个有n个结点的树，每个节点i都有一个正权重w(i),每条边j也有一个正权重c(j). 要求给出一个线性复杂度的算法，找出一个结点u，使得对其他所有结点i，w(i)*L(i)的总和最小，其中，L(i)为i到u路径上的所有边的权重和.

SOL: 本题贪心就足够了。记sumW为树上所有节点权重和(仅仅节点)以及WC_i[p]为以p为根的第i颗子树中所有节点权值和(仅仅节点)。如果P是重心，则　"sumW>2*WC_i[p]" 对于所有P的子树i成立--所有子树的权重都小于所有节点权重和的一半。为了找到满足这个条件的节点 用贪心就足够了。随便从一个节点开始，看到哪个子树的权重和超过所有节点权重和一半，就往那个子树移动。直到不能移动位置为止。

[Linux]抛弃scim投奔ibus输入法啦

网上面对于ubuntu大多数人推荐使用scim输入法。我一直用的就是scim-python。无奈它兼容性还是有问题，qt程序底下总是没法用热键切换。最近我的pidgin也老和它冲突。于是上网一搜，发现进来新的ibus输入法很流行。是scim-python的原作者写的。于是就去装了一个下来。对于ubuntu用户，步骤很简单。直接apt-get install ibus就可以了。好像官方源里暂时还没有ibus，我是添加了ppa的源。步骤可以参见这里。

除去ibus这个平台，还需要安装具体的输入法。比如我安装了ibus-pinyin 也就是拼音。还有ibus-table包括了五笔等输入法。由于我是gnome的桌面，还安装了ibus-gtk这个库，后面要用到。

然后就用im-switch -s ibus把输入法设置为ibus。没有im-switch的可以装一下，这样比较干净。不用再去profile里设置环境变量。然后重启看一下效果吧。这个ibus用起来很舒服， 有种在windows底下用google输入法的感觉。


另外我是emacs用户，所以一般都把默认的切换热键ctrl+space换成alt+shift。可以在ibus的preference里设置。需要注意的是alt+shift要加上release（键松开）的修饰，不然不行， 不知道为什么。

[算法]最近看到的几道有意思的题

1 某机器需要处理n个请求，每个请求都有其运行所需的存储空间(R[i])及运行之后输出所占用的存储空间(O[i])，且O[i]小于r[i]。假设CPU只能同时处理一个请求。现在该机器共有m个存储空间，请设计一个算法来安排这n个请求的处理顺序，使得所有请求都能被处理。并简要说明该算法的正确性。如果无论如何安排也不能处理完这些请求，算法也应能给出判断。SOL: 贪心法， 按照R[i]-O[i]降序排列请求

2 在一个空间里有m（m为偶数）只老虎，n只兔子，还有一个你，总共m+n+1只东西（什么，你说你不是东西？）每次随机地抽出两只东西发生互动（通常造成可怕的结果），幸存者再放回去。具体规则如下：
1）老虎和老虎->两相残杀
2）老虎和兔子->老虎吃掉兔子
3）兔子和兔子->没事
4）老虎和你->你成为老虎的美餐
5）你和兔子->你可以选择放回去或煮了兔子
问题是：最后你虎口余生(即，出现山中无老虎，猴子称大王的局面）的概率是多少（你需要在兔子问题上作出最优决策使此概率最大）
SOL: 1/(m+1) 本题最大的trick在于认识到兔子的存在其实根本不影响最后结果，可以直接忽略所有的兔子。剩下m只老虎和一个你。所求概率相当于你排在最后一位的概率。

3 16个人背后各贴一个数字，每个数字都可能取1到16的任意整数值（即可以重复，可以有数字不出现），每个人可以看到其他人的数字，但看不到自己的，贴好数字之后不可以进行任何形式的交流（诸如使用排队次序传达信息之类的伎俩无效），每人猜一个数字，问事先如何安排可以保证至少有一人猜中自己的数字。
SOL: 16个人每个人分别猜自己背后的数字,也就是16个人分别猜16个1-16的数字,显然无法保证一定一人猜中。但是如果16个人集中猜同一个1-16的数字X则能保证一定有一个人猜中, 方法是每一个人分别猜一个数，遍历解空间。这里我们这样人为制造出X:X = X1 xor X2 xor X3... xor X16 (X_i是第i个人背后数字).所以这个X对于所有人是一样的.于是可以第i个人可以猜测一个数Yi,这个数Yi满足和其他所有能看见的人背后的数字的xor之和为i.

[Emacs]调整字体

update @ 2009/6/09
对于最新的emacs 23版本,字体描述格式,已经从X Logical Font Description (XLFD)转变为更为简单的fontconfig方式.关于两种字体系统,可以参见本blog里这个帖子.不过为了向前兼容,XLFD依然被支持.比如同是描述13pt的Courier New字体,两种格式分别如下:

•      XLFD: -*-Courier New-normal-r-*-*-13-*-*-*-c-*-iso8859-1

•      Fontconfig: Courier New-13
  

在emacs 23里,set-default-font已经过时.实际如果在.emacs中使用了set-default-font,普通模式下emacs字体依然正确.但是如果是用daemon模式运行emacs23的client时候, client会不正常的设置字体.解决方法是在set-frame-font,或是使用default-frame-alist来添加字体, 如下

(add-to-list 'default-frame-alist '(font . "DejaVu Sans Mono-14"))

这样普通和daemon模式就都可以正确设置字体了.
对于emacs22以及更早版本的字体设置如下:
-------------------------------------------------------------------------------
说实话emacs里要调整个字体什么的还真挺麻烦的。一般的基于GUI的editor都比它来的简单直接。

1 关于Linux下的字体
使用xlsfonts来查看系统里有哪些字体

$xlsfonts

得到像如下格式的输出

-adobe-courier-medium-r-normal--17-120-100-100-m-100-iso8859-1
-dejavu-dejavu sans mono-medium-r-normal--0-0-0-0-c-0-iso8859-1

每一行都是一种系统支持的字体。每一行的格式参见 Font specification , 简单说来遵循“-maker-family-weight-slant-widthtype-style-pixels-height-horiz-vert-spacing-width-registry-encoding"这样的格式。需要特别指出的是pixels代表的是字体的高度(单位是像素)，height代表的是字体在屏幕上的高度*10(单位是磅), pixels和height两个当中通常只指定一个值，另一个用*代替。另外我们注意到列出来的字体当中有些字段为0,这说明这些字体是矢量字体。对于这些字段我们使用的时候需要用数字或者*来替换。

可以通过xfd来预览你想尝试的字体， 比如

$xfd -fn "-dejavu-dejavu sans mono-medium-r-normal--16-*-*-*-c-*-iso8859-1"   

2 回到Emacs
可以通过M-x set-default-font 然后输入字体名称(如果不知道可以用tab来complete)来设置当前字体。如果需要固定下来，可以在~/.emacs当中加入:

(set-default-font "-dejavu-dejavu sans mono-medium-r-normal--16-*-*-*-m-*-iso8859-1")

需要额外指出的是，这里我设置成了dejavu的等宽字体。不过我发现使用了这种字体以后，line spacing显得过大了，所以可以用以下语句来调整：

(setq-default line-spacing 0)

另外我这里的emacs有一点小bug所以set-default-font以后会有好几秒钟的延迟，需要在~/.emacs开头加入

(modify-frame-parameters nil '((wait-for-wm . nil)))

3 几个字体设置的小tip

• M-x describe-char 我们可以使用这个命令查看光标所在的字符采用的是什么字体。
• M-x describe-fontset 这个命令用来查看各个字符集分别采用了什么字体。
• 在*scratch* buffer中输入(frame-parameter nil 'font) 光标放在行末按C-x C-e就可以看到当前字体
• Shift + MouseLeftClick可以出来字体选择对话框;
• M-x describe-font可以查看当前字体描述
• M-x set-default-font 可以看到可以选择的字体。

参考:
[1] http://www.linuxquestions.org/questions/linux-software-2/emacs-changing-default-font-size-and-font-type-489000/
[2] http://www.yuanma.org/data/2006/0503/article_355.htm
[3] http://www.gnu.org/software/emacs/windows/Fonts-and-text-translation.html

[Python] Yaml与Json

Python2.6开始支持Json，见Json库。
Yaml的Python库见PyYaml

简单说起来:

1. Python的json库在默认设置下输出的是Yaml语言的子集
2. 两个库的语法基本一致。不同的是yaml的dump输出的直接为字符串，json的dump还需要指定一个stream object。如果要输出为字符串，得使用dumps
   

关于两者详细的关系和区别，这里有一片英文的文章讨论yaml与json的关系

[MacOS] MacOS系统使用经验笔记

1. 在Finder中找隐藏目录的热键: shift+command+G。默认的finder界面里是不会显示隐藏目录的。所以用上述热键然后手动输入路径
2. MacOS X中设置环境变量和普通Unix/Linux的方法略有不同。你依然可以像在Unix/Linux 中那样在~/.cshrc(tcsh)或者~/.bashrc(bash)里设置环境变量，对于terminal中的程序完全没有问题。但是对于基于Carbon或者Cocoa的Native Mac程序(比如Carbon Emacs)来说是没有用的。它们不会从shell中继承环境变量。一个方法是把$PATH, $PYTHONPATH等环境变量设置在~/.MacOSX/environment.plist这里。可以用(a) "/Developer/Applications/Utilities/Property List Editor.app"这个工具修改. 也可以(b) 用defaults 命令:
   

   defaults write ${HOME}/.MacOSX/environment PATH "${HOME}/bin:/usr/bin:/bin:/usr/local/bin"

   
   为了在系统中使用统一的设置，在~/.cshrc中， 使用如下命令:
   

   setenv PATH `defaults read ~/.MacOSX/environment PATH` 

   
   
   注意： 需要重启以使改变生效
   Updated on Aug 27, 2012: ~/.MacOSX/environment.plist 已经deprecated了. 新的方法是修改/etc/launchd.conf使得所有Unix 环境变量在GUI中可见 参考Accessing the Unix environment from emacs and Cocoa apps in OS X Mountain Lion
   
3. 显示Mac里系统相关信息
   查看总体的系统信息

   $ system_profiler

   查看CPU信息

   $ sysctl -a machdep.cpu

   或者

   $ sysctl -n machdep.cpu.brand_string
   Intel(R) Core(TM) i5-2435M CPU @ 2.40GHz

4. 如果从打开Terminal开始到出现提示符为止的等待时间过长, osxdaily说这是由于系统的login process会读取/private/var/log/asl下所有的系统日志文件.所以我们可以把这些日志删除来加速login过程

   sudo rm -rf /private/var/log/asl/*.asl

5. 用命令行打印文件

   $ lpstat -a
   GHC6107_BW accepting requests since Sun Oct 28 15:30:42 2012
   GHC9206_BW accepting requests since Mon Oct 29 12:48:11 2012
   GHC9206_COLOR accepting requests since Mon Nov 28 13:00:02 2011
   
   $ lp -d "GHC9206_BW" -o sides=two-sided-long-edge *.pdf
   request id is GHC9206_BW-82 (6 file(s))

6. 在Lion以及Mountain Lion中关掉ipv6

   $ networksetup -setv6off ethernet
   $ networksetup -setv6off wi-fi

[算法]几个有趣的关于数列的O(1)空间O(n)时间小算法

1 数列L中有n个整数。其中有k个数字出现了两次，1个数字出现了一次(所以n=2k+1)。找出只出现一次的那个数字。
解： 将n个数字xor以后，重复出现的就会消失。剩下的就是只出现一次的。

2 数列L中有n个数。已知其中有一个数字出现了至少 n/2+1次。找出这个数字。
解： 用链表存储这n个数字。p指向当前考察的数字。p从链表头开始。如果p和p->next的数字相同，p=p->next，如果不同，则将p和p->next一同从链表中删除。当p->next是链表尾的时候，p就是所求数字。

3 数列L中有n=2k个数字a1,a2,...,an,b1,b2,...,bn。将其变换为a1,b1,a2,b2,...,an,bn。可以将这个问题理解为扑克里的洗牌。
解： 很难的题目。这里有一篇论文http://webhome.cs.uvic.ca/~jellis/perfect.html。

[Linux]Wine的一点使用经验

因为实在受不了Adacious的频繁出问题而分外想念win下的foobar，我装了wine。现在wine加上foobar运行的非常良好。下面记一下安装和使用wine的时候的一些问题。

安装

ubuntu上很简单:

apt-get install wine

中文支持

安装了wine以后，在~/.wine底下会有一个driver_c目录，这里是wine心目中的C盘。你可以之后再映射过来正真的D盘阿E盘阿，但这个C盘无法改变(至少我是没找到)。在这个driver_c目录下， 有一个windows/font 目录。可是刚刚装完的时候这里是空的。你可以把你喜欢的windows字体拷过来或是做上符号连接，比如重要的英文字体tahoma.ttf 以及重要的中文字体simsun.ttf。然后键入"wine regedit"调用wine的注册表，修改[HKEY_LOCAL_MACHINE\Software\Microsoft\Windows NT\CurrentVersion\FontSubstitutes]。把MS Shell Dlg 以及MS Shell Dlg2的键值由默认的tahoma改为simsun，这样就可以正确的显示中文了

程序中字体过小

这是由于dpi值设置的不够大。可以选择在winecfg的Graphics标签里调整dpi值大小(默认是96)。或者继续wine regedit修改[HKEY_CURRENT_CONFIG\Software\Fonts]里的LogPixels键值。LogPixels默认是60(十六进制,也就是十进制的96)。比如我就调整到了120。这样程序里的对话框以及文件选择框之类的的字就足够大了。

菜单/状态栏/消息框中的字体依然过小

调整过dpi之后，有可能发现程序里的字是大了，但是菜单之类的字体还是很小。这个问题我google了很久 "Wine", "MenuFont","tiny"之类，看到一些人问但是都没有答案。早先版本的wine可以通过设置win.ini里MenuFontSize等来解决。但新版本的不可以。下午参考着wine源码搞定了这个问题。原来wine会从注册表当中直接读取MenuFont/StatusFont/MessageFont信息。比如MenuFont信息既包括了字体也包括了大小。这几个键值在"[HKEY_CURRENT_USER\Control Panel\Desktop\WindowMetrics"]。但是是用二进制的形式存储的。所以你在user.reg当中可以找到"MenuFont"=hex:f5,ff,ff,ff...这样的字串。如果需要把字体调大，可以把第一个f5弄小一点，比如我调到f2就很好了。

[Python]可变长参数

Python支持可变长参数，函数参数中形如*arg这样的就是可变长参数。如果定义了def func(*arg)，则可以让接受不同个数的函数，比如func()以及 func("hello", "world")均为合法的函数调用。

下面这个例子用可变长参数调用func并将可变长参数*arg传递给func。比如test(sleep, 1)就相当于 sleep(1)；test(max, 1, -1)就相当于调用max(1,-1)。

def test(func, *args, **kargs):
    if not callable(func):
        raise RuntimeError, str(func) + ' not a callable object'
    else:
        func(*args, **kargs)

[Python]Python线程简例

第一部分：最简单的用法

Python提供了非常简单的线程用法。最简单的用法只要遵循下面几步：

1. 定义一个类(比如下面例子里的Job)继承threading.Thread
2. 在该类中必须实现__init__(初始化)以及run函数(该线程需要执行的代码).注意在__init__当中要调用Thread.__init__。其他成员函数和变量可以自己根据需要添加。
3. 用start函数启动线程。
4. (可选)用join函数来阻塞线程直至线程结束。
   

若不理解join的作用，可以看如下例子:

import os
import time
from threading import Thread
class Job(Thread):
   def __init__(self, cmd):
       Thread.__init__(self)
       self.cmd = cmd
       self.starttime = time.time()
   def run(self):
       os.popen(self.cmd)
       print "time %.2fs, job %s is done"%(time.time()-self.starttime,self.cmd)
jobs = []
for i in range(1, 5):
   j = Job("sleep %d"%i)
   jobs.append(j)
   j.start()
for j in jobs:
   j.join()
   print "time %.2fs, job %s returned"%(time.time() - j.starttime, j.cmd)

运行得到结果:

time 1.00s, job sleep 1 is done
time 1.00s, job sleep 1 returned
time 2.00s, job sleep 2 is done
time 2.00s, job sleep 2 returned
time 3.00s, job sleep 3 is done
time 3.00s, job sleep 3 returned
time 4.00s, job sleep 4 is done
time 4.00s, job sleep 4 returned

如果我们把最后一个循环的顺序该一下，变成倒叙（如下），其余部分不变

for j in reversed(jobs):
   j.join()
   print "time %.2fs, job %s returned"%(time.time() - j.starttime, j.cmd)

得到结果:

time 1.00s, job sleep 1 is done
time 2.00s, job sleep 2 is done
time 3.00s, job sleep 3 is done
time 4.00s, job sleep 4 is done
time 4.00s, job sleep 4 returned
time 4.01s, job sleep 3 returned
time 4.01s, job sleep 2 returned
time 4.01s, job sleep 1 returned

所以当你调用join时，仅仅是检查该线程是否以及结束。如果结束则返回；否则阻塞直至结束。
再来作一点变换， 对join加上参数timeout。 timeout指定调用join后多久停止阻塞。如果没有指定该参数（就像我们前面做得这样），则一直阻塞到线程结束:

for j in reversed(jobs):
   j.join(0.5)
   print "time %.2fs, job %s returned"%(time.time() - j.starttime, j.cmd)

我们得到

time 0.52s, job sleep 1 returned
time 1.00s, job sleep 1 is done
time 1.02s, job sleep 2 returned
time 1.52s, job sleep 3 returned
time 2.00s, job sleep 2 is done
time 2.02s, job sleep 4 returned
time 3.00s, job sleep 3 is done
time 4.00s, job sleep 4 is done

第二部分： 一个例子

在这个例子里面，我们使用指定数目个线程来完成一批任务。就好比1000个矿要采，但我们就只用9个农民轮流去采。

在这个例子里我们定义了一个Jobs类(乔布斯?)和一个Worker类。Jobs类通过继承Queue来维护一个任务队列。如果要添加新任务，就调用newjob。newjob函数的参数决定了一个任务：它们包括一个名字(name)，一个函数入口(func)以及相应的参数(args,kargs)。每个Worker类的实例对应一个线程，当线程开始执行或者idle的时候，就从任务队列中取一个任务，并执行这个任务。完成之后再接着做下一个，周而复始直至所有任务完成(任务队列为空)。

class Jobs(Queue.Queue):
    def __init__(self):
        Queue.Queue.__init__(self)
    def newjob(self, name, func, *args, **kargs):
        if not callable(func):
            raise RuntimeError, str(func) + ' not a callable object'
        self.put((name, func, args, kargs))
    def do(self, numthreads = 1, debug = True):
        threads = []
        for i in range(numthreads):
            t = Worker("thread%d"%i, self, debug)
            threads.append(t)
            t.start()
        for t in threads:
            t.join()

class Worker(threading.Thread):
    def __init__(self, name, jobs, debug = False):
        threading.Thread.__init__(self)
        self.name = name
        self.jobs = jobs
        self.debug = debug
    def run(self):
        while not self.jobs.empty():
            try:
                job  = self.jobs.get(True, 1)
                (name, func, args, kargs) = job
            except:
                break
            stime = time()
            func(*args, **kargs)
            if self.debug:
                print "%s is done by %s, fin in %.2f s"%(name, self.name, time()-stime

[Python] Python中的类型与对象

读了一篇文章Python Types and Objects探讨Python当中的类型与对象。要说这篇文章也算是写的不错，图文并茂的。可是我还是看的迷迷糊糊的。于是又多花了一些时间搞清Python里的关系。

一切都是对象

---

先从简单的说起

>>>mylist = [1,2,3]
>>>type(mylist)
<type 'list'>

所以这里我们新建了一个list的实例叫mylist。通过内建的type()函数我们可以查看这个实例的类型，返回的结果告诉我们它的类型是list这种内建的类型。

>>>type(list)
<type 'type'>
>>>list.__bases__
(<type 'object'>,)

这里我们先查看了list的类型。我们得知list的类型是type，换言之list是type的一个实例。紧接着我们用__bases__属性查看它的父类，得知list其实继承了内建的object。再来

>>>type(type)
<type 'type'>
>>>type.__bases__
(<type 'object'>,)

好，现在我们知道type的类型还是type自己，它是自己的一个实例，同时它继承了object。最后：

>>>type(object)
<type 'type'>
>>>type.__bases__
()

从而我们得知，object也是type的一个实例，同时它没有父类。

总结一下目前的结论：

• Python当中任何东西都是对象，它都要对应一个类型
• 为了表达这个类型，Python仍然使用了对象。所以int, list这些类型同时也都是对象。比方你可以用id(int)，id(list)得到这些类型的id(其实是这些对象的内存地址)
• 为了得到统一的解释(每个对象都对应一个类型)，便赋予int, list对象以一个type类型。type自己也是一个对象
• type的类型是自己，这个游戏从而可以结束了。
• object也是一种类型，可以类比于int, list。但是由于每样东西都是对象，所以int, list, type这些抽象的类型落实到instance以后又都是object派生出来的。

class 和 type 的统一

---

在Python2.2之前，class和type是阳关道和独木桥,互不相干。这种class也被称为老式类(old-style class)。从Python2.2之后开始，class可以被认为是一种用户自定义的类型，也被称为新式类(new-style class)。从地位上来说和list或者dict等类型一样。为兼容起见老式类依然被保留，并认为是一个类默认的类型。如果你要定义一个新式类，该类必须继承object，或者继承一个其他新式类。(注：Python3.0以后将不再支持老式类)

现在让我们作一下实验，分别定义一个老式类 oldclass和一个新式类 newclass:

>>>class oldclass:
...    def __init__(self):
...        pass
>>>class newclass(object):
...    def __init__(self):
...        pass

检验一下：

>>>oldobj = oldclass()
>>>newobj = newclass()
>>>print type(oldobj), oldobj.__class__
<type 'instance'> <class __main__.oldclass at 0x7f700714da10>
>>>print type(newobj), newobj.__class__
<class '__main__.newclass'> <class '__main__.newclass'>

这里我们可以看到新式类的类型和__class__是统一的。再来检验一下内建的dict：

>>>print type(dict), dict.__class__
<type 'type'> <type 'type'>

我们看到同样的结论。

本文参考:
Python Types and Objects
Data Model

[Python] CPython1.01源代码阅读笔记(1)

(未完结)
简介
CPython是官方的、使用最广的Python解释器。因为使用C语言实现而得名CPython。非官方的Python解释器还包括JPython(用Java实现)以及PyPy(用Python本身实现)。

关于CPython源码的阅读，网上我见到相关文章有:

• 张羿的Python源码分析
• Robert Chen的CPython源码剖析
  

这两篇侧重点各有不同。前者偏重CPython的词法语法分析，后者偏重解释器的执行机理。我的笔记会和前者重合度较高。事实上我也是参考着前者来的，有部分他略过或是简单提及的地方可能我这里会详细处理。

CPython 1.01是其官方网站上我能找到的最早的版本。这个版本应该是1994年左右release的。所以还是相当初期的时候，规模比较小，便于学习。
解压后我们可以看见它的目录结构包括:

Include/	C源代码的头文件(.h)
Lib/	用Python自己写的Python库文件(.py)
Python/	这里是"编译器"和解释器的源码，Python的核心所在
Grammar/	包括一个Grammar文件，用BNF描述Python语言语法
Parser/	生成pgen这个工具使用Grammar文件

一个编译器运作，必然离不开词法分析和语法分析，所以我们也从这里入手。
词法分析：
所谓词法分析是指将输入的字符流转变为token流。CPython中的token类型被定义在Include/token.h中。比如NAME就是一个token，它对应着关键字以及标识符。"a = b + 10"这个字符流对应的token流为"NAME EQUAL NAME PLUS NUMBER"。

从字符流到token流的转换在Python/tokenizer.c中完成。tokenizer的核心数据结构是tok_state。它的作用是记录当前tokenizer的状态，比如当前输入缓冲区的起始位置(buf)和终止位置(end)以及当前读取到的字符指针(cur)。

如果将tok_state看成tokenizer的成员变量们，你会看到tokenizer.c中还定义了下面这些tokenizer的成员函数:

• tok_new: 创建并返回一个tokenizer实例tok，下面提到的tok都是该tokenizer的实例，可以看成是一个全局的变量。
• tok_setups(str): 调用tok_new并将返回的tok绑定到一个字符串上。
• tok_setupf(f): 调用tok_new并将返回的tok绑定到一个文件上(可以是标准输入stdin，以便互交模式)。
• tok_free(tok): 将tok这个tokenizer实例释放。
• tok_nextc(tok): 从tok绑定的输入中读取下一个字符并返回。
• tok_backup(tok, c): 将c放回tok绑定的输入中(tok->cur--)
• tok_1char(c): 根据单个字符c返回token，比如"<"返回 LESS


• tok_2char(c1,c2): 根据连续两个字符c1, c2返回token， 比如 "<="返回LESSEQUAL


• tok_get(tok, p_start, p_end): 根据tok->cur的返回输入的字符流当前位置的token，以供语法分析。


• tok_dump(int type, char* start, char* end): 打印输出从start到end (均为字符指针)且类型为type的token，以供调试使用。

这些tok开头的函数当中，真正重要的其实就是tok_get--读取当前token。它会在语法分析中反复被调用。 语法分析： Python的语法分析需要借助Parser/目录下pgen这个工具。据Guido老师自己回忆，从Python release到现在，这个pgen是改动最小的部分了。这部分在我看来实现的很精彩。 先说一下python语法分析的基本原理。pgen实现了一个LL(1)的Parser。pgen的输入对象是Grammar/目录下的Grammar文件。 我们可以看一下Grammar文件里到底是如何定义Python语法的。比如其中最重要的几行包括：

stmt: simple_stmt | compound_stmt
simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE
small_stmt: expr_stmt | print_stmt  | del_stmt | pass_stmt | flow_stmt | import_stmt | global_stmt | access_stmt | exec_stmt
compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | funcdef | classdef

它表示每个stmt可以是一个simple_stmt也可以是一个compound_stmt。simple_stmt可以是几个small_stmt的同行并列用";"隔开。 small_stmt可以是expr_stmt, print_stmt, del_stmt等简单语句。而compound_stmt则包括if_stmt, while_stmt等需要跨越多行的复合语句。就这样Python用BNF范式定义了最基本的语法。 现在我们有了这个通俗易懂的Grammar文件以后，pgen负责把这个Grammar转换成NFA，然后再转换为相应的DFA，接着再化简这个DFA，最后保存在gramint.c 和gramint.h这两个文件中。如果你觉得很复杂，你只需要记住我们根据Grammar这个文件得到了一个语法规则就可以了。我们现在来看一下一个py交互模式的运作流程以便于理解：

1. 在pythonmain.c 的realmain()函数中，执行run(stdin, "")
   
2. 进入pythonrun.c的run(fp,filename)调用run_tty_loop
3. 进入pythonrun.c的run_tty_loop(fp, filename)，执行如下循环:
   

   run_tty_loop(fp,filename){
       for (;;) {
           run_tty_1(fp,filename); //不断执行一个“单行”语句
       }
   }

4. 进入pythonrun.c的run_tty_1(fp, filename)，主要执行如下：
   

   run_tty_1(fp, filename) {
   //gram <- graminit将已生成的Python语法规则放进gram，
   //其实不在这个函数里完成，为了理解的方便我就这样写在这里。     
   //根据语法gram以及输入文件fp生成语法树存放在n中     
   node* n = parsefile(fp, filename, &gram, single_input, ...)
   // 执行以n为根节点的语法树
   v = run_node(n, filename, ...) 
   }

给定以上的主要流程，我们来接触更加细节的部分。首先我们来看parsetok.c中的parsefile这个函数，它主要功能包括"

parsefile(fp,filename, g, ...) {
//初始化err_ret
//初始化一个tokenizer(词法分析器)tok
tok = tok_setupf(fp, ...);
return parsetok(tok, g, ...);
}

所以这个函数也相当简单，初始化一个词法分析器然后调用parsetok开始做词法分析。再来看parsetok:

parsetok(tok, g, ...) {
ps = newparser(g, start)
for (;;) {
    type = tok_get(tok, &a, &b);
    addtoken(ps, type, ...);
}
delparser(ps);
}

所以这里就是用一个for循环不停的调用tok_get抓取下一个token供语法分析使用。语法分析里的状态转移以及移进归约在addtoken中实现。

[Python]一个用ssh来远程登录多台机器并执行命令的脚本

功能类似于multissh。事实上我也抄了这个名字//grin。
要求安装了pexpect这个包先。
用法见usage:
Usage: ./multissh.py -f cmdfile -l username -c cmd -n nodesfile -v -r
execut cmd on remote hosts (all hosts in ./hosts.txt by default)
-v verbose
-r recording hosts on which mission succeeded and failed
-l username
-c cmd to be executed remotely
-n file containing the nodes
-f file conaining the cmd
-h show the usage
就是指定一个文件比如nodes.txt以及命令以后，它可以自动登录到nodes.txt包含的节点里执行命令。可以在源文件里替换进你自己的密码，也可以使用公钥密钥登录不需输入密码。指定了v选项的话得到在远端每台主机上的详细输出。指定了r选项的话记录下那些节点成功那些节点失败。
我前面的帖子里有关于ansi_color的一个脚本，拿过来可以配合使用得到彩色输出

使用前可能要根据情况修改prompt变量的定义. 这个变量是关于登录后提示符的正则表达.我根据我自己的几台机器随便写了两个.未必符合你的情况.

#!/usr/bin/python
import sys
import os
import getopt
import pexpect
import re
try:
    from ansi_color import *
except ImportError:
    def color_str(s, *args):
        return s
    fg_green = None
    fg_red = None
    fg_blue = None

prompt = "^.*\(.*\):|\[.*@.*\]|\$"
nl = open("/dev/null", "w")
    
def _print(s):
    if not single_mode:
        print s    

def do(cmds, hostname, username):
    global verbose, quiet, good_hosts
    #print "executing \"%s\""%(repr(cmds))
    ret = 0
    try:
        sshcmd = 'ssh %s'%(hostname)
        if username != None:
            sshcmd = sshcmd + " -l %s"%username
        s = pexpect.spawn(command=sshcmd, timeout=20)
        if verbose:
            s.logfile_read = sys.stdout
            s.setecho(False)
        else:
            s.logfile_read = s.logfile_send = nl 
            s.setecho(False)
        t = 0
        while t < 3:
            i = s.expect([prompt, pexpect.EOF, pexpect.TIMEOUT,\
                          "Are you sure you want to continue connecting (yes/no)?",\
                          "(P|p)assword:"])
            t += 1
            if i == 0:
                break
            elif i == 1:
                _print("End Of File")
                return 1
            elif i == 2:
                _print("time out")
                return 1
            elif i == 3:
                s.sendline("yes")
            elif i == 4:
                s.sendline(password)
        if t >= 3:
            return 1
        if cmds:
            for cmd in cmds:        
                s.sendline(cmd)
                s.expect(prompt)
        else:
            _print("\nEntering interactive mode, please ^] to escape")
            s.interact()
        s.sendline("exit")
        s.close()
        return 0
    except pexpect.ExceptionPexpect:
        return 1

def print_usage():
    print "Usage:\t ./multissh.py -f cmdfile -l username -c cmd -n nodesfile -v -r"
    print "execut cmd on remote hosts (all hosts in ./hosts.txt by default)"
    print "\t-v verbose"
    print "\t-r recording hosts on which mission succeeded and failed"
    print "\t-l username"
    print "\t-c cmd to be executed remotely"
    print "\t-n file containing the nodes"
    print "\t-f file conaining the cmd"
    print "\t-h show the usage"
    print "\t-p password"
    sys.exit(0)

if __name__ == "__main__":
    try:
        opts, args=getopt.getopt(sys.argv[1:], \
            "l:f:n:c:p:vhrq",["login_name", "cmdfile","nodesfile","command","password","verbose","help","recording","quiet"])
    except getopt.GetoptError, err:
        print str(err)
        print_usage()
    if opts == [] and args == []:
        print_usage()
    if args:
        hosts = [args[0]]
    else:
        hosts = []

    cmds = []
    verbose = False
    quiet = False
    username = None
    recording = False
    password = ""
    single_mode = True
    
    for o, ra in opts:
        a = ra.strip("\n")
        if o in ("-h", "--help"):
            print_usage()
        elif o in ("-n", "--nodesfile"):
            hosts = [l.strip(" \t\n") for l in open(a, 'r')]
            single_mode = False
        elif o in ("-c", "--command"):
            cmds = [a]
        elif o in ("-f", "--cmdfile"):
            cmds = [cmd.strip(' \n') for cmd in open(a, 'r')]
        elif o in ("-v",  "--verbose"):
            verbose = True
        elif o in ("-q", "--quiet"):
            quiet = True
        elif o in ("-r", "--recording"):
            recording = True
        elif o in ("-l", "--login_name"):
            username = a
        elif o in ("-p", "--password"):
            password = a

    if not hosts:
        _print("using default ./hosts.txt")
        h = open(os.path.join(os.path.expanduser("."), "hosts.txt"),'r')
        hosts = [dst.strip(' \n') for dst in h]
        
    if recording:
        f_good = open("good_hosts.txt","w")
        f_bad = open("bad_hosts.txt","w")

    good_hosts =[] 
    bad_hosts =[]
    
    for (i, hostname) in enumerate(hosts):
        _print ("%d/%d: ["%(i+1, len(hosts))+ color_str(hostname, fg_blue)+"]")
        ret = do(cmds, hostname, username)
        if verbose:
            print
        if ret == 1:
            bad_hosts.append(hostname)
            _print("["+color_str("Fail!", fg_red)+"]")
            if recording:
                print>>f_bad, hostname
                f_bad.flush()
        else:
            good_hosts.append(hostname) 
            _print ("["+color_str("OK!", fg_green)+"]")
            if recording:
                print>>f_good, hostname
                f_good.flush()
            

    _print ("%d hosts suceed!"%len(good_hosts))
    sys.exit(ret)

[Python]执行一个进程并监视是否超时

用到popen2 module当中的Popen3这个类。用法很简单，创建子进程并立即返回父进程。然后可以用poll()函数检查子进程是否已经结束(未结束的话返回值-1)。

import popen2
def _popen(cmd, timeout = 10, num_retry = 3, logfile = sys.stdout):
    i = 0
    is_timeout = False
    while i <= num_retry:
        print "%dth try"%i, cmd
        sys.stdout.flush()
        i += 1
        t0 = time()
        P = popen2.Popen3(cmd, True)
        prompt = False
        while time() < t0 + timeout and P.poll() == -1:
            sleep(0.1)
        sts = P.poll()
        if sts == -1:
            logfile.write(color_str("command [%s] timeout\n"%(cmd), fg_red))
            if i < num_retry:
                logfile.write(color_str("terminate and try again\n", fg_red))
            logfile.flush()
            is_timeout = True
            os.kill(P.pid, signal.SIGTERM)
        elif sts != 0:
            for l in P.childerr.readlines():
                logfile.write(l)
            if i < num_retry:
                logfile.write(color_str("try again\n", fg_red))
            logfile.flush()
            is_timeout = False
        else:
            is_timeout = False
            break
    logfile.write(color_str("return "+str(sts)+"\n", fg_red))
    sys.stdout.flush()
    if is_timeout:
        return (sts, open("/dev/null", "r"))
    else:
        return (sts, P.fromchild)

按说popen2这个module应该已经deprecated，被subprocess module所取代。不过subprocess.Popen的poll()函数似乎有bug，总是返回None。所以只好还用“古老”的module。

[Latex]MacOS上Latex几个IDE的比较

工欲善其事,必先利其器。因为要在macbook上用latex写paper，需要在几种latex编辑器的选择里找一种最舒服的。我先后尝试了如下的一些：

• TexShop。免费的一个编译环境。最大的优点就是免费。打开的文件一多的时候操作起来不方便，因为不能用标签选择文件，使用起来很不舒服。
• TextMate。是一个综合性的文本编辑器。界面漂亮，使用很友好。但是最大的问题是要钱
• BBEdit。也很不错的一个文本编辑器。但是要钱。TextWrangler是其免费版，但是功能受限制，不爽。
• Emacs+AUCTeX。还是这个好，免费，而且界面也可以搞的很漂亮。