Wednesday, July 21, 2010

git笔记

git是Linus亲自操刀设计实现的版本控制工具(据说Linus在两个礼拜内搞定了git,教主威武).git功能上比SVN要强,但是学习曲线也陡了很多. 这里是我对SVN的笔记


文档

关于git的教程和手册网上很多, 但很多写的都不好.最推荐:
Git Workflow (这里的diagram非常给力)
How to version projects with Git 图文并茂,有木有?
git quick reference

这几个也不错
Git Magic 中文,英文
Pro Git(中文)

其他的还有:
Understanding Git Conceptually
Git User Manual写的比较晦涩
Git - SVN Crash Course. 我觉得帮助不是很大, 因为git和svn在用法上区别是在太大了
GIT cheat sheet这个不错
Basic Branch Merging
关于stash, log, 以及gitconfig的用法

用法

初始化一个workspace
从远端克隆一个repository到本地
$git clone git://path/to/your/git/repo
注意git是一个分布式的版本控制系统. 如果你从server1上clone的repo, 那么以后server1就相当于你的源.如果以后server2再clone了你的repo, 你就相当于server2的源.我发现这种结构很方便调试 -- 在其他机器上可以从我本地repo来pull 文件. clone的时候除了git协议还可以使用ssh, 比如
$git clone ssh://hostname/path/to/your/git/repo

工作流程
进入你的工作目录,通常大家首先将本地repository更新到源上的最新版本(大致相当于svn update, 但是因为git是分布式的设计,更新到源上最新未必是全局最新). 下面的命令从origin 这个remote 更新 master这个branch的update.
$git pull origin master
未必需要从自己所在的branch来更新. 比如你实际在master这个branch, 你也可以更新branch foo的东西,即使你还是留在master这个branch里:
$git pull origin foo
有时候每次都是默认同样的remote同样的branch,那么我们可以修改工作目录下的.git/config文件,
[branch "master"]
    remote = origin
    merge = refs/heads/master
这样就可以直接用下面命令来更新而无须指定remote和branch
$git pull


做了修改后, 为了查看当前工作目录的状态,比如哪些文件被改动, 哪些文件没有commit, 可以使用status (大致相当于svn st)
$git status
如果需要git status的时候忽略某些文件,比如.o文件或者.pyc文件, 我们可以在.gitignore这个文件中加入两行*.o以及*.pyc.

修改了本地的文件后, 需要将其用add命令将其加入index. svn里没有index的概念,而且add这个命令在svn中是将一个文件加入版本控制. 而git里, 一个文件每次的修改都会需要你用add加入index后才能commit.
$git add file1 file2
然后将index的修改commit到本地.
$git commit file1 file2 -m "go! commit file1, file2"
以上两步(add, commit)也可以被合并成一步
$git commit -a file1 file2 -m "go! commit file1, file2"
如果需要更改上一次commit的信息
$git commit --amend -m "this is the right commit!"

这个时候文件只是在本地commit, 如果希望更新到远端的repositiory中, 还需要push(和更新源到本地的pull命令对应). 默认git push的话是push到origin的master分支
$git push
你也可以指定remote repo以及branch
$git push repo5 branch12
如果当前工作目录下checkout了多个branch, 但是你一般只会push正在tracking的这个branch,可以在config文件(比如.git/config)里设置
[push]
    default = tracking
或者使用命令
$git config push.default tracking

提取给定版本 checkout
checkout最新commit里的foo
$git checkout foo
如果需要提前两个版本的foo,可以
$git checkout HEAD~2 foo
从最新的stash(stash@{0})里checkout foo这个文件
$git checkout stash@{0} foo

撤销更改 revert, checkout, reset
比如你刚刚修改了一个文件foo, 但现在想撤销这个更改. 这需要根据foo的状态来选择不同的方法:
  • Changed but not updated: 如果一个文件foo被删除了, 或者被修改了但完全还在本地workspace中,还没有使用git add把foo加入index当中, 那么我们只需要重新checkout 这个文件
    $git checkout foo
    如果你不幸有一个branch也叫foo
    $git checkout -- foo
    如果你需要恢复当前目录所有文件
    $git checkout . 
    有时候需要把当前workspace中所有的修改都撤销,可以简单的使用:
    $git stash
  • Changes to be committed: 这时候修改已经加入index当中,但是还没有commit 提交到本地repo,我们可以使用reset使的当前workspace回到上一个commit的时候, 然后使用checkout恢复修改.
    $git reset HEAD foo
    $git checkout foo
    撤销所有index当中的修改:
    $git reset HEAD
  • 如果已经使用git commit把修改提交到了本地repo当中, 我们可以把本地repo rollback到上一次commit前的状态:
    $git reset --hard HEAD~1
    --hard选项会overwrite的所有的改动.

    如果我们只需要undo某一次的commit,可以使用git revert:
    $git revert b38155cbf671d55ceb027687c39508de8cef2463
    这样实际上是提交了另一个commit来抵消指定的commit.

查看日志 log
当前branch的commit日志
$git log
当前branch的commit日志,显示内容
$git log -p
当前branch的commit日志,但只显示上3次提交的内容
$git log -3
当前branch的commit日志,但只显示被修改的文件名
$git log --name-only

处理冲突 conflict
参考手册http://www.kernel.org/pub/software/scm/git/docs/user-manual.html
以及 http://www.kernel.org/pub/software/scm/git/docs/git-push.html

pull的时候如果有本地修改会导致无法成功. 如果希望能把远端的commit merge到本地
$git checkout -m foo
Auto-merging foo
有可能会失败,这时候就需要你手动来编辑这个文件来merge了

push的时候, 当前commit到远端repo的时候,有时候会出现如下问题:
$git push
To git@example.come:example.git
 ! [rejected]        master -> master (non-fast-forward)
error: failed to push some refs to 'git@example.com:example.git'
To prevent you from losing history, non-fast-forward updates were rejected
Merge the remote changes before pushing again.  See the 'Note about
fast-forwards' section of 'git push --help' for details.
这是由于你的工作目录没有update到最新的版本.换言之有人在你上一次pull之后又push了新的commit进去.所以如果你的push生效, 可能会导致别人push的commit失效. 解决方法有两种:
$git pull
$git push
这种方法先把当前工作目录更新到最新 -- 这一步可能会产生冲突. 解决冲突后把更新提交. 这种方法会产生两个commit信息. 一次是说你自己的更新,另一次是将你的分支和repo上分支的merge.
如果不希望产生两次commit信息, 可以用第二种方法:
$git pull --rebase
$git push
这种方法直接将你的commit重新rebase到最新的版本上, 然后再进行提交.

分支 branch
一个repo可以有不同的分支,branch命令查看本地已有的分支, *表示当前使用的branch
$git branch
* master
  testbranch
可以用branch -r 查看remote所有的分支
$git branch -r
也可以用branch -a 同时查看local和remote所有的分支
$git branch -a
以当前branch的HEAD为起始点,新建新的branch叫newbranch
$git branch newbranch
也可以指定起始点(比如testbranch), 创建一个新的分支叫newbranch
$git branch newbranch testbranch

将当前分支从master切换到testbranch
$git checkout testbranch
$git branch
  master
* testbranch

删除一个local的branch
$git branch -d branch_to_delete
删除一个remote的branch
$git branch push origin --delete branch_to_delete
远端 remote
查看当前branch有哪些remote
$git remote
origin
查看当前branch有哪些remote,显示具体一些的信息
$git remote -v
origin git@example.com:bar.git (fetch)
origin git@example.com:bar.git (push)

查看origin这个remote的具体信息
$git remote show origin
一个repo可以有多个remote.比如给分支branch_foo添加一个新的remote:
$git remote add branch_foo git@host-for-new-remote:repo-name.git
将新添加的remote添加为tracking的branch
$git branch --set-upstream branch_foo   remote_bar/branch_foo

查看历史版本
查看某个版本(some-sha1)的某个文件
$git show some-sha1-number:some-file
查看某个版本(some-sha1)的和最新版本(HEAD)之间的所有区别
$git diff some-sha1 HEAD
查看某个版本(some-sha1)的和最新版本(HEAD)之间的某个文件的区别
$git diff some-sha1 HEAD --somefile

比较当前branch和另外一个branch比如叫foo的区别
$git diff foo
比较branch foo和另外一个branch bar的区别
$git diff foo bar
查看远端repo里的文件
查看当前HEAD中所有加入git管理的个文件
$ git ls-tree -r  HEAD

其他相关工具
tig - text-mode interface for git 设置git ignore的方法: http://help.github.com/ignore-files/

Saturday, July 17, 2010

赶个时髦,学习一下Object-C

(未完)
由于iPhone等Mac系产品无比红火的存在,Object-C也变得重要起来。Object-C是Apple的御用语言(类似C#之于Microsoft)。如果要开发个iPhone App啥的,就需要用到Object-C。如果要在MacOS里写点基于Cocoa的应用程序,也需要用到Object-C(其实Cocoa有python等其他语言的绑定,不过我试了一下不太喜欢)。

话说当年水果教教主Steve Jobs被董事会一脚踢出了自己创立的Apple,就搞了一个Startup叫做NeXT。Object-C就是NeXT从别人手里买下的。Steve Jobs在NeXT待了十年,期间潜心研发硬件软件,修为大为精进。而Apple这段时间却止步不前,终于在1997年被Steve Jobs夺舍而复辟回到了Apple。Steve Jobs顺道也把在NeXT修炼的OpenStep操作系统(打包了Object-C,Cocoa和Xcode等)带回了Apple,也就是后来广为人知的MacOS X。在使用Object-C的时候会发现大量NS开头的类(NeXTstep的意思),就是在纪念这段历史。

Object-C从名字上来看顾名思义就是包括了面向对象的C。道友可能会问,C++不就是用面向对象版的加强的C么?对,但其实现在我们看到的C++是那轮改造中涌现出来的最流行的那个。Object-C和C++都说自己继承了C语言,是C的超集--当你用不到面向对象的时候确实是这样。但是用上面向对象以后,两者的语法就存在着不小的区别。Object-C的面象对象部分其实处处都流露出从更加上古时期就流传下来的Smalltalk的影子。为了以示区别,Object-C中对于C扩充的关键字多以@开头,比如@interface,@end等。

下面开始步入正题:
第一个Object-C程序:Hello World

像学习其他所有语言一样,我们也不能免俗的从Hello World开始。下面是Object-C版本的Hello World
#import <stdio.h>

int main( int argc, const char *argv[] ) {
    printf( "hello world\n" );
    return 0;
}
不难发现,Object-C的Hello World和C版本的基本一样,唯一区别在于把#include换成了#import。没错,谁让Object-C就是C的扩充呢。

面向对象:类的创建

在Object-C当中, 首先用@interface定义一个类的成员变量和成员函数,然后在@implement中实现成员函数
Object-CC++
//Foo.h
@interface Foo : NSObject 
{ 
@private:
    double x;
@protected:
    double y;
@public:
    double z;
} 
-(int) f:(int)x; 
-(float) g:(int)x :(int)y; 
@end
//Foo.h
class Foo 
{ 
private:
    double x;
protected:
    double y;
public:
    double z;
    int f(int x); 
    float g(int x, int y); 
};
//Foo.m
#import "Foo.h"
@implementation Foo 
-(int) f:(int)x {...} 
-(float) g:(int)x :(int)y {...} 
@end 
//Foo.cpp
#include "Foo.h"
int Foo::f(int x) {...} 
float Foo::g(int x, int y) {...}

调用类方法

Object-CC++
[myObj method]
[myObj method:para1:para2]
output=[myObj method:para1:para2]
[obj1 func1:[obj2 func2]]
myObj.method()
myObj.method(para1,para2)
output=myObj.method(para1,para2)
obj1.func1(obj2.func2())
在Object-C当中,类方法的调用并不是传统的C/C++方式。而是采取了贴近Smalltalk的设计--消息。

Instance Method vs Class Method
在Object-C中,类的方法分为Instance 和Class两种,定义的时候分别使用"-"以及"+". Class method在大多数其他语言比如C++以及Java中又叫静态方法(static method).
@interface MyClass : NSObject

+ (void)aClassMethod;
- (void)anInstanceMethod;

@end
调用的时候
[MyClass aClassMethod];

MyClass *object = [[MyClass alloc] init];
[object anInstanceMethod];

Duck Typing

同受Smalltalk影响,Object-C和Python一样可以归入Duck Typing:一个类的实例可以调用该类中定义都方法,也可以调用该类中并没有定义的方法。在C++中如果一个类foo没有定义方法bar,那么foo的实例是无论如何也不能调用bar的--编译就无法通过。但是在Object-C(以及Python)中却没有问题--至少在编译期没有问题,但在运行期会有异常.

参考

从C/C++语言到Objective-C语言
Learning Object-C

Thursday, July 08, 2010

[Linux]readline

使用gnuplot的时候, 使用backspace 或者del这样的键总是显示~这样的字符
rlwrap -a -c gnuplot

这有一篇Consistent BackSpace and Delete Configuration
没有来得及仔细看

Tuesday, July 06, 2010

Virtualbox


Guest OS Addition
启动虚拟OS以后, 在device的menu里找到安装Guest OS Addition
安装这个的好处是鼠标可以自由移动, Guest OS的分辨率也会调整的比较好

共享文件夹
Host OS: Mac OS X
Guest OS: Ubuntu 9.04
为了在Guest OS中访问Host的文件系统,我们需要把Host的目录mount上

mount -t vboxsf [-o OPTIONS] sharename mountpoint
e.g. mount -t vboxsf -o uid=500,gid=500 /path/in/host /mount/point/in/guest

Guest OS: Windows XP
在Guest的Windows系统中访问MacOS上的目录,是通过映射网络硬盘实现的
在windows的命令行中输入
net use x: \\vboxsvr\sharename
这里x是你在Windows系统中分配的网络硬盘盘符,而sharename则是你在虚拟机中设置的共享文件夹(不一定是路径)

[Linux]动态链接库相关命令

Linux下动态链接库的管理
ldconfig 管理系统中的动态链接库文件

ldconfig这个命令会在“特定的路径”下搜寻可以共享的动态链接库文件(在Linux底下格式为lib*.so*),进而创建出动态装入程序(ld.so)所需的连接和cache文件.这里"特定的路径"指/lib和/usr/lib这些默认路径以及动态库配置文件/etc/ld.so.conf内所列的目录以及文件.

如果刚刚安装了一个lib之后,相关文件仍然说找不到,可能是动态链接文件的cache没有更新.可以ldconfig把ld.so的cache更新一下:
ldconfig
只处理foo文件夹下的动态链接文件(前面描述的特定路径下就不处理了)
ldconfig -n foo
显示当前cache的动态链接文件
ldconfig -p

ldd
作用: 查看可执行文件需要的动态链接库
例子:
>ldd /bin/ls
 linux-vdso.so.1 =>  (0x00007fff549ff000)
 librt.so.1 => /lib/librt.so.1 (0x00007fd82409c000)
 libselinux.so.1 => /lib/libselinux.so.1 (0x00007fd823e7e000)
 libacl.so.1 => /lib/libacl.so.1 (0x00007fd823c75000)
 libc.so.6 => /lib/libc.so.6 (0x00007fd8238f2000)
 libpthread.so.0 => /lib/libpthread.so.0 (0x00007fd8236d5000)
 /lib64/ld-linux-x86-64.so.2 (0x00007fd8242c8000)
 libdl.so.2 => /lib/libdl.so.2 (0x00007fd8234d0000)
 libattr.so.1 => /lib/libattr.so.1 (0x00007fd8232cb000)


是否应该使用环境变量LD_LIBRARY_PATH?
答案是no.尽量不要设置这个变量.理由参见http://linuxmafia.com/faq/Admin/ld-lib-path.html


Mac下的动态链接
ldd对应otool

Ref
http://wiki.linuxquestions.org/wiki/Library
http://tldp.org/HOWTO/Program-Library-HOWTO/shared-libraries.html

[Latex]几招压缩Latex paper的页数

写paper的时候要压缩页数常常让人很痛苦.其实默认的Latex的paper尚有很大的空间,让你不动太多的内容改动就大大的压缩论文页数.下面我贡献常用的几招
调整Section title的font和spacing
\usepackage[medium,compact]{titlesec}
默认的section title啥的其实spacing相当大.所以别看这招简单, 但其实相当狠, 能省下来很大的空间.

对于Bibliography参考文献用小号字体
可以用 \small, 再小点用 \footnotesize, \scriptsize 也有人用. 不过\tiny就太小了,reviewer会有意见的.
\footnotesize
\bibliography{ref}
\bibliographystyle{abbrvnat}

标准的itemize环境里的indent吃掉了很多空间,可以用list环境来自定义左右间距等参数
\begin{list}{\labelitemi}{\leftmargin=1em}
  \setlength{\topmargin}{0pt}
  \setlength{\itemsep}{0em}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
\item blablabla
\item blablabla
\end{list}
在这里我们用\labelitemi (实心圆点)作为每个item开头的bullet.还可以用预定义好的\labelitemii (一个-)或者\quad (空白)甚至 $\star$这样的.
或者可以这样全局的来设置:
\usepackage{enumitem}
\setlist{itemsep=0pt,parsep=0pt}

调整Equation和前面文字的空间
公式和文字之间有时候会留下很大的间距,可以通过\vspace来压缩这个间距
Therefore,
\vspace*{-0.5\baselineskip}
\begin{eqnarray}
     A = B
\end{eqnarray}

Monday, June 28, 2010

[Linux]以安全模式启动firefox或是thunderbird

不小心装了有问题的add-on然后firefox或者thunderbird就启动不起来了?
/path/to/firefox/firefox -safe-mode
/path/to/thunderbird/thunderbird -safe-mode

卸载掉有问题的add-on之后就好了

Saturday, April 17, 2010

[Python]py2app:将python程序转换为Mac OS Application的工具

先安装py2app
安装完毕后会有一个叫py2applet的程序出现
接下来进入我们python程序的目录,比如我们的程序叫HelloWorld.py
第一步: 生成HelloWorld的setup.py
$ py2applet --make-setup HelloWorld.py
第二步: 生成HelloWorld.app的结构
$ python setup.py py2app -A

[Linux]cheeting sheet of sh, csh, bash

sh, csh, bash 比较

Statement sh tcsh bash
if-then-else
if [ expression ] 
then
    ...
else
    ...
fi
if (expression) then
    ...
else
    ...
endif
注:then必须和if同一行
if [ expression ]
then
    ...
else 
    ...
fi 
for-loop
for var in (list)
do
    ....
done
foreach var (list)
    ...
end
for var in [list]
do
    ...
done 
Loop in Bash: http://www.cyberciti.biz/faq/bash-for-loop/

Sh: http://www.freeos.com/guides/lsst/
Bash: http://tldp.org/LDP/abs/html/

Monday, March 29, 2010

[Linux/Mac]package/library管理工具

Ubuntu


很好的一个reference: Ubuntu Skills

安装软件
  • 从源安装是最方便最快捷的方式. 源的设置在/etc/apt/sources.list当中.
    如果知道需要安装的包的名称, 比如叫foo. 那么安装foo只需要
    apt-get install foo
    如果不知道确切名字,只知道大概是关于foo这个东西的, 可以通过下面的命令来搜索所有关于foo的包
    apt-cache search foo
    还有时候连包都不知道, 但是只知道需要某个文件比如叫foo.c,但不清楚应该装哪个包, 这时候可以先安装apt-file
    apt-get install apt-file
    然后用apt-file来帮你找可能是哪个包有这个文件
    apt-file search foo.c
  • 也可以下载deb文件来安装
    dpkg -i foo.deb


自动更新所有过时的package
apt-get update
卸载package foo
apt-get remove foo
彻底卸载package foo (连同配置文件一起删除)
apt-get remove --purge foo
自动卸载不需要的包
apt-get autoremove
查看某个包foo的详细信息
apt-cache show foo
查看repository中package foo的版本
apt-cache policy foo
添加某个源的key
apt-key add bar.asc

安装完之后, 通常用dpkg来管理包
查看package foo所安装的文件以及路径
dpkg -L foo
显示包的信息
dpkg -s packagename
显示包括指定文件的包
dpkg -S filename
显示指定包的状态
dpkg --get-selections packagename
配置某个包
dpkg --configure packagename
配置所有的包
dpkg --configure -a


MacOS中的home brew

https://github.com/mxcl/homebrew/wiki/The-brew-command
非常好用的MacOS下的包管理软件.强烈推荐.
一个brew的cheatsheet: http://cheat.errtheblog.com/s/brew/ 一个安装包时候常遇到的问题
$ sudo brew install ruby
Cowardly refusing to `sudo brew install'
这是by design. 我的解决方法是吧brew的onwer设成root
brew install foo
brew cleanup foo

如何为brew制作Formula:Formula Cookbook

MacOS中的port

关于port的使用MacPorts Guide
安装包foo
port install foo
删除包foo
port uninstall foo
查看包foo的相关信息
port info foo
查看所有过时的包
port outdated
更新所有过时的包
port upgrade outdated
查看已经安装的包
port installed
清除所有已安装包的临时文件
port clean --all installed
彻底删除旧的包
port -f uninstall inactive
删除inactive的包
port -u uninstall
port uninstall inactive
清理foo包的中间文件(比如损坏了)
port clean foo
安装foo这个包之前先将其deactivate
port deactivate foo
port activate foo
查看foo这个包都在本机安装了哪些文件
port contents foo
查看foo这个包都依赖哪些其他包
port deps foo
查看哪些包依赖foo
port dependents foo

Hadoop Related

参考文档

收集的一些关于Hadoop的链接
Official Docs
Hadoop Quick Start (Official)
Hadoop MapReduce Tutorial using Java
Hadoop MapReduce Tutorial using Streaming
Hadoop Command Line
Jobconf parameters
Hadoop API Doc (Java)

Cluster Setup
Job Configuration的选项和默认值(有点老, 0.15的, 不过大部分没变)
Other Tutorials
Cloud 9: 关于hadoop的介绍很好很具体.有一些关于具体的programming的指导.
Hadoop Really Quick Start
Cloud computing with Linux and Apache Hadoop
The Hadoop Distributed File System

Hadoop自带工具

大部分初学者可能的问题, 先看Hadoop FAQ

DistCp

bash$ hadoop distcp hdfs://nn1:8020/foo/src1 \ 
            hdfs://nn1:8020/foo/src2 \ 
            hdfs://nn2:8020/bar/dest 

bash$ hadoop distcp -f hdfs://nn1:8020/srclist \ 
            hdfs://nn2:8020/bar/foo 

用RandomTextWriter生成随机文本
hadoop jar ${HADOOP_HOME}/hadoop-*-examples.jar randomtextwriter\
  -D test.randomtextwrite.total_bytes=52428800 \
  -D test.randomtextwrite.bytes_per_map=5242880 \
  /data/rand-text
参数test.randomtextwrite.total_bytes指定总共有多少字节要写;参数test.randomtextwrite.bytes_per_map指定每个map写多少字节.

Sort
hadoop jar ${HADOOP_HOME}/hadoop-*-examples.jar sort \
  -outKey org.apache.hadoop.io.Text \
  -outValue org.apache.hadoop.io.Text \
   /data/rand-text /data/sorted-text

Grep
hadoop jar ${HADOOP_HOME_DIR}/hadoop-*-examples.jar grep \
  /data/rand-text /data/greped-text dfs[a-z.]+' 

参数tips

reducer需要内存超过默认的1024MB的话,可以通过参数调整:
-D mapred.job.reduce.memory.mb=2048

使用Java作Hadoop MapReduce的时候,如果用到其他第三方的jar文件,用-libjars 选项来include

可以用-file选项指定需要使用的脚本
-file=myscript.sh

使用Streaming的时候,每个map task最多只能处理一个输入文件. 因此如果输入包括100个文件,则至少需要100个map.如果设定的mapred.map.tasks数目小于100,Hadoop会自动调整为100.

压缩格式的输入
当输入是gz或者是bz2文件时,不需要做特殊的处理.
-D stream.recordreader.compression=gzip

压缩格式的输出
当希望输出是压缩格式(比如.gz文件)时, 可以加上下面的选项
-D mapred.output.compress=true \
-D mapred.output.compression.codec=org.apache.hadoop.io.compress.GzipCode

指定map以及reduce的数目
指定map数目
-D mapred.map.tasks=your_map_number
指定reduce数目
-D mapred.map.tasks=your_reduce_number
特别的,使用map only 的MapReduce job时,
-D mapred.reduce.tasks=0

使用identityMapper作为mapper或者reducer
-mapper org.apache.hadoop.mapred.lib.IdentityMapper
-reducer org.apache.hadoop.mapred.lib.IdentityReducer

Key,Value的划分
对于streaming job,需要将map的输出划分成key和value.默认的划分是第一个"\t"之前的是key,之后的是value.但是我们可以自定义分隔符,比如要用=作为分割:
-D stream.map.output.field.separator==
也可以指定第几个分隔符之前的作为key:
-D stream.num.map.output.key.fields=4

Primary, Secondary Key
Hadoop Mapreduce 默认根据key来分配reducer使得所有key一样的record都被同一个reducer处理.有时候我们希望每个record是这样的格式 (k1,k2,v), 然后所有k1(也就是primary key)一样的record被同一个reducer处理, 而这个reducer看见的所有k1的record按照k2来排序.这样的要求可以通过类似下面的代码来实现: 比如这里将map输出里每行的前2个field作为k1也就是partition参考, 而第3第4个field作为k2来排序
-partitioner org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner \
-D stream.num.map.output.key.fields=4 \
-D num.key.fields.for.partition=2


输出路径可以在命令行中用${mapred.output.dir}指定或者在程序中用JobConf.setOutputPath来指定

Friday, February 19, 2010

[Linux]Makefile速查

基本语法:
target: prerequisites
    command
target:规则生成的目标. 可以是最终的目标文件,也可以是中间文件,还可以是“伪目标”(比如all,clean)
prerequisites:生成规则目标所需要的文件名列表
command:生成规则目标所要执行的动作,可以是一行也可以多行.但每行必须以tab开头

一个Makefile就是由一个或多个规则构成.默认的情况下,make执行的是Makefile中的第一个规则.比如下面例子:
# 定义变量可以方便修改
objects = main.o utils.o
#默认最终生成目标:edit
edit : $(objects)
    cc -o edit $(objects)
#指给定.o目标所需要的.h文件,make自动使用.o文件同名的.c文件,并且使用cc编译
main.o : defs.h
utils.o : defs.h
#告诉make clean是一个伪目标而不是真实文件
.PHONY : clean
clean :
    rm edit $(objects)

内部宏:
$?:比目标的修改时间更晚的那些依赖模块表。
$@ :当前目标的全路径名。可用于用户定义的目标名的相关行中。
$<:比给定的目标文件时间标记更新的依赖文件名。
$* :去掉后缀的当前目标名。例如,若当前目标是pro.o,则$*表示pro。

通配符
HEADERS=$(wildcard ./*.h)

参考:
[1] GNU Make中文手册

Thursday, February 18, 2010

[数学]抽扑克

2n张牌,n张红n张黑.随机从这副牌里连续抽牌(抽出来后就不扔回去了),平均能够看见多少次连续两张红牌?如连续三张红牌,视为看见两次.平均能看见多少次前一张红牌后一张黑牌?

Sol: 先定义随机变量
I_{i}=\begin{cases} 1 & \textrm{ith,(i+1)th are both read}\\
0 & \textrm{otherwise}
\end{cases}
这样能看见的连续红牌次数X = I_1+I_2+...+I_(2n-1). 虽然I_i和I_j之间并不独立(比如你前n张都抽的是红牌,那么后n张只能是黑牌了),但是如果是对X求期望,就可以把各个I_i单独拎出来求期望,再对期望求和:
E[X] = E[I_1]+\cdots+E[I_{2n-1}]=(2n-1)\frac{n}{2n}\frac{n-1}{2n-1}=\frac{n-1}{2}
同理可以得到看见先红后黑的平均次数是 n/2

Saturday, February 06, 2010

[数学]关于扔硬币得到的序列

现在有一枚硬币, 每次以概率p得到正面(下面以H代表),概率q=1-p得到反面(以T代表).反复投掷这枚硬币并记录出现的结果序列, 比如 T H H T T T H H T H...这样的一个序列. 针对这个序列我们可以说,在时间4我们完成了一个pattern THHT, 在时间6我们完成pattern TTT, 时间9又重复出现了pattern THHT.

下面是一些直观上容易理解的以及费解的:)结论: 

  1. 一个长度为k的给定pattern,在t时刻出现的概率为 p^i q^(k-i).这里i是pattern中T出现的次数. 这个很好理解.比如TTT在任意时刻出现的概率是p^3,  THHT是p^2 q^2, HTHT也是p^2 q^2
  2. 同一个pattern, 两次出现的时间间隔的期望是 1/[p^i q^(k-i)]. 这个结果也很直观. 可以根据Delayed Renewal Process得到. 所以THHT出现间隔是1/(p^2 q^2),HTHT出现间隔也是1/(p^2 q^2)
  3. 一个pattern, 从第一次扔硬币开始到第一次出现的时间期望

    E[time until HTHT] =  E[time until HT] + E[time between HTHT] = E[time between HT] + E[time between HTHT] = 1/(pq) + 1/(p^2 q^2)

    这里的一个trick是把pattern HT和HTHT之间的时间间隔等同于出现pattern HTHT 的间隔. 仔细想一下的话, 出现一次HTHT后这个pattern对下一次出现HTHT的贡献(或者影响)就是它的尾巴HT了. 同理我们还有

    E[time until THHT] =  E[time until T] + E[time between THHT] = E[time between T] + E[time between THHT] = 1/p + 1/(p^2 q^2)

    所以从第一次投硬币开始观察的话,  HTHT和THHT第一次出现的平均时间是不同的.
    同样我们也可以得到连续k个T出现的平均时间, 注意每一次连续出现i个T都对i+1个T有贡献

    E[time until k consecutive T] = 1/p + 1/p^2 + ... + 1/p^k

这个问题还有一个利用Martingale的方法来算,而且是Bob Li提出来的(A martingale approach to the study of occurrence of sequence
patterns in repeated experiments, Annals of Probability, 1980).比如我们要求E[time until HTHT].设在第i轮,一个赌徒下注1块钱.如果第i轮结果是H,赌徒就赢得1/p块钱,接下来第i+1轮结果是T,赌徒就赢得1/(pq)块钱,以此类推.不过如果一旦没有压准,所有钱就输了.请注意这是一个公平赌博.如果每一轮都有一个赌徒来下注.设Xn为第n轮下来赌场的收入:
Xn=(n-4) - [1/(p^2 q^2) -1] + 1 - [1/(pq) -1 ] + 1

因为Xn是Martingale,所以 0 = E[Xn] = (E[n]-4) - [1/(p^2 q^2) -1] + 1 - [1/(pq) -1 ] + 1
也就得出E[n] = 1/(pq) + 1/(p^2 q^2)

Monday, February 01, 2010

[数学]比较k个随机数加权后的大小

如果有k个随机变量x_1..x_k独立同分布于U[0,1],每个随机变量对应一个非负权重a_1...a_k.
那么加权后第一个随机变量比其他随机变量加权后都大的概率(i.e., a_1x_1>= a_ix_i for all i):

Sol:
如果给定x_1=x, a_1x_1比a_ix_i大的概率为min(a_1x_1/a_k,1)

\int_{0}^1\min(\frac{a_1x}{a_2},1)\cdots \min(\frac{a_1x}{a_k},1) d x

Tuesday, January 19, 2010

[数学]关于Coupon Collector的问题

原题在这里.简单的说,市面上有一种coupon有n个样式.每一个你新收集的coupon以1/n的概率为其中任意一种.如果说你需要收集T个coupon你才能把所有的样式都拿到,那么T的均值是多少呢?

假设我们手里已经有了i-1种不同的coupon.那么在收集了i-1种不同coupon后,出现一个新式的coupon所需要的尝试次数服从参数为pi的几何分布.pi=(n-i+1)/n 也就是出现第i种新coupon的概率.
E[T]=1/p_1+1/p_2+\cdots+1/p_n =  \frac{n}{n}+\frac{n}{n-1}+\cdots+\frac{n}{n} = n H_n\approx n \ln n


该问题的一个变种是:求当我们收集齐了所有n种coupon,其中某个样式(比如印着机器猫的)coupon只拿到了一张的概率.

该珍贵的coupon,可以是第1种收集到的,也可以是第j种收集到的.j服从1,...,n,的均匀分布.如果它是第j种收集到的coupon,则后面不出现该coupon的概率是 1/(n-j+1). 所以全概率是:
\sum_{j=1}^n \frac{1}{n}\frac{1}{n-j+1}= \frac{H_n}{n}\approx \frac{\ln n}{n}

Sunday, January 17, 2010

[Emacs]我总结的Emacs Cheating Sheet

这有一个不错的pdf版本cheat Sheet:Emacs Cheat Sheet

C代表Ctrl键, M代表Meta键, ←和→是右箭头和左箭头
基本操作
这里总结的是基本操作,大多数mode下都可以用
在文本中移动
C-f, C-b 向前(C-f)或是向后(C-b)移动到下一个字符.
M-f, M-b 向前(M-f)或是向后(M-b)移动到下一个单词.
C-M-f, C-M-b 在一对匹配的括号间,向前(C-M-f)或是向后(C-M-b)跳转.
C-a,C-e 移到当前行首(C-a)或者行尾(C-e).
M-a, M-e 向前(M-a)或是向后(M-e)移动到下一个句子.
C-x C-space 跳转到上一个mark的地方
C-v,M-v 向前(C-v)或是向后(M-v)翻页
M-<, M-> 移动到buffer首/尾
M-m 移动到第一个非空格字符。(back-to-indentation)
M-r 加参数,移动到窗口里的某一行。不加参数缺省移动到窗口中间。
M-x goto-char 到文件的第 N 字节。
M-x goto-line 到文件第 N 行。
C-x C-n 设定 goal-column.
C-u C-x C-n 取消 goal-column.
M-g g 移动到指定行

编辑文本
C-o 当前位置插入一行
M-Delback,M-d 以word为单位的前删/后删
C-d 删除后面一个字符且不放入kill-ring
C-M-k 向前删除直到匹配括号
Esc-C-Del,Esc-C-Backspace: 先后删除到匹配括号
M-z : 删除到下一个出现的位置

大小写转换
从光标位置开始,处理单词后半部分
capitalize-word (M-c) -- 首字母改为大写
upcase-word (M-u) -- 全部改为大写
downcase-word (M-l) -- 全部改为小写
从光标位置开始,处理单词前半部分
negtive-argument; capitalize-word (M-- M-c)
negtive-argument; upcase-word (M-- M-u)
negtive-argument; downcase-word (M-- M-l)
改变选定区域的大小写 downcase-region (C-x C-l) -- 选定区域全部改为小写
upcase-region (C-x C-u) -- 选定区域全部改为大写


设定Marker
C-空格,C-@ 设定一个mark
C-x h 整个缓冲区全部mark

对齐 (http://www.emacswiki.org/emacs/AlignCommands#toc2)
M-x align 对齐当前选择
M-x align-current 对齐当前section
M-q fill-paragraph 对一个段落排版

获取帮助
C-h c 简要描述给定键绑定
C-h k 详细描述给定键帮定
C-h f 描述给定函数
C-h v 描述给定变量
C-h m 描述当前mode
键/键组合 C-h 以当前键/键组合开头的绑定
M-x `finder-commentary' RET foo RET.

查找
C-s 向前方查找
C-r 向后方查找

注释
M-; 注释一个区域或者去掉区域的注释 (需要开启transient-mark-mode以后)

操作矩形
首先Set Marker然后移动光标围成一个矩形区域
C-x r k 删除矩形区域
C-x r t 矩形区域中插入文本

切换不同窗口
C-x 0 删除当前窗口(注意是零不是o)
C-x o 把光标在屏幕上的窗口间进行切换。记忆方法:其它(other)窗口。
C-x 1 把当前光标所在的窗口放到最大,隐藏其它所有的窗口。记忆方法:只剩一(1)个。
C-x 2 水平切分屏幕
C-x 3 竖直切分
C-x w r 1 存储当前窗口layout到寄存器1(可以为其他数字)
C-x j r 1 读取寄存器1(可以为其他数字)中的窗口layout

切换不同buffer
C-x b 缓冲区名称. emacs会提供一个缺省的缓冲区,一般是上一个用到的.如果不行,手动输入缓冲区名称,支持和自动补全.
C-x C-b 列出缓冲区菜单. 但这个命令不会将光标移动到缓冲区菜单的窗口中,需要C-x o命令切换过去.
C-x →,C-x ←. 循环切换到前一个(后一个)缓冲区
C-x k 杀死一个缓冲区(默认是当前缓冲区)
C-x C-s 保存当前缓冲区

切换不同frame
C-x 5 0 切换frame

在Emacs中使用Shell buffer
M-x ansi-term 带有色彩支持的term
M-x shell 系统默认shell
M-x eshell emacs自带shell

参数
M-<数字> : 执行 <数字>这么多次
C-u <数字> : 同上



常用Mode下的操作
AucTex LaTeX mode
C-c C-b 编译buffer / 预览编译结果
C-c C-r 编译选定的region
C-c C-c 运行定义好的命令比如 latex, view, bibtex
C-c C-v 查看当前的output file
C-c C-e 添加指定的环境
C-u C-c C-e 替换当前的环境
C-c ] 添加\end{...} 来匹配当前环境
C-c ; 注释选定区域,再操作一次就是去除选定区域的注释

CC mode
子模式:
auto-state 当你输入时自动缩进,自动换行
hungry-state 当你Backspace时,自动删除尽可能多的空白和空行
C-c C-t 同时转换(开/关)auto-state和hungry-state子模式
C-c C-a 转换 auto-state 子模式
C-c C-d 转换 hungry-state 子模式

M-/ 自动补齐(缓冲区中能找得到的串)
M-; 行尾加入注释
C-c C-e 扩展宏
C-c C-c 注释掉整个区域
C-c C-\ 将区域中的每一行结尾都加入一个'\'字符

cc-mode下的缩进
C-c . 设置缩进风格(按TAB键可列出可用的风格,缺省的为gnu,其 缩进为2个字符;linux为8个;k&r为5个…)
C-c C-q 缩进当前函数
C-M-q 缩进当前表达式
tab 缩进当前行
C-x h C-M-\ 缩进当前buffer
C-M-u C-M-q 缩进当前block

Lisp mode (http://www.delorie.com/gnu/docs/emacs/emacs_329.html)
C-: 执行一行lisp
C-x C-e 执行光标前的lisp

VC (version control) mode(http://lifegoo.pluskid.org/wiki/EmacsVC.html ,http://lifegoo.pluskid.org/wiki/EmacsVC.html , http://www.credmp.org/?p=65)
C-x v i 添加当前buffer的文件到version control当中
C-x v v 下一个合理的version control 动作(通常在一个状态下只有一个合理动作)
C-x v m 更新当前文件
C-x v + 更新当前文件集合
C-x v d 显示一个目录下所有注册到版本控制下的文件
C-x v l 查看log
C-x v = 和repository上代码作比较
C-x v ~ 查看以前版本

org mode (官方手册 , 中文教程)
Org mode是Emacs上一个用于组织信息,管理信息,撰写大纲的利器.可以帮助你非常快速的组织思路,查找信息.
C-c C-t Rotate the TODO state of the current item among
C-Shit-Enter 新建一个TODO 项目
Shit+Tab 切换view
链接:
[[链接地址][链接名称]]比如 [[http://www.gnu.org/software/emacs/][GNU Emacs]]
或者 [[链接地址]]如果你不需要名称


Cscope Mode
C-c s a 设定初始化的目录,一般是你代码的根目录
C-c s I 对目录中的相关文件建立列表并进行索引
C-c s s 序找符号
C-c s g 寻找全局的定义
C-c s c 看看指定函数被哪些函数所调用
C-c s C 看看指定函数调用了哪些函数
C-c s e 寻找正则表达式
C-c s f 寻找文件
C-c s i 看看指定的文件被哪些文件include

Dired mode (http://jamesthornton.com/emacs/node/emacs_396.html#SEC396 , http://www.20seven.org/journal/2008/11/emacs-dired-directory-management.html)
Dired mode用于文件管理
C-x d/M-x dired 进入Dired模式
C copy
D delete
# 标记所有atusave文件
R rename
s sort

iBuffer mode (http://www.emacswiki.org/emacs/IbufferMode)
和Dired mode相仿,但是用于buffer管理
M-x ibuffer 进入ibuffer模式
m 选定当前位置buffer
u 去除选定当前位置buffer
t 改变buffer list里每个buffer的选定状态
D 删除当前选定的buffer(们)
g 刷新
% n 选定所有那些buffer名称符合给定正则表达式的
% m 选定所有那些mode名符合给定正则表达式的
% f 选定所有那些文件名符合给定正则表达式的

GDB
M-x compile RET 编译
M-x gdb RET 调试
gdb --annotate=3 a.out 或者 gdb -i=mi a.out
C-x ` (出错信息中)下一个错误,一个窗口显示错误信息,另一个显示源码的出错位置
C-c C-c 转到出错位置

启动gdb调试器后,光标在源码文件缓冲区中时:
C-x SPC 在当前行设置断点
C-x C-a C-s step
C-x C-a C-n next
C-x C-a C-t tbreak
C-x C-a C-r continue

其他一些七七八八的

设置AucTex中的viewer. AUCTeX以前是通过设置TeX-output-view-style和TeX-view-style来决定如何根据output文件的后缀来用不同的viewer打开output文件. 新的实现是通过设置TeX-view-program-list和TeX-view-program-selection两个变量来实现:
比如把pdf和dvi文件关联到Evince.
(setq TeX-view-program-list '(("Evince" "/usr/bin/evince --page-index=%(outpage) %o")) )
(setq TeX-view-program-selection '((output-pdf "Evince") (output-dvi "Evince")) )

--could be out of date---
改变AUCTeX默认pdf viewer:
"Customize group - Auctex - Tex Command" entry for the "^pdf" extension in
"Tex Output View Style" => "evince %o"

重要变量
major-mode: 当前mode

载入.emacs文件
M-x load-file RET ~/.emacs RET Reload .emacs without restarting

check the value of your load-path by asking for help on the variable: ‘C-h v load-path RET’

By default Emacs doesn’t include subdirectories of a directory which is added to load-path. But you can do it by issuing a command in startup file:

(normal-top-level-add-subdirs-to-load-path)

Recover Data
M-x recover-file <ret> foo.c <ret>
yes <ret>
C-x C-s

查看package路径
M-x locate-library

在eclipse当中绑定emacs键位设定
Window->Preferences->General->Keys Scheme中选emacs

强制使用某种mode 比如xxx-mode
M-x xxx-mode

刷新当前文件
M-x revert-buffer
刷新所有已经打开的文件
M-x revert-all-buffers

去除所有结尾的whitespace
M-x delete-trailing-whitespace

绑定key http://www.xemacs.org/Links/tutorials_2.html http://www.gnu.org/s/emacs/manual/html_node/elisp/Key-Binding-Commands.html
(global-set-key (kbd "C-x C-\\") 'next-line)

显示行号(类似vi中的 :set nu)
(global-linum-mode t)

如果希望emacs帮你自动wrap line,
M-x auto-fill-mode

判断当前系统
(if (eq system-type 'windows-nt) do-what-you-like)
如果是MacOSX, 把'windows-nt换成'darwin

C-\ 切换 "拼符"输入法

Friday, December 25, 2009

[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定义的网段的访问许可设为允许

Thursday, December 24, 2009

[数学]停车问题

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

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算法是该题另一种解法,事实上它的实用性更广.

Thursday, October 22, 2009

[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"
      }
   }

Wednesday, October 21, 2009

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

问题:(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

Saturday, October 17, 2009

[数学]阿里巴巴开门

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

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)

Thursday, October 15, 2009

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

问题:(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}

Sunday, October 11, 2009

[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

Saturday, October 10, 2009

[数学]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

Saturday, September 19, 2009

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

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:

Thursday, August 20, 2009

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

Wednesday, August 12, 2009

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
  2. 如果你使用的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,可以照着选自己需要的样式

    Tuesday, July 21, 2009

    [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

    Friday, July 10, 2009

    [数学]三个囚徒的问题

    从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 杀CCx  
    杀A 放B 杀C Cxx
    杀A 放B 杀CCxx
    杀A 杀B 放CB  
    杀A 杀B 放CB  

    Thursday, July 09, 2009

    [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.

    Tuesday, June 16, 2009

    [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 远远大于,远远小于

    Thursday, June 11, 2009

    [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\Fontssimsun.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

    Tuesday, June 09, 2009

    [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按照这里说的更改以后就好啦!

    Thursday, June 04, 2009

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

    Friday, May 22, 2009

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

    硬币不知道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

    Thursday, May 21, 2009

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

    Thursday, May 14, 2009

    [数学]一道小学应用题

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

    “一辆大客车和大货车分别从甲乙两地出发,经过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 (公里)

    Wednesday, May 13, 2009

    [算法]拳皇友谊赛

    这两天看到的一道蛮好玩的题:
    变态的比赛规则:为了促进各部门员工的交流,百度(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}

    Friday, May 08, 2009

    [算法]找树的重心

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

    给一个有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成立--所有子树的权重都小于所有节点权重和的一半。为了找到满足这个条件的节点 用贪心就足够了。随便从一个节点开始,看到哪个子树的权重和超过所有节点权重和一半,就往那个子树移动。直到不能移动位置为止。

    Thursday, May 07, 2009

    [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(键松开)的修饰,不然不行, 不知道为什么。

    Tuesday, April 28, 2009

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

    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.

    Wednesday, April 15, 2009

    [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

    Sunday, April 12, 2009

    [Python] Yaml与Json

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

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

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

    Saturday, April 11, 2009

    [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

    Saturday, March 28, 2009

    [算法]几个有趣的关于数列的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。

    Wednesday, March 11, 2009

    [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就很好了。