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