Monday, November 30, 2009

[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里面也恢复了输入中文的功能.

Thursday, November 19, 2009

[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);
});


参考

Wednesday, November 18, 2009

[数学]挑西瓜 (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算法是该题另一种解法,事实上它的实用性更广.