Approximate String Matching 模糊匹配
Arbitrary Precision Arithmetic 高精度计算
Bandwidth Reduction 带宽压缩
Bin Packing 装箱问题
Calendrical Calculations 日期
Clique 最大团
Combinatorial Problems 组合问题
Computational Geometry 计算几何
Connected Components 连通分支
Constrained and Unconstrained Optimization 最值问题
Convex Hull 凸包
Cryptography 密码
Data Structures 基本数据结构
Determinants and Permanents 行列式
Dictionaries 字典
Discrete Fourier Transform 离散Fourier变换
Drawing Graphs Nicely 图的描绘
Drawing Trees 树的描绘
Edge and Vertex Connectivity 割边/割点
Edge Coloring 边染色
Eulerian Cycle / Chinese Postman Euler回路/中国邮路
Factoring and Primality Testing 因子分解/质数判定
Feedback Edge/Vertex Set 最大无环子图
Finite State Machine Minimization 有穷自动机简化
Generating Graphs 图的生成
Generating Partitions 划分生成
Generating Permutations 排列生成
Generating Subsets 子集生成
Graph Data Structures 图
Graph Isomorphism 同构
Graph Partition 图的划分
Graph Problems ― hard 图论-NP问题
Graph Problems ― polynomial 图论-多项式算法
Hamiltonian Cycle Hamilton回路
Independent Set 独立集
Intersection Detection 碰撞测试
Job Scheduling 工程安排
Kd-Trees 线段树
Knapsack Problem 背包问题
Linear Programming 线性规划
Longest Common Substring 最长公共子串
Maintaining Line Arrangements 平面分割
Matching 匹配
Matrix Multiplication 矩阵乘法
Medial-Axis Transformation 中轴变换
Median and Selection 中位数
Minimum Spanning Tree 最小生成树
Minkowski Sum Minkowski和
Motion Planning 运动规划
Nearest Neighbor Search 最近点对查询
Network Flow 网络流
Numerical Problems 数值问题
Planarity Detection and Embedding 平面性检测和嵌入
Point Location 位置查询
Polygon Partitioning 多边形分割
Priority Queues 优先队列
Random Number Generation 随机数生成
Range Search 范围查询
rate of convergence 收敛速度
robustness 鲁棒性
Satisfiability 可满足性
Searching 查找
Set and String Problems 集合与串的问题
Set Cover 集合覆盖
Set Data Structures 集合
Set Packing 集合配置
Shape Similarity 相似多边形
Shortest Common Superstring 最短公共父串
Shortest Path 最短路径
Simplifying Polygons 多边形化简
Solving Linear Equations 线性方程组
Sorting 排序
Steiner Tree Steiner树
String Matching 模式匹配
Text Compression 压缩
Topological Sorting 拓扑排序
Transitive Closure and Reduction 传递闭包
Traveling Salesman Problem 旅行商问题
Triangulation 三角剖分
Vertex Coloring 点染色
Vertex Cover 点覆盖
Voronoi Diagrams Voronoi图
Tuesday, October 30, 2007
[zz]OJ不完全统计
http://sqybi.blog.hexun.com/12668571_d.html
今天看到了一个OJ的介绍,但比较不详细.那我就来写一个...更不详细的吧...
以下所有说法如无特别说明均属于个人见解,仅供参考!!!
首先是国内比较老牌的知名OJ:
PKU/POJ(Peking University Judge Online For ACM/ICPC)
地址:
http://acm.pku.cn/JudgeOnline
介绍:
北 京大学的题库,我主要在做的一个.题目数量很多,OJ的各项功能也很完善,而且还提供免费的OJ系统下载,可以利用提供的系统自己搭建OJ.题目数量很 多,有几千道,但水题也很多.关于这一点,因为题目数量大,所以水题自然就多,但这不说明PKU的题目质量不高.PKU的难题还是不少的,而且做不做水题 还是要由做题人自己决定的,和OJ无关.
推荐程度(最高10):
8
推荐做法:
如果是初学者或者仅仅想提高变成准确性,那么按照AC率做,保证1Y率;如果是有一定水平的OIer,可以每页完成40~50题;如果是大牛,那么尽量做吧;如果想专门训练某个项目,可以去网上搜pku题目分类,个人觉得pku里的dp题和数学题比较多.
ZJU/ZOJ(Zhejiang University Online Judge)
地址:
http://acm.zju.edu.cn/
介绍:
浙江大学的题库,国内起步最早的几个OJ之一.题目数量也接近2000.我没有太多的做zju的题目,所以不好说题目质量如何.OJ系统的友好性不如pku,但功能并不差.应该可以作为pku的替代品.
推荐程度:
7
推荐做法:
无(可以参考pku做法)
然后是一些不太知名的或比较新的:
Vijos(Velocious Informatics Judge Online System)
地址:
http://www.vijos.cn/
介绍:
说到现在的OJ,就不得不提Vijos.Vijos是Vivian Snow(就是湖南师大附中的刘康,个人主页是http://www.viviansnow.cn/ , 现在似乎上不去了=.=)搞的一个Judge系统,本来是作为创新大赛作品的,后来就搞起来了,现在人气很旺.但是Vijos的各种事情很多,而且服务器 不稳定,速度慢不说还时不时的关闭.关于Vijos的事情大家可以参考Dragon.Dai在Vijos的1周岁时候写下的这篇<Vijos的过 去,现在和将来>(http://www.mybloop.com/get/376674/Vijos.doc),这里不再赘述.Vijos上所有人都可以上传自己的题目,虽然增加了很多灵活性,但由此导致的是题目水平参差不齐.而且上传题目的人在选择题目难度的时候很难做出同样的判断,都有自己的个人见解,所以本来题目难度是很好的一个设计,现在却成了鸡肋.
推荐程度:
5
推荐做法:
用来测试竞赛原题,另外可以做一做AC率较低的题目.不推荐做大量的Vijos题目(yours牛别打我...).
TJU/TOJ(Tianjin University Online Judge)
地址:
http://acm.tju.edu.cn/toj
介绍:
可能大家都以为是同济的题库了吧=.=,其实这个是天津大学的,因为笔者是天津人,所以对这个OJ有独特的感情...虽然没怎么做过.总体来说比zoj稍差,题目质量不确定(我说了我没怎么做过...),一般我都用来做Contests.
推荐程度:
5
推荐做法:
无,可以做做Contests.注意是Online Contests而不是Virtual Contests,Virtual那个...打开就能知道,是利用TOJ自己的题库出Contests...其实这个设计很新颖,所有人都可以出测试.适合队内搞测验...
NKOJ(Nankai Online Judge)
地址:
http://acm.nankai.edu.cn/
介绍:
这 个是天津市南开大学的OJ,想必大多数人都不知道吧?在看下面的介绍之前,你可以先上去看看,体会一下.你一定会发现,通过大量Ajax技术的应用,加上 清新的界面,你会感到十分舒适.而且nkoj似乎有一个功能是自己不出现在Rank List和Status里面,这个功能很贴心.题目是nkoj最大的弱点,数量不大,质量一般.不过因为是中英文题目夹杂且中文题目数量不少(和pku 比),所以想做中文题的除了Vijos也可以来这里看看.其实nkoj比vijos要漂亮的多,速度比vijos稍快,稳定性...应该比vijos好不 少吧.
推荐程度:
5
推荐做法:
做中文题.
rqnoj(RenQingNet Online Judge,任青网络信息学奥赛(OI)在线判题系统)
地址:
http://www.rqnoj.cn/
介绍:
一个新兴的OJ,题目质量一般,数量也不多.除了去刷Rank,没有什么值得做的.
推荐程度:
2
推荐做法:
无.
接下来说一下国外的OJ:
SGU(Saratov State University Online Contester)
地址:
http://acm.sgu.ru/
介绍:
sgu 是俄罗斯斯坦福州立大学(大概是这个名字)的OJ,很老牌了.题目数量很少,但题题精炼,每做一道题都会让你的编程水平上升.在有一定编程水平之后可以试 着做做,要争取做出每一道题.如果sgu能全部AC的话...那这个人不是抄袭就是神牛...注意status需要通过左边的"status online"链接来看,而且sgu速度稍慢并且不太稳定.总之是非常特别以及及其应该推荐的OJ.
推荐程度:
9
推荐做法:
AC每一道题,可以按照AC Rate来做.
Ural(Timus Online Judge)
地址:
http://acm.timus.ru/
介绍:
Ural是Ural State University的一个OJ,题目不是很多,但都是原创,而且比较经典.如果sgu做着费劲,那么试试Ural吧.
推荐程度:
8
推荐做法:
试着做做每一道题吧,可以按照AC Rate来.
其它几个OJ:
HIT(Harbin Institute of Technology) http://acm.hit.edu.cn/
JLU(JiLin University Online Judge System) 教育网http://acm.jlu.edu.cn/joj 网通 http://202.98.18.36/joj
UVa(全名是啥...) http://acm.uva.es/problemset/
SPOJ(Sphere Online Judge) http://www.spoj.pl/
欢迎大家在下面回复告诉我更多的OJ,我会及时添加.
关于UVa和SPOJ的简介,请见http://hi.baidu.com/wfhhzyh/blog/item/328573597931d3292834f0ab.html.
欢迎转载,转载请注明出处(http://hexun.com/sqybi).最好能TrackBack一下.
SPOJ的确牛
最近面试老是被考到算法和数据结构题，郁闷透顶，开始后悔当年没有一心一意搞信息学竞赛 /_\
没办法，现在开始也不迟，况且算法这东西是一生受用的，的确太弱小了。
无聊中逛到了SPOJ，之前我就注册过帐号了，但当时没时间，现在忍不住上去看了一下，发觉还真强大。
几乎支持所有流行与非流行的语言，还有一些特殊的为了证明某种用途的语言（如brainf**k和whitespace,这两种语言真TMD变态阿……）
随便用C++做了第一题 TEST,把标准输入的数字搬到标准输出,遇到42就停止.提交后才发觉竟然要用时0.1sec,内存大小要2M多...
是不是说明了数据强呢......后来想了想,可以从
1.自己包装输入(因为题目明说了每个数字最多只有两位数字)
2.用位运算(判断是否为42时快很多)
来提高速度,简单题就给了自己这么多启发.
这里还有神牛关于用brainf**k解SPOJ测试题的文章,哈哈.
--
Best wishes,
Yours, iveney
Department, of Computer Science,
Zhongshan University (Sun Yat-sen University),
Guangzhou, China
没办法，现在开始也不迟，况且算法这东西是一生受用的，的确太弱小了。
无聊中逛到了SPOJ，之前我就注册过帐号了，但当时没时间，现在忍不住上去看了一下，发觉还真强大。
几乎支持所有流行与非流行的语言，还有一些特殊的为了证明某种用途的语言（如brainf**k和whitespace,这两种语言真TMD变态阿……）
随便用C++做了第一题 TEST,把标准输入的数字搬到标准输出,遇到42就停止.提交后才发觉竟然要用时0.1sec,内存大小要2M多...
是不是说明了数据强呢......后来想了想,可以从
1.自己包装输入(因为题目明说了每个数字最多只有两位数字)
2.用位运算(判断是否为42时快很多)
来提高速度,简单题就给了自己这么多启发.
这里还有神牛关于用brainf**k解SPOJ测试题的文章,哈哈.
--
Best wishes,
Yours, iveney
Department, of Computer Science,
Zhongshan University (Sun Yat-sen University),
Guangzhou, China
Wednesday, October 24, 2007
Tuesday, October 23, 2007
Google 黑板报 -- Google 中国的博客网志: 让千台服务器“共舞” - 使用 Google 工具栏进行发送
Google 黑板报 -- Google 中国的博客网志: 让千台服务器"共舞"
产品与使用技巧Tuesday, October 16, 2007
用MetaPost+LaTeX生成pdf文件
之前使用了TeX来做简历，觉得还不错。逛王垠主页时碰到MetaPost，觉得以后可能会用到，于是尝试了一下，发觉要做如下配置会比较方便，谨记录以备忘。
所有版权，归王垠所有 :)
王垠对MetaPost的介绍：http://learn.tsinghua.edu.cn:8080/2001315450/metapost.html
1.生成流程
1)使用编辑器编辑mp文件和tex文件
2)使用mpost filename.mp生成filename.1文件(eps格式)
3)在tex中使用包graphicx，即
\usepackage{graphicx}
使用\includegraphics{filename.1}来插入图形。
4)生成pdf文件
这里我有个为解决问题，就是使用pdflatex时会提示\includegraphics不能被识别，但是改用如下步骤做却没错：
latex test.tex
dvips test.dvi -o test.ps
ps2pdf test.ps
为了方便，不妨写个make脚本或bash脚本来完成从mpost到最后生成pdf的步骤。
2.中文支持（我是UTF8的忠实拥护者）
为了要支持中文，必须给mp文件加个壳，如下：
verbatimtex
%&latex
\documentclass{article}
\usepackage{CJKutf8}
\begin{CJK}{UTF8}{song}
\begin{document}
etex
beginfig(1);
beginfig(1)
....... // 这里写图形代码
endfig;
verbatimtex
\end{CJK}
\end{document}
etex
end
------------------
当然,在tex文件里还是要做相应的utf8处理。
所有版权，归王垠所有 :)
王垠对MetaPost的介绍：http://learn.tsinghua.edu.cn:8080/2001315450/metapost.html
1.生成流程
1)使用编辑器编辑mp文件和tex文件
2)使用mpost filename.mp生成filename.1文件(eps格式)
3)在tex中使用包graphicx，即
\usepackage{graphicx}
使用\includegraphics{filename.1}来插入图形。
4)生成pdf文件
这里我有个为解决问题，就是使用pdflatex时会提示\includegraphics不能被识别，但是改用如下步骤做却没错：
latex test.tex
dvips test.dvi -o test.ps
ps2pdf test.ps
为了方便，不妨写个make脚本或bash脚本来完成从mpost到最后生成pdf的步骤。
2.中文支持（我是UTF8的忠实拥护者）
为了要支持中文，必须给mp文件加个壳，如下：
verbatimtex
%&latex
\documentclass{article}
\usepackage{CJKutf8}
\begin{CJK}{UTF8}{song}
\begin{document}
etex
beginfig(1);
beginfig(1)
....... // 这里写图形代码
endfig;
verbatimtex
\end{CJK}
\end{document}
etex
end
------------------
当然,在tex文件里还是要做相应的utf8处理。
Wednesday, October 10, 2007
[zz]用 Latex 为论文排版
http://learn.tsinghua.edu.cn:8080/981852/study/latex.html
目录
语法规范
latex 中，用“%”做为注释行的开始，用“\”作为命令或者变量的开始。用一对大括号“{}”作为一个区块的起始和结束，在这一个区块中，命令和变量具有局部意义。用一对方括号“[]”作为某个命令参数的起始和结束，参数之间用“,”隔开。
文档结构
文档的开始必须使用类似如下命令：
\documentclass[a4paper, 12pt, onecolumn]{article}
这条命令指定文档的类型是 article，可以根据需要换为 slides，book 等；字体为 12pt；纸张类型是 A4；单栏。
然后使用 \usepackge 命令指定需要使用的宏包，如：
\usepackage{CJK} % CJK 中文支持
\usepackage{graphicx} % EPS 图形支持
\usepackage{indentfirst} % 中文段落首行缩进
\usepackage{fancyhdr} % 梦幻页眉
正文部分开始时，需要使用如下命令：
\begin{document}
\begin{CJK}{GBK}{song}\CJKcaption{GB} % 如果需要使用中文，必须加上这一句
相应的，正文结束后，需要使用：
\end{CJK}
\end{document}
中文格式相关问题
段落缩进
要使中文段落每段起始时空两个汉字的位置，除了需要使用宏包“indentfirst”外，还需要使用如下命令：
\setlength{\parindent}{24pt}
此命令加在导言区（导言区即在第一条命令和正文开始之间的部分）即可，参数应该根据正文字体的大小来设定，因为这里正文字体是 12pt，两个字的位置就是 24pt。
中文字体
设定中文字体很简单，只需要用类似如下的命令：
\CJKfamily{hei}这是黑体
我们也可以针对某个段落设定字体大小和行间距：
\fontsize{22pt}{26pt}后面的这一段文字，字体大小是 22pt，段落的行间距是 26pt
当需要将行间距恢复到默认值时，只要用
\linespread{}\selectfont
即可，因为行间距只有当字体大小发生变化时才会重新计算，所以在 \linespread 后面必须跟上字体尺寸变换的命令，如 \small 之类，或者直接写上 \selectfont。
章节和段落组织
可以用
\section{第一层章节}
\subsection{第二层章节}
\subsubsection{第三层章节}
这样的命令来分层次定义文章的章节，可以用
\begin{itemize}
\item 第一条
\item 第二条
\item 第三条
\end{itemize}
这样的命令来定义多个条目，可以用
\paragraph{第一段}
\paragraph{第二段}
\paragraph{第三段}
这样的命令来定义段落。
图片
用如下命令来插入图片（只支持 eps 图片）：
\begin{figure}
\begin{center}
\includegraphics[]{kingofcats}\\
\small{图1 猫王的图片}
\end{center}
\end{figure}
其中 \begin{center} 和 \end{center} 的含义是将其中的内容居页面中间排放，“\\”符号用来换行。
表格
用如下命令来定义表格：
\begin{tabular}{c|c}
\hline
第一列标题 & 第二列标题 \\
\hline
第一行第一列 & 第一行第二列 \\
\hline
第二行第一列 & 第二行第二列 \\
\hline
\end{tabular}
杂项格式
参考文献
用如下命令定义参考文献：
\begin{thebibliography}{99}
\bibitem{stid.Internetwork.smth}
stid.
论灌水与写论文的关系.
北京：新水木出版社，2005
\bibitem{kingofcats.newsmth}
kingofcats.
我是猫王我怕谁.
北京：灌水出版社，1999
\end{thebibliography}
脚注
用如下命令来定义脚注：
猫王\footnote{即 King of Cats，猫中之王，也称 stid}
页眉和页脚
用如下命令来定义页眉和页脚：
\pagestyle{fancy} % 使用梦幻页眉
\lhead{}
\chead{}
\rhead{\small{北京理工大学工程硕士学位论文（设计）开题报告}}
\lfoot{}
\cfoot{}
\rfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
常用命令
- \date{} 去掉标题中的默认日期
- \newcommand{\supercite}[1]{\textsuperscript{\cite{#1}}} 带一个参数的自定义命令
- \thispagestyle{empty} 此页不使用页眉和页脚
- \vspace{20mm} 在垂直方向空出 20mm 的距离
- \hspace{12pt} 在水平方向空出 12pt 的距离
- \underline{} 加下划线
- \setcounter{page}{1} 从 1 开始计算页码
- \newpage 强制换页
- \clearpage 给最后一页也加上页眉和页脚
- \makebox[72pt][s]{被打散的文字} 定义宽度为 72pt 的文本盒，并将其中的文字均匀分布
- \makebox[30mm][c]{居中的文字} 定义宽度为 30mm 的文本盒，并将其中的文字居中排列
Fedora上配置Tex UTF-8 中文系统
文章来源：
http://reciteword.cosoft.org.cn/yaoguang/showarticle.php?category=myarticle&&doc
page=0&&newsid=25
作者：胡正
2007.9.18
为了制作中文PDF书籍文件，并解决PDF中文不能拷贝的问题，用最新的方法再次配置了一下
Tex系统，参考的文章是：
http://mailboxpublic.googlepages.com/texlive2007cjkchinesehowto
步骤如下：
1. 安装Tex Live 2007.
下载：
ftp://ftp.ctex.org/CTAN/systems/texlive/Images/texlive2007-live-20070212.iso.zip
unzip后mount上，运行install-tl.sh，按i就行了。
装完后编辑~/.bash_profile
PATH=/usr/local/texlive/2007/bin/i386-linux:$PATH
2. 生成字体文件。
mkdir ~/font
cd ~/font
cp /media/c/WINDOWS/Fonts/simsun.ttc .
yum install fontforge
cp /usr/local/texlive/2007/texmf-dist/source/latex/CJK/utils/subfonts/* ~/font/
cp /usr/local/texlive/2007/texmf/fonts/sfd/*.sfd ~/font/
time fontforge -script subfonts.pe simsun.ttc song Unicode.sfd
大概要个把小时。
编辑一个makemap文件，内容如下：
for i in *.tfm
do
cat >> song.map << EOF
${i%.tfm} ${i%.tfm} < ${i%.tfm}.pfb
EOF
done
然后chmod +x makemap
./makemap
编辑一个c70song.fd文件：
% This is c70song.fd for CJK package.
% created by Edward G.J. Lee
% modify by Yue Wang
\ProvidesFile{c70song.fd}
\DeclareFontFamily{C70}{song}{\hyphenchar \font\m@ne}
\DeclareFontShape{C70}{song}{m}{n}{<-> CJK * song}{}
\DeclareFontShape{C70}{song}{bx}{n}{<-> CJKb * song}{\CJKbold}
\endinput
最后拷贝文件：
cd ~/.texlive2007
cd texmf-var
mkdir -p fonts/map/dvips/CJK
mkdir -p fonts/tfm/CJK/song
mkdir -p fonts/type1/CJK/song
mkdir -p tex/latex/CJK/UTF8
cp ~/font/song.map fonts/map/dvips/CJK/
cp ~/font/*.tfm fonts/tfm/CJK/song
cp ~/font/*.pfb fonts/type1/CJK/song
cp ~/font/c70song.fd tex/latex/CJK/UTF8
更新系统：
texhash
updmap --enable Map song.map
3. 测试。
编辑一个test.tex文件：
\documentclass{article}
\usepackage{CJKutf8}
\begin{document}
\begin{CJK}{UTF8}{song}
你好!
\end{CJK}
\end{document}
然后
pdflatex test.tex
evince test.pdf，应该中文正常了，而且中文可以拷贝。搞定！ ：）
http://reciteword.cosoft.org.cn/yaoguang/showarticle.php?category=myarticle&&doc
page=0&&newsid=25
作者：胡正
2007.9.18
为了制作中文PDF书籍文件，并解决PDF中文不能拷贝的问题，用最新的方法再次配置了一下
Tex系统，参考的文章是：
http://mailboxpublic.googlepages.com/texlive2007cjkchinesehowto
步骤如下：
1. 安装Tex Live 2007.
下载：
ftp://ftp.ctex.org/CTAN/systems/texlive/Images/texlive2007-live-20070212.iso.zip
unzip后mount上，运行install-tl.sh，按i就行了。
装完后编辑~/.bash_profile
PATH=/usr/local/texlive/2007/bin/i386-linux:$PATH
2. 生成字体文件。
mkdir ~/font
cd ~/font
cp /media/c/WINDOWS/Fonts/simsun.ttc .
yum install fontforge
cp /usr/local/texlive/2007/texmf-dist/source/latex/CJK/utils/subfonts/* ~/font/
cp /usr/local/texlive/2007/texmf/fonts/sfd/*.sfd ~/font/
time fontforge -script subfonts.pe simsun.ttc song Unicode.sfd
大概要个把小时。
编辑一个makemap文件，内容如下：
for i in *.tfm
do
cat >> song.map << EOF
${i%.tfm} ${i%.tfm} < ${i%.tfm}.pfb
EOF
done
然后chmod +x makemap
./makemap
编辑一个c70song.fd文件：
% This is c70song.fd for CJK package.
% created by Edward G.J. Lee
% modify by Yue Wang
\ProvidesFile{c70song.fd}
\DeclareFontFamily{C70}{song}{\hyphenchar \font\m@ne}
\DeclareFontShape{C70}{song}{m}{n}{<-> CJK * song}{}
\DeclareFontShape{C70}{song}{bx}{n}{<-> CJKb * song}{\CJKbold}
\endinput
最后拷贝文件：
cd ~/.texlive2007
cd texmf-var
mkdir -p fonts/map/dvips/CJK
mkdir -p fonts/tfm/CJK/song
mkdir -p fonts/type1/CJK/song
mkdir -p tex/latex/CJK/UTF8
cp ~/font/song.map fonts/map/dvips/CJK/
cp ~/font/*.tfm fonts/tfm/CJK/song
cp ~/font/*.pfb fonts/type1/CJK/song
cp ~/font/c70song.fd tex/latex/CJK/UTF8
更新系统：
texhash
updmap --enable Map song.map
3. 测试。
编辑一个test.tex文件：
\documentclass{article}
\usepackage{CJKutf8}
\begin{document}
\begin{CJK}{UTF8}{song}
你好!
\end{CJK}
\end{document}
然后
pdflatex test.tex
evince test.pdf，应该中文正常了，而且中文可以拷贝。搞定！ ：）
Tuesday, October 9, 2007
[zz]无间道全剧情解析：部分赞成部分反对
我听到很多看过《无间道iii-终极无间》的网友说这是一部很难看懂的电影！而且对影片中的剧情充满了疑问？其实我刚看的时候也有这种感觉！不过经过看了 一次电影和五次碟片后，再加上看了《无间道iii-终极无间》的导演刘伟强在香港电台综艺节目《电影两面睇》中对本片剧情的解剖，另外还加上网友们在网上 对本片剧情的分析！我基本上可以说全部看懂了这部影片！所以我把大家认为是疑问的东西综合起来，写了这篇文章！但愿能全面解密《无间道iii-终极无间》 中所有的疑问！下面我将解答影片中点击率最高的十大疑问！
疑问一：陈俊为什么会在杨棉荣面前自杀？
解答：因为陈俊是韩琛派进警局的卧底，这个秘密被杨棉荣知道了！而杨锦荣说不给陈俊机会！所以陈俊唯有自杀，就算他不自杀，也难逃法律的制裁！因为杨锦荣不会放过他的！那么杨锦荣怎么知道陈俊是韩琛派进警局的卧底？
理由：首先我要说明杨锦荣并不是之前媒体所猜测的双重卧底，而是警局高层很信任的一个人，他 的作用就是洗清警局的内鬼。那他和韩琛是什么关系呢？很简单！是一种互相利用，互相帮助的关系！他们只是交换情报，各取所需而已！如果你注意陈永仁，杨锦 荣，沈澄在码头的那场戏！你会听到陈永仁对杨锦荣说："以后和韩琛交换情报时要小心点"！所以说陈俊就是韩琛出卖给杨锦荣的，好让杨棉荣在上级面前立功， 这样他等于帮了杨锦荣！但是反过来杨锦荣自然也要帮他！反正一句话就是互相利用！
疑问二：记得有一场戏，就是刘健明把陈俊的制服送过去时！这时从陈俊的制服里掉出一串钥匙！刘健明还把钥匙放回制服去了！很多网友认为这场戏是多余的！其实不是多余的！
解答：因为刘健明后来就是通过这串钥匙打开了陈俊保龄球会储物柜的，然后找到了那几张杨锦荣和沈澄在天台见面的照片！作为怀疑杨锦荣是内鬼的开始！
理由：如果你仔细看！会发现当内务部的张警官说怀疑杨锦荣的内鬼的时候，刘健明马上给庶务部打了个电话，说有事要过去一下！当刘健明到庶务部找到了陈俊的制服，从里面摸出了那串钥匙！这场戏导演的镜头放的很清楚！
疑问三：韩琛为什么叫陈永仁用烟灰缸砸沈澄弟弟沈亮的头？
解答：至于这场戏，好多网友大呼导演做作，说是多余的！更有很多网友认为既然是谈生意，为什 么要打架，那样岂不是把生意谈的更糟，直接引起冲突！还有网友认为这根本是导演为了安排六大影帝同台竟技作铺垫的一场戏！其实这场戏相当重要！至于为什么 有这场戏？那是因为韩琛当时根本就是不相信沈澄和陈永仁！所以让陈永仁去送死！不过还好杨锦荣及时出现救了陈永仁！有些人认为杨锦荣那时是去抓陈永仁，其 实是因为杨棉荣知道陈永仁有危险，然后去救他！想想：如果杨锦荣当时没出现！而当时陈永仁是在沈澄的地盘上，可想而知，打了他那边的人，只有死路上条！幸 好杨锦荣及时出现救了陈永仁一命！
理由：那么说韩琛为什么不相信沈澄和陈永仁呢？相信六大影帝大警局同台竟技后，再加上沈澄用 酒瓶砸了陈永仁一下，后来韩沈双方说事情扯平了！这时又出现了一场戏！是陈永仁在吃泡面，韩琛走过来，后来陈永仁问韩琛对沈澄这次放过了他有什么看法？这 时韩琛说了一句话："你有没有碰过一种人，不知什么时候对你好，什么时候要你的命，我就碰过，我也不知道他这次为什么不杀你，以后内地的这条财路就交给你 了"！很显然韩琛这时已清怀疑沈澄可能是警察的卧底，但不敢肯定！可韩琛说把内地这条财路交给陈永仁时！他清楚沈澄就算是警察，也是你陈永仁去送死！所以 那次和沈澄在码头交易时，韩琛车在半路就调头叫兄弟们全部回去了！让陈永仁一人去交易！而且还把货全部藏起来了！准备让陈永仁送死！在这里傻强还问过韩琛 为什么不去码头交易？韩琛说是这条命告诉他的！不过这次还是杨棉荣出面救了陈永仁！因为杨棉荣和沈澄早就认识，所以他知道沈澄的真正身份！用电影里的话就 叫做"粤港合作"！所以说如果杨锦荣没及时出现陈永仁和沈澄必有一死！那么这么说韩琛是什么时候开始才相信陈永仁的！那是在傻强死后！陈永仁对韩琛说傻强 是警方卧底，他已经解决了他！这时韩琛才开始相信陈永仁！后来就带陈永仁去仓库，由于陈永仁和刘健明合作！韩琛当时在仓库里被刘健明一枪解决了！
疑问四：在停车场有场戏，就是刘健明在杨锦荣的车底装录音器时手机响了，这时他从里面跑出来，杨锦荣也发现了他！有些人对这场戏很迷惑，下面我作详细解释！
解答：这场戏就是说明从这时起，杨锦荣已经知道刘健明在调查自己了！而他也怀疑刘健明是警局内鬼！
理由：首先杨锦荣怎么知道刘健明正在调查自己呢？他是根据车内安装的跟踪器看到刘健明钻进他车底时鬼祟的身影！从这场戏可以看出刘健明和杨锦荣的计中计即将展开。
疑问五：可记得有这么个情节：他监视杨锦荣的时候，杨锦荣忽然直直地看着镜头。这时他的反应很奇怪，他居然笑了！那么他这一笑代表什么呢？
解答：代表刘健明已经知道杨锦荣发现自己正调查他！想想：通过停车场那场戏，杨锦荣肯定知道 刘健明会对自己会作更深入的调查！所以他肯定早已发现刘健明在他办公室里装满了监视器！而刘健明为什么要笑呢？很简单！他知道杨锦荣正在怀疑他，也正在调 查他，但是目前没有什么证据可以致他于死地，要不然他会破坏掉自己的监视器，然后带人来抓他！而不会像现在这样直直的看着监视器没有什么办法！况且说他还 可以利用监视器好好调查杨锦荣！所以他笑了！但是他没有想到这个监视器也成了杨锦荣调查他的设备了！此话怎讲！请听下一疑问！
疑问六：为什么杨棉荣明明知道刘健明在监视他，他还要在监视器面前从保险箱拿出录音带，然后开车出去送给沈澄？
解答：这只是杨棉荣在调查刘健明时联合沈澄使的一个将计就计，也可以说是计中计！
理由：因为杨锦荣只是怀疑刘健明是内鬼，但是没有证据还是不敢肯定，所以设此一计观察刘健明 到底是不是内鬼！他知道刘健明正在监视自己，所以他故意从保险箱拿出一版空白的录音带放到那个信箱去，然后故意叫沈澄去取。可这录音带最后还是被一路跟纵 杨锦荣的刘健明给烧了，其实这一切杨锦荣都清楚！既然刘健明会把自己的录音带烧掉！这点足以说明刘健明很有可能是警局的的内鬼，所以说这不是是杨锦荣的一 个计策而已！可聪明的刘健明这次中计了！
疑问七：记得有一场戏，就是陈永仁和沈澄在码头交易时，而黄志诚正准备布置好一切抓韩琛时！这时杨锦荣出现了！说上级有命令，今晚不用行动！那么杨锦荣为什么要阻止黄志诚的行动？
解答：很简单！他知道码头那边如果真的交易了，沈澄可以抓住韩琛，你黄志诚去了也许和沈澄必有一拼！因为杨锦荣知道沈澄是警察，而黄志诚并不知道！
理 由：记得杨锦荣阻止黄志诚行动时，他很生气的说了一句："我不管你们什么上级的指令，我只知道我的一个兄弟正在外面拼命"！其实想想：如果这时杨锦荣不及 时出现会有什么后果！那就会出现警察向警察开火的场面了！很明显我这里指的警察是黄志诚和沈澄！但黄志诚还是不听杨锦荣的话，这时警局的梁警官来了，当然 身为警察部的高层人员梁当然清楚当时的情形，及沈澄的警察身份，所以他出面制止了！
疑问八：刘健明偷了李心儿电脑过后的第二天，李心儿在刘健明面前说电脑密码就是车牌号码！很多人对这场戏很是迷惑！下面我作详细解释！
解答：这场戏的目的就是描述刘健明就是从这里才清楚李心儿已经知道了他是警局内鬼的身份！所以出现了后来刘健明假装被李心儿催眠说出自己真正身份的一幕！那么刘健明是怎么知道李心儿发现他是内鬼的呢？还有就是刘健明为什么要假装被李心儿催眠然后说出自己真正身份呢？
理由：因为李心儿在说"密码就是车牌"的时候，就刚刚好有张照片在桌上，其实世上哪有这么巧 的事！所以说所有的巧合都是人为的！这点对于从事破案工作的警察-刘健明来说是不可能识不破的！他就是从这时开始怀疑李心儿的！那么李心儿是什么时候开始 怀疑他的呢？原因很简单，陈永仁死了，关你刘建明什么事？你干吗来接近我？而且对我这么好！必有所图！所以我来催眠你让你自己说出真相！其实我们大家都以 为刘健明真的被李心儿催眠了，然后说出了自己真正的身份！其实，那都是假象！刘健明哪会这么容易被催眠？而是刘健明反过来在利用李心儿！自己利用假装被催 眠的这种方式把真相告诉李心儿，以博取他的同情，并希望可以得到她的原谅而且能够帮他保守秘密！ 可见刘健明这个人是多么的狡猾呀！
疑问八：记得有一场戏，就是刘健明在办公室通过监视器监视杨锦荣时，电话突然响了！而这时电 话的声音是陈永仁的！具体是说看到了杨锦荣和韩琛见面！这时刘健明把电话挂了！随后电话又响起，这时是李心儿的声音，他说有人寄了盒录音带给陈永仁，那录 音带现在在她手上！关于这场戏的争论是最多的！有人说这时已经是2003年了，陈永仁都已经死了，怎么还会打电话！还有一个问题就是：陈永仁都死了那么久 了，怎么还有人寄录音带给他，其实当刘健明看到那个录音带时，寄录音带的信封上写的是"陈永仁（收）"！这一切的一切怎么解释呢？且听下面分解！
解答：其实刘健明接到的第一个电话也是李心儿打的，只是刘健明把李心儿的声音幻觉成陈永仁的声音！为什么会这样？下面再作分解！还有那个带子到底是谁寄给陈永仁的呢？答案是杨锦荣！杨锦荣这样做有什么意义呢？自然是听下面分解！
理由：如果你很仔细观看影片，你会看见当刘健明接到李心儿第二个电话时，李心儿的第一句话 是："刚才为什么不说话"？这句话很显然能证明前面那个有陈永仁声音的电话是李心儿打的！那么刘健明为什么把李心儿的电话幻想成陈永仁的声音呢？一句话： 刘健明破案心切，产生了幻觉！因为他一直都想找到能证明杨棉荣是内鬼的证据，可是始终没有很大的发现，所以他把李心儿打进来的电话幻觉成已经找到杨锦荣是 内鬼的证据了，因为电话里的陈永仁说看到了杨锦荣和韩琛在见面！电话过后他出门的时候不是连门都找不着吗！所以足以证明他已经很疲惫了，产生幻觉是理所当 然的，当然他这只是幻觉，并不是我们所说的精神分裂或发疯之类的，因为刘健明根本就没有疯过，他后来也一直只是在装疯而已，关于这点我在下面会作详细解 释，敬请留意！那么说第二个问题！杨锦荣为什么要寄带子给李心儿？很简单，他在调查刘健明，但是只是怀疑，没有证据！所以他设此一计再试刘健明，没想到刘 健明拿到录音带后故意说把它交给重案组，实际上是在半路制造了车祸，把录音带拿来回来了，当然这一切杨锦荣一定是看在眼里的，所以他更是肯定了刘健明是警 局的内鬼，不然用不着一直销毁认为对自己有威胁的录音带！所以说他寄磁带写"陈永仁（收）"，而且地址是李心儿那里的，这只不过是杨锦荣调查刘健明时使的 一个计策而已，没想到刘健明再次上当！
疑问九：在这第九个疑问当中我将解答有关录音带的全部内容！想想：关于录音带本片使用的太多 了，第一：杨锦荣从保险箱拿出的那块录音带，后来放进信箱，最后被刘健明烧毁！第二：杨锦荣寄了盘带子给李心儿，而信封的地址却是李心儿的，最后这盘录音 带还是落到了刘健明手里！那么这盘录音带中录了什么呢？下面有分解！第三：刘健明从杨锦荣房间偷出了一盘录音带，那么这里面录了些什么呢？有人说这盘录音 带的内容是歌曲《被遗忘的时光》，也就是影片最后在刘健明办公室找到的那盘，我可以告诉你这个答案是错的！真正的答案等下再透露！第四：沈澄最后放给刘健 明听的录音带是哪里找到的呢？第五：刘健明正在收听从杨锦荣的保险箱中偷回来的录音带，里面是杨锦荣和韩琛的对话！听完后他把录音机直接放进口袋，走出办 公室，叫上内务部所有工作人员前去保安科找杨锦荣，要他听录音带里面的内容！当时他的表情很自信！还说了一句台词："去请保安科的头头回来喝咖啡"！可是 为什么刘健明当着众警察的面时录音机的内容却变成了刘健明和韩琛的对话！关于这场戏网友争论很多，有人说刘健明疯了，有人说这是杨锦荣的计中计，故意在里 面穿插一段自已和韩琛的对话，然后又录上刘健明和韩琛的对话，让刘健明在众人面前出丑！其实这些说法都是错误的，真正的说法下面呈现！
解答：首先在信箱中被刘健明烧毁的录音带是一块空白的，因为那只不过是杨锦荣的一个计策而 已。还有刘健明从李心儿手中拿回的那版录音带，其实就是影片最后在刘健明办公室的到的那块录有歌曲《被遗忘的时光》的录音带，因为当刘健明听了从李心儿手 中拿回录音带的内容后发现自己上当了，所以他必须拼一拼，于是就出现了去杨锦荣保险箱找磁带的一幕！还有刘健明从杨锦荣保险箱偷回来的录音带里面的内容确 实是杨锦荣和韩琛的对话，并不是某些人所说的录音内容是歌曲《被遗忘的时光》，更不是某些网友所说的刘健明那是幻觉，他当时特别的清醒！那他为什么有了录 音带去抓杨锦荣时，竟然会当众面前在录音机中播自己和韩琛的对话呢？这个下面再作分解！那么最后沈澄手中刘健明和韩琛谈话的录音带又是从何而来呢？且听下 面分解！
理由：其实这一切要从杨锦荣说起，也可以说刘健明在他保险箱偷录音带，这一切都是自己安排 的！想想：他是不是对换水的陈伯说：陈伯你真厉害，我们没水了你都知道啊！所以他肯定刘健明在水里下药的事情！所以那天他支开了保安部所有人员，只留了两 个人，而那两个人喝了咖啡后就不醒不事了，因为泡咖啡的水有毒呀！所以保安部就被刘健明很轻松的进去了！当刘健明开杨锦荣保险箱时，不知你他细看了没有！ 这时银幕上一共出现过三双手！一双手是戴了手套的，另一双手是穿白衬衫戴了个手表的，还有第三双手是穿西服的，而且没戴手表和手套！很显然这三双手当中有 一双手是刘健明正在开密码箱，也就戴手套的那双！而剩下两双手有一双也是刘健明的，因为那是刘健明回忆自已以前在电脑屏幕前所记录：杨锦荣在保险箱上所旋 转的角度！那么第三双手就是杨棉荣的，此时杨锦荣也正在刘健明的房中开保险箱，因为他知道刘健明这时已在他房间里所以他才趁此机会潜入刘健明的办公室，这 就是他为什么要支开保安部所有人给刘健明提供机会盗取录音带的理由，因为只有这样刘健明才会不在办公室，我杨锦荣才有机会！所以最后沈澄放刘健明和韩琛的 录音带时说了一句话："你还是听听杨警官在你房间找到的录音带吧！"所以当刘健明盗取录音带后，问你在我办公室玩的开心吗？这点足以说明杨锦荣对刘健明的 一切了如指掌！当刘健明回到办公室后，听了从杨锦荣那偷回的录音带，确实是杨锦荣和韩琛的对话，但是他这时发现了一个问题！自己和韩琛对话的录音带不见 了，再联想到在保安部时杨锦荣打给他的那个电话！我完全可以断定，在自已去保安部偷录音带的同时自已那个致命录音带是被杨锦荣拿走了！我深知：以他手上那 盘杨锦荣和韩琛对话的录音带根本定不了杨锦荣的罪，也许杨棉荣和韩琛交换情报的事上级早就清楚了！再想想自己那盘录音带，以上面的录音内容完全可以致自己 于死地，也许杨锦荣马上就会派人来抓我了！更何况杨锦荣怀疑我这么久，调查我这么久，早就看我不顺眼了，现在那么重要的证据落在他手上，我只有死路一条 了！所以在这种环境所逼下，刘健明就只有鱼死网破，破釜沉舟，先下手为强，后下手遭殃！他早就想好以装疯的形式来自首，所以拿了自己和韩琛对话的录音带在 大家面前放！这样就等于自已把罪行公布于世，也算是一种自首，他想这样总比被杨锦荣揭穿自已好多了！所以后来就出现了一枪解决了杨棉荣及自杀没成功的结 果！其实这都是有原因的，因为他在装疯！
疑问十：关于刘健明是不是装疯？
解答：很多人认为不是，我前几天贴了一篇《终极解密《无间道�》-刘健明其实在装疯》的文章 后被人大骂，好多网友说编剧没想到的都被你想到了，意思是说在无中生有的！其实我开始也不相信刘健明是在装疯的！后来看了《无间道iii-终极无间》的导 演刘伟强在香港电台综艺节目《电影两面睇》中对本片剧情的解剖后我才大悟！刘伟强说："如果刘健明真的疯了，那他就等于走出了无间地狱的轮回，因为对于一 个疯了的人来说等于忘了以前所有的一切，重新开始了！如果刘健明的下场是这样的话，那就不符合我们《无间道》系列的主题了！相反，如果刘健明如果没有疯， 就预示着他从此走上不归路，要承受无间的痛苦，因为他不能忘掉以前的一切，而自己现在又成了残疾人，警察也没得做了，所以说他比死了还更痛苦，你如果仔细 看：最后他手指在轮椅边缘上轻轻的敲扣着，其实那都是陈永仁在扣敲摸索密码器时的动作！这时他已经把自己幻想成陈永仁了！希望能够像陈永仁那样得到解脱！ 勉受这无间之苦！你留意了影片中最后的几行字吗？那就是写给刘健明！"听了刘伟强的解剖我终于明白了，还有影片最后的几行字好像是什么："当坠无间地狱 者，日复一日，年复一年，永世不得翻身"，好像是这名话吧，不过也好像说错了，反正意思都差不多！至于刘健明为什么要装疯？我想我上面对录音带事件的分析 已经把这问题说的很清楚！那么哪些方面能证明刘健明是在装疯呢？下面我将贴一些证据上去！
理由：第一：在香港，精神病患者是不必坐牢的，接受治疗即可。所以当刘健明发现杨锦荣拿走了 他和韩琛对话的录音带后。他就想了："既然瞒不住了，不如将计就计！我知道你们现在马上会揭发我，但是我一定要抢先于你们！等你们揭发了我我就完了！所以 他只有通过装疯的形式去自首！
第二：其实刘健明最后还是在警方面前自首了，决定自首之前他清楚以他的罪行自首后也是难逃一 死的，所以他只有通过装疯这种形式进行自首，正如我上面所言：在香港，精神病患者是不必坐牢的，接受治疗即可。只有这样才能免于一死。所以我们看到下面这 两场戏！第一场戏：刘健明正在收听从杨锦荣的保险箱中偷回来的录音带，里面是杨锦荣和韩琛的对话！听完后他把录音机直接放进口袋，走出办公室，叫上内务部 所有工作人员前去保安科找杨锦荣，要他听录音带里面的内容！当时他的表情很自信！还说了一句台词："去请保安科的头头回来喝咖啡"！第二场戏：当他在杨锦 荣面前把录音机打开时里面的对话却变成了刘健明和韩琛的了，这时刘健明拔枪指向杨锦荣的头说："刘健明，我要亲手逮捕你"！看到这里，大家都认为刘健明已 经疯了，已经连谁是自己都分不清了！其实没有，他是装的！这样既可以把自已的罪行公布于世，也可以说算是自首吧！但是这样做更可以让大家以为他已经疯了， 而且有悔过的心理！这样就等于达到了他自首但不坐牢的目的了！后来还出现了一枪解决杨锦荣和自杀的镜头！其实这两方面还是有原因的！想想：刘健明在疯狂状 态下，居然那么远还可以一枪打暴杨锦荣的头？而自杀时用的同样是那把枪，那么近却打不死自己！这样是不是太夸张了点？那么真相只有一个，他是在装疯，所以 趁此机会杀了他一个仇人！
第三：他自杀的时候为什么打下巴？一般来说都应该打太阳穴的吧！那原因只有一个：他在装疯！ 为了更逼真，他只有自残！让别人都相信他应该死掉了（包括观众），而且还要让大家都误以为他已有悔过的心理！其实他自己心里很清楚，打下巴而已，大不了缝 几针，不会弄出人命的！再说一个警校毕业的人怎么可能连开枪自杀都不会成功呢？难道他会不知道枪打中那里会死？打中哪里不会死？所以是他自己不想死！其实 他不是在自杀仅是自残而已！这种自残的手段在柯南，金田一故事中也很常见，凶手往往通过这样做来让人们不怀疑他！刘健明就是通过自残的方式让别人以为他已 经疯了，而且已经有悔过的心理！希望大家能够重新接受他这个人！
第四：最后mary来看他的时候态度很冷漠，这也是有原因的！作为最了解他的女人，经过录音 带的事件后我相信mary应该已经看透他了，而且他俩毕竟也相处了那么久，对刘健明的一切可以说是了如指掌！只有她知道刘健明是在装疯，但是出于往日的一 份情义，她并没有揭发他。其实刘健明在这一部和第一部的结局一样，用自己的智慧逃过了法律的制裁！
通过以后这些足以证明刘健明是在装疯！但有 网友说，他既然是在装疯，那他为什么会被李心儿催眠了呢？在电话中为什么把李心儿的声音听成陈永仁的呢？为什么那次接到李心儿电话后出内务部时连出口都不 知在哪边？再说幻想陈永仁用枪指着他怎么解释？还有一场他换衣服时陈永仁旁边冲着他笑，这又是为什么？这一切的一切难道就不能证明刘健明已经疯了？这些问 题我会一个一个解答：首先前三个问题上面有答案的，自己找找！至于他为什么会幻想陈永仁用枪指着他！这个问题是因为刘健明尽量把自己幻想成陈永仁，希望能 像陈永仁那样得到解脱！这句话是刘伟强说的！所以拿枪的那个陈永仁是他自已扮演的，而自己所指的刘健明及坐在旁边的黄志诚则都是自已幻想出来的!这并不表 示刘健明已经疯了，只能说他希望能尽快得到解脱的那种心理！至于那场他换衣服时陈永仁旁边冲着他笑的戏，就更清楚的表明他把自己幻想成陈永仁了！因为他那 时是在照镜子，而且冲着镜子笑，而陈永仁这时在镜子里面，也是在微笑！其实镜子里面那个在笑的是自己，只是他自己把自己幻想成了陈永仁！所以镜子里会出现 陈永仁在笑！最后解答二个问题：就是刘健明在警局自残以后！李心儿收到一条短信内容是：刘健明说："李医生，过了今天就没事了，我一定会亲手逮捕刘健 明"，这场戏有什么意义呢？导演怕我们对剧情误会，因为刘健明在大家面前播出了他和韩琛的录音观众一定会很意外，其实在这之前，刘健明就已经决定自首了， 不然他不会给李心儿发那条短信，所以这场戏是导演为了防止我们误会剧情而安排的！第二个问题：就是最后刘嘉玲在刘健明背后开了一枪，有些人说这场戏是多余 的，其实这这场戏具有画龙点睛的作用！而且一箭双雕，刘健明当时在想：就是因为这个女人，我走了今天这个地步，饱受无间之苦。而另一方面则说明刘健明没有 忘掉以前的一切，所以说他还是无间道路上巡回，始终没有得到解脱！这也符合了《无间道》系列的主题。
Saturday, October 6, 2007
Friday, October 5, 2007
Lambda演算
本文介绍了 'lambda 演算'.
原文地址：http://blog.sina.com.cn/s/blog_4b23ee54010006uy.html
设
L ≡ y + x
M ≡λy. L ≡ λy. (y + x)
则
(λx.M)y = M[x:=y] ≠ λy. y + y
我们还是用PASCAL语言为例来说明这点。
M就相当于以下的函数（在下面例子中我们扩展一下PASCAL的语法，让其函数返回值也可以为一个函数）：
program Example_2;
var
y, z: integer;
function M(x: integer): function; // M的返回值也是一个function
function L(y: integer): integer; // L是M的子函数
begin
L := y + x;
end;
begin
M := L;
end;
begin
readln(y, z);
writeln( M(y)(z) );
end.
上面例子中M的返回值也是一个function，因此M(y)得到的是一个函数，M(y)(z)得到的才是一个函数值。
上述程序的正确输出应该是z+y。在调用了M(y)以后，函数M返回的是一个函数L，且因为L是M的子函数，L中的x就是M的参数x，他的值应该等于y，不过L本身的参数名字也叫做y，如果不加区分就会搞混淆。一种错误的计算过程如下：先计算M(y)，得到一个函数
function L(y: integer): integer;
begin
L := y + y;
end;
然后计算L(z)，得到z+z。这个结果是错误的，这就是对局部变元和全局变元不加区分的结果。
当然如果让计算机来执行这个程序它是不会搞错的，因为编译器采用了一个叫做“名字空间”的方法，每个变元名前面都会加上名字空间。具体而言，在编译器看来，函数M应该是下面这个样子的
function M(M_x : integer): function;
function M_L(M_L_y: integer): integer;
begin
M_L := M_L_y + M_x ;
end;
begin
M := M_L;
end;
计算机计算M(y)(z)的时候，先计算M(y)，得到一个函数
function M_L(M_L_y: integer):integer;
begin
L := M_L_y + y
end;
然后计算 M_L(z)，得到 z + y。这个结果是正确的。
其实编译器所采用的这个方法就是把函数中所有出现过的变元名，函数名都加上一个前缀，这个前缀是这个函数本身的名字空间。主程序的名字空间就是空字符串， 主程序的子函数M的名字空间就是"M_"，M的子函数L的名字空间是L的父函数M的名字空间加上L自己的名字，即"M_L_"。这样就永远不会出现局部变 元和全局变元同名的问题了。
不过作为程序员来说，为了让程序更便于理解，需要自己来手工地给函数L的参数改名。例如可以把M改为下面的形式
function M(x: integer): function;
function L(y1: integer): integer; // 把L的参数命名为y1
begin
L := y1 + x;
end;
begin
M := L;
end;
这样在计算M(y)(z)的时候就不会搞错了。
下面我们回到λ演算中来。在λ演算中也会有这种问题。
设
L ≡ y + x
M ≡λy. L ≡ λy. (y + x)
则
(λx.M)y = M[x:=y] ≡ (λy. (y + x))[x:=y] ≠ λy. y + y
这就和刚才的计算过程一样，如果不做任何处理地直接将(λy. (y + x))中的x换为y，则会导致原来自由的y在替换后变为约束的，这就产生了错误。
原来自由出现的变元在β替换以后变成了约束的，这种现象就叫做“variable capture”。
解决“variable capture”的方法也和程序设计中一样，只要把M中的约束变元y改一个名字就可以了。这其实是基于这样一种思想：把函数中的参数或局部变元名字改变， 函数的功能仍然保持不变。但在λ-演算，我们需要把这种思想形式化地定义出来。在Curry的著作以及其他一些λ-演算的著作中，公理
(α) λx.M = λy. M[x:=y] 这里y不出现于M中
被加入形式理论λβ中。这条α公理就是为了处理变元改名而引入的。
原文地址：http://blog.sina.com.cn/s/blog_4b23ee54010006uy.html
演算的概念
在Lambda演算中，我们所做的演算是通过一定的机械规则将一个lambda term 转化为另一个lambda term，这个转化过程就称为lambda calculus广义上来说，对于任何一个发展变化的数学(或物理)系统，只要赋于它的状态以一定的语义，将它从一个状态变换到另一个状态，这个变化过程就是一个演算过程。
比如我们经常做的加法运算：2+13=15,这就是在PA系统中做的演算。我们做数学证明，就是在形式化的公理系统中进行逻辑推导的演算。我们写程序，就 是在图灵机上做演算。一段程序的指令序列就描述了一个演算过程。我们说话，写字，就是在自然语言上做演算。强人工智能主义者认为：人类思考问题，也是在做 某种演算。
在经典的计算理论中，演算的最重要的性质就是机械性，这是“演算”的强大威力所在，也是其局限性所在。但是如果把演算的概念扩展到物理世界中，有可能能突破机械性的局限(量子图灵机)。
起源
在十八世纪初，现代数学取得了辉煌的成果。其中G. W. Leibniz (1646 -- 1716)是当时的杰出者，他是微积分学的创始人之一。作为数学家和哲学家，他为推动现代逻辑的发展也作出过重大的贡献。 Leibniz曾有一个宏伟的理想：（1）建立一个通用语言，使得所有的问题能在其中表述；以及（2）找出一种判定方法，解答所有在通用语言中表述的问 题。
人们为实现这一理想付出了很多努力，直至二十世纪才出现一些重要成果。谓词逻辑和集合论的建立实际上完成了Leibniz的第一条理想，这归功于一些一流的数学家，Frege, Cantor, Russell, Hilbert 和 Godel。Leibniz的第二个理想成为了一个哲学问题：“是否存在一个通用的判定方法求解所有用通用语言表述的问题呢？”这就是所谓的Entscheidungsproblem（德语，意思是“判定问题”）。
在1936年，A Church（这家伙就是McCarthy的导师）和Alan Turing独立地给出了这个问题的否定答案。为了解决此问题，他们以 不同的方式形式化定义了“可判定”的概念（或者“可计算”的概念）。事实上他们给出了两种不同的计算模型：Turing发明了一组机器---Turing 机，并以此定义可计算性；Church发明了一个形式系统---lambda演算，并以此定义了可计算性。后来证明，图灵机和lambda演算其实是等价 的。就这样，λ-演算问世了。
Lambda 演算对函数式程序设计Functional Programming有巨大的影响，特别是Lisp语言的精髓。
非形式化描述
在 lambda 演算中，每个表达式都代表一个只有单独参数的函数，这个函数的参数本身也是一个只有单一参数的函数，同时，函数的值是又一个只有单一参数的函数。函数是通过 lambda 表达式匿名地定义的，这个表达式说明了此函数将对其参数进行什么操作。lambda演算所以不考虑多元函数的情况，因为多元函数可通过重复作用一元函数的运算而得到。
λ-演算有两种基本运算：“作用(Application)”与“抽象(Abstract)”。
作用：表达式 FA 表示对象 F 作用于对象 A，FA 既可被理解为计算 FA 的过程， 也可被理解为此过程的输出。λ-演算是无类型系统，从而自作用 FF 是合 法的，这将模拟递归。
抽象：在抽象运算中，记号λ将被引入。对于数学式x^2，λx. x^2 表示函数 x |→ x^2，通俗一点的表示，λx.x^2就是函数f(x)=x^2,当然，也可以认为是f(y)=y^2，参数的取名并不重要。
一般来说，若 M[x] 为表达式，则 λx. M[x] 表示函数 x |→ M[x]。
把作用与抽象结合起来就有如下方程 (λx. M[x])N = M[N]
这一方程便是所谓的β-变换。这里 M[N] 通常写成 M[x:=N]，表示在M中将所有“自由出现”的 x 替换为 N 所得到的结果（事实上替换过程中 N 的表达式也可能要改变，这一点将在后面详细说明）。
形式化定义（这一节是完全的数学方式的表达，很头痛的东西，我不太能够认真地看下去，所以这部分我完全摘抄其它文章：P）
【定义1】λ-演算的字母表由以下组成：
●变元集合：Δ = {v, v', v'', v''', …}, Δ无穷
●抽象算子：λ
●括号：(, )
【定义2】λ-项的集合Λ归纳定义为满足以下条件的最小集合：
● x ∈Δ → x ∈ Λ
● M, N ∈Λ → (MN) ∈ Λ
● M ∈Λ, x ∈Δ → (λx M) ∈ Λ
若用BNF(Backus Normal Form)表示，则有
Δ ::= v | Δ'
Λ ::= Δ | (ΛΛ) | (λΔΛ)
【定义3】我们做以下约定：
● x, y, z, … 表示任意变元；
● M, N, L, … 表示任意λ项；
● M ≡ N 表示M和N语法恒同；
● 通常采用以下省略括号表示法：
(i) F M_1 M_2 … M_n ≡ (…((F M_1) M_2)…M_n) (左结合)
(ii) λx_1x_2…x_n. M ≡ (λ x_1 (λ x_2 (…(λx_n M)…) ) )
● 设 P ≡ M N_1 N_2 … N_k (k ≥ 0)，当k=0时，P ≡ M;
设 P ≡ λx_1x_2…x_k. M (k ≥ 0)，当k=0时，P ≡ M。
【定义4】设M ∈ Λ，M的长度ρ(M)被定义为M中变元出现的次数，即
● ρ(x) = 1, x ∈Δ
● ρ(MN) = ρ(M) + ρ(N)
● ρ(λx. M) = ρ(M) + 1
以后我们说对M的结构作归纳是指对M的长度ρ(M)作归纳，这是自然数上的归纳。
【定义5】设M∈Λ，对M的结构作归纳，定义M的子项集合Sub(M)如下：
● Sub(x) = {x} , x ∈Δ
● Sub(N_1 N_2) = Sub(N_1) ∪ Sub(N_2) ∪ { N_1N_2 }
● Sub(λx.N ) = Sub(N) ∪ {λx.N }
若N ∈ Sub(M)，则称N为M的子项。
例如：y为 λx.yy 的子项，但是x不是 λx.yy 的子项。
【定义6】设M ∈Λ，
● M 的自由变元集合 FV(M) 归纳定义如下：
FV(x) = {x}
FV(N_1N_2) = FV(N1) ∪ FV(N_2)
FV(λx.N ) = FV(N) - {x}
● 若x出现于M中，且x不属于FV(M)，则称x是约束的。
● 若FV(M)为空集，则称M为闭λ-项（或组合子），且记全体闭λ-项的集合为 Λ* 。
例如 M ≡ λx. yxy ，则其中x 是约束变元，y是自由变元。N ≡ λxy. yxy 是一个闭λ-项。
事实上约束变元和自由变元的概念在数学的其他领域也出现过，例如在微积分中
∫(3xy+x-y) dx
这里dx其实就表明在3xy+x-y中x是约束变元。
【定义7】上下文(Contexts)
λ上下文集合C[]定义为满足下列条件的最小集合：
● x ∈C[]
● [] ∈ C[]
● C_1[], C_2[] ∈ C[] → (C_1[]C_2[]) ∈ C[]
● C_1[] ∈ C[] → (λx. C_1[]) ∈ C[]
上下文中的空白用一个[]表示。引入上下文的概念是为了方便以后的讨论。
例如
C_1[] = (λx. []x) M
则
C_1[λy.y] = (λx. (λy.y) x) M
换句话说，C_1[N] 就是把 C_1[] 中的 [] 出现的地方都填入 N。这种填入替换和前面说的 M[x:=N] 不同，M[x:=N] 要把M中所有自由出现的x替换成N， 并且N本身可能也会适当地改变。但是C_1[N]的替换则是把所有的[]都换成N，且N不做任何改变。
另外需要注意的是，FV[M]中的变元在 C[M] 中可能会变成约束变元。
lambda演算的公理化系统
形式理论λβ由以下的公理和规则组成。这7条规则是lambda演算中最重要的部分，体现了演算的逻辑性和机械性。我们可以把lambda的函数看作是一 个有机体，这些规则就类似于有机体中分子与分子结合的方式，有机体通过这些组合方式可以无限的繁衍，并且无论如何繁衍，最终都还是这种有机体。因此，对于 一个可计算的问题，无论它有多么困难，理论上都有一个足够长的函数能够把它表示出来。
公理：
(ρ) M ＝ M
(β) (λx. M) N = M[x:=N]
规则：
M = N
(σ) ---------------
N = M
M = N, N = L
(τ) ---------------
M = L
M = N
(μ) ---------------
ZM = ZN
M = N
(ν) ---------------
MZ = NZ
M = N
(ξ) ---------------
λx.M = λx.N
公式 M = N 在λβ中可记为λβ|- M = N，有时简记为 M = N，
这时称M可β转换于N。
上面的公理和规则的名称来源于 Curry[1958]。
β变换
β替换有两个基本原则：
1。M[x:=N] 只能把M中自由出现的x替换为N；
2。原来在N中自由出现的变元，在M[x:=N] 的结果中也应该保持自由。
下面将分别对这两个原则进行描述。
1。M[x:=N] 只能把M中自由出现的x替换为N
上述公理系统中的β公理其实就是λ演算中的作用（Application）过程。从计算机程序设计的角度来看，任何一个λ项都可以看作是一段子程序，λx. M 就表示该子程序的输入参数是x，而 (λx. M) N 则表示把N作为参数x带入到子程序M中进行计算。M本身的语法形式描述了M的计算过程，因而只需要把M中所有“自由出现”的x替换成N即可得到计算结果。注意，这里一直强调要替换“自由出现”的x，下面我们举一个例子来说明这一点。
假设我们已经在λ演算中定义了加减乘除运算，设
L ≡ λx. (y + x)
M ≡ L (x * x)
则
(λx. M) t ≡ (λx. L(x*x) ) t
≡ (λx. (λx. (y + x)) (x*x) ) t
= (λx. (y + x))(t*t)
= y + t*t
注意其中第一个＝号处不能把(λx. (y + x))中的x替换成t，因为(λx. (y + x))中的x是约束的，如果把(λx. (y + x))中的x也换成t的话，将得到
(λx. M) t ≡ (λx. (λx. (y + x)) (x*x) ) t
= (λx. (y + t)) (t*t)
= y + t
在计算第二个等号的时候约束变元x在 (y + t)中没有出现，所以实际上并没有做任何替换，只是简单地浪费掉一个参数(t*t)，最后得到结果y+t。但这个替换的结果并非我们所希望的。
从程序设计的角度来看，λx. M 相当于一段子程序，"λx."说明了子程序M的输入参数是x，M中除了x以外的其他自由变量都相当于子程序中的全局变量。
因此在λ演算中规定 M[x:=N] 只能把M中“自由出现”的x换成N。
2。原来在N中自由出现的变元，在M[x:=N] 的结果中也应该保持自由（俺不懂PASCAL，所以这里完全照抄了）
请看下面的例子：设
L ≡ y + x
M ≡λy. L ≡ λy. (y + x)
则
(λx.M)y = M[x:=y] ≠ λy. y + y
我们还是用PASCAL语言为例来说明这点。
M就相当于以下的函数（在下面例子中我们扩展一下PASCAL的语法，让其函数返回值也可以为一个函数）：
program Example_2;
var
y, z: integer;
function M(x: integer): function; // M的返回值也是一个function
function L(y: integer): integer; // L是M的子函数
begin
L := y + x;
end;
begin
M := L;
end;
begin
readln(y, z);
writeln( M(y)(z) );
end.
上面例子中M的返回值也是一个function，因此M(y)得到的是一个函数，M(y)(z)得到的才是一个函数值。
上述程序的正确输出应该是z+y。在调用了M(y)以后，函数M返回的是一个函数L，且因为L是M的子函数，L中的x就是M的参数x，他的值应该等于y，不过L本身的参数名字也叫做y，如果不加区分就会搞混淆。一种错误的计算过程如下：先计算M(y)，得到一个函数
function L(y: integer): integer;
begin
L := y + y;
end;
然后计算L(z)，得到z+z。这个结果是错误的，这就是对局部变元和全局变元不加区分的结果。
当然如果让计算机来执行这个程序它是不会搞错的，因为编译器采用了一个叫做“名字空间”的方法，每个变元名前面都会加上名字空间。具体而言，在编译器看来，函数M应该是下面这个样子的
function M(M_x : integer): function;
function M_L(M_L_y: integer): integer;
begin
M_L := M_L_y + M_x ;
end;
begin
M := M_L;
end;
计算机计算M(y)(z)的时候，先计算M(y)，得到一个函数
function M_L(M_L_y: integer):integer;
begin
L := M_L_y + y
end;
然后计算 M_L(z)，得到 z + y。这个结果是正确的。
其实编译器所采用的这个方法就是把函数中所有出现过的变元名，函数名都加上一个前缀，这个前缀是这个函数本身的名字空间。主程序的名字空间就是空字符串， 主程序的子函数M的名字空间就是"M_"，M的子函数L的名字空间是L的父函数M的名字空间加上L自己的名字，即"M_L_"。这样就永远不会出现局部变 元和全局变元同名的问题了。
不过作为程序员来说，为了让程序更便于理解，需要自己来手工地给函数L的参数改名。例如可以把M改为下面的形式
function M(x: integer): function;
function L(y1: integer): integer; // 把L的参数命名为y1
begin
L := y1 + x;
end;
begin
M := L;
end;
这样在计算M(y)(z)的时候就不会搞错了。
下面我们回到λ演算中来。在λ演算中也会有这种问题。
设
L ≡ y + x
M ≡λy. L ≡ λy. (y + x)
则
(λx.M)y = M[x:=y] ≡ (λy. (y + x))[x:=y] ≠ λy. y + y
这就和刚才的计算过程一样，如果不做任何处理地直接将(λy. (y + x))中的x换为y，则会导致原来自由的y在替换后变为约束的，这就产生了错误。
原来自由出现的变元在β替换以后变成了约束的，这种现象就叫做“variable capture”。
解决“variable capture”的方法也和程序设计中一样，只要把M中的约束变元y改一个名字就可以了。这其实是基于这样一种思想：把函数中的参数或局部变元名字改变， 函数的功能仍然保持不变。但在λ-演算，我们需要把这种思想形式化地定义出来。在Curry的著作以及其他一些λ-演算的著作中，公理
(α) λx.M = λy. M[x:=y] 这里y不出现于M中
被加入形式理论λβ中。这条α公理就是为了处理变元改名而引入的。
Thursday, October 4, 2007
[zz]Linux文件系统的桌面应用
原文链接
本文中要介绍一个所谓的"Linux 文件系统的守护神"，这是指一个能实时地观察 Linux 文件系统的变化情况的程序模块。能够实时的观察文件系统的变化情况，并做出及时的适当的反应，这对于应用 Linux 做桌面计算机系统来说，是十分的有趣，也是十分的重要的。本文还要介绍 Linux 文件系统的异步 I/O 的扩展。同样，这对于 Linux 系统的桌面应用也是关键的。
本文中要介绍一个所谓的"Linux 文件系统的守护神"，这是指一个能实时地观察 Linux 文件系统的变化情况的程序模块。能够实时的观察文件系统的变化情况，并做出及时的适当的反应，这对于应用 Linux 做桌面计算机系统来说，是十分的有趣，也是十分的重要的。本文还要介绍 Linux 文件系统的异步 I/O 的扩展。同样，这对于 Linux 系统的桌面应用也是关键的。
传 统的 Linux 文件系统呈现给用户程序的界面，确实是十分的干净利落。用户程序可以打开一个文件，向文件中线性的写入数据，从文件的某一位置开始，线性的读出数据，关闭 一个文件，删除一个文件，创建一个文件，等等。请看，只有这么若干个简洁的操作原语，可是却能提供这么多丰富的应用。但是，我们注意到，用于访问 Linux 的文件系统的这些操作原语，并没有提供非常复杂的加锁解锁的功能。这是一件很奇妙的事情，如果来自不同的用户程序的请求发生了冲突怎么办呢？
我 们不妨走的再靠近一点，仔细的看看删除一个文件是怎样进行的。如果已经有一个用户程序在访问一个文件，而另外一个用户程序正好要删除这一个文件，这时会发 生些什么呢？我们知道，Linux 的文件系统是基于所谓的 inode 的，每个文件都相伴有一个 inode。在 inode 中记录了关于这个文件的一些系统信息，比如文件的所有者，文件相关的一些权限记录，关于文件的若干个时间戳，等等。在内存中的 inode 还维持着一个关于自己的使用计数。每当一个 inode 所代表的文件被打开一次，这个 inode 就把关于自己的使用计数加一。每当这个 inode 所代表的文件一被关闭，这个 inode 就把关于自己的使用计数减一。当用户程序删除一个文件的时候，相关的系统调用很快就返回到这个用户程序，告诉它，相应的文件已经被删除了。但是相应的 inode 还是保留在系统中，inode 首先要检查自己的使用计数，如果使用计数为零，那么 Linux Kernel 才可以真正的去删除这个文件。如果使用计数大于零，也就是说，还有其它的用户程序在访问这一个文件，那么 Linux Kernel 需要等待这些其他的用户程序一个个都完成对这一个文件的访问才行。也就是说，要等到这个 inode 的使用计数掉到零，才能真正的去删除这一个文件。
我们可以设想一下，如果有一个 MP3 播放程序在播放一首 MP3 音乐，我们觉得它不好听，就到硬盘上找到这个文件，把它 rm 掉了。这时候，MP3 播放程序并不受到影响，还是可以继续播放这首 MP3 音乐，虽然这时候在文件系统上用 ls 已经找不到这个 MP3 音乐文件了。实际上，一直要到 MP3 播放程序停止播放这首 MP3 音乐，然后 Linux 文件系统才真正的从硬盘上删除这个 MP3 文件。这个经验和我们在 Windows 平台上遇到的截然不同。
在 Windows 平台上，当我们试图在文件夹窗口中用鼠标点击右键菜单删除 Winamp 正在播放的一首 MP3 音乐的时候，Windows 系统会用一个弹出对话框告诉我们，这个文件正在被使用，没办法删除。Windows 系统的关于删除文件的这样一个解释，如果使用不当的话，会带来一个滑稽可笑的问题。我们可以设想一下，用户的一个 P2P 的文件共享程序提供了一个 MP3 文件以供别人下载，恰巧这个 MP3 音乐文件十分的热门，不断的有人来下载，这个用户最终决定要节省一下带宽，想要把这个 MP3 音乐文件删除掉，但是 Windows 系统却不允许用户这样做，因为这个 P2P 的文件共享程序总是在使用这个 MP3 文件。用户要想删除这个文件，不得不先把 P2P 的文件共享程序给停下来！呵呵。
但是 Linux 的文件系统的操作原语也有它自己的问题。我们知道，在一个 Linux Shell 的命令行上，先 rm，然后再 ls，非常的干净，被 rm 的文件没有了，被删除了。但是我们可以设想有一个图形界面的文件管理程序，当用户从 Shell 的命令行上 rm 掉一个文件的时候，这个图形界面的文件管理程序并没有收到任何人发给它的任何消息，它还以为什么都没有发生，被删除掉的文件还在那儿。这实在是很 U.G.L.Y. 啊。
那么要想解决这个问题，一个明显的但是非常不好的办法，就是让一个后台进程 Daemon 每隔一个很短的时间间隔，就检查一下文件系统上这个目录的情况，看看有没有发生什么变化。这个办法的缺点真的是显而易见的，不但系统的性能受到影响，而且它的反应也还不是实时的。
如 果我们需要用户程序能够实时地了解文件系统上某一个目录的变化情况，从实时这个角度出发，显然，我们需要有一个中断机制。我们都知道，硬件中断能够实时地 把系统某一个部件的情况反映给中央处理器，同样的，要想把位于系统内核中的文件系统的情况实时地反映给用户程序，我们也需要一个由操作系统内核到达用户进 程的软件中断机制。熟悉 Linux 系统编程的读者朋友们立即就会想到，这个中断机制在 Linux 系统中早已就有了，这就是信号传递 signal。
找到了信号传递这样一个中断用户进程的机制，一切似乎都已齐备，看来可以动手实现这样一个 Linux 文件系统的守护神，来实时地监视文件系统的变化情况，并且及时地把消息通知给用户程序了。不过且慢，让我们搜索一下 Linux Kernel，看看是否有别人也在做同样的工作。哈哈，果不其然，原来这样一个实时地监视文件系统情况的机制早已在 Linux 内核中实现了。下面一段就是取自 Linux Kernel 文档的一段小小例程，说明了 Linux Kernel 中的 dnotify 功能的用法。dnotify 就是指 directory notification，监视文件系统上一个目录中的情况。
#define _GNU_SOURCE /* needed to get the defines */ |
上面这一小段例程，对于熟悉 Linux 系统编程的读者朋友们来说，是很容易理解的。程序首先注册一个信号处理例程，然后通知 Kernel，我要观察 fd 上的 DN_MODIFY 和 DN_CREATE 和 DN_MULTISHOT 事件。（关于这些事件的详细定义，请读者朋友们参阅文后所列的参考资料。） Linux Kernel 收到这个请求后，把相应的 fd 的 inode 给做上记号，然后 Linux Kernel 和用户应用程序就自顾自去处理各自的别的事情去了。等到 inode 上发生了相应的事件，Linux Kernel 就把信号发给用户进程，于是开始执行信号处理例程，用户程序对文件系统上的变化也就可以及时的做出反应了。而在这整个过程中，系统以及用户程序的正常运行 基本上未受到性能上的影响。这里还需要说明的是，dnotify 并没有通过增加新的系统调用来完成它的功能，而是通过 fcntl 来完成任务的。增加一个系统调用，相对来说是一个很大的手术，而且如果设计不当，处理得不好的话，伤疤会一直留在那里，这是 Linux Kernel 的开发者们所非常不愿意见到的事情。
  |
|
对 于桌面计算机系统来说，能够快速的响应用户的请求，这也是十分关键的。换句话说，当用户移动鼠标的时候，不管系统正在进行什么天大的、重要的、神圣的、不 可打断的工作，它都得立即停下，并且要让鼠标立即流畅的在计算机屏幕上完美地运动起来。对于习惯在传统的 Linux 命令行上工作的读者朋友们来说，让鼠标能够在任何时间都可以在计算机屏幕上向无头苍蝇一样地乱窜，竟然被当成是最重要的系统任务，这实在有一点让人难以接 受。不过，当你从 Linux 命令行上转移到 GNOME 或者 KDE 这样的图形界面的用户环境的时候，鼠标被锁死，百分之百的也是会让你失去理智的。所以，还是让我们接受这一个现实，看一看如何才能增加系统的响应速度吧。
从 文件系统的角度讲，特别是考虑到网络文件系统，它的响应速度有可能会相当的慢。当用户在文件管理程序中，选择了对文件进行某一个操作以后，文件系统可能会 需要相当长的时间，才能完成这一操作。如果文件管理程序必须要等待文件系统完成这一操作，然后才能继续的话，这显然会给文件管理程序的用户带来非常不愉快 的经历。解决这一个问题的办法，就是要实现异步的文件系统 I/O。
在 Linux 的 Gnome 桌面环境中，由 GnomeVFS 包裹了真正的 Linux 文件系统 I/O，实现了一个异步的文件系统 I/O 接口 API。我们可以看到下面这个用 GnomeVFS 打开文件的例子。
enum _GnomeVFSOpenMode { |
我们注意到，上面的代码段中，用户程序为了打开一个文件，向 GnomeVFS 注册了一个 call back 例程。在注册了这一个 call back 例程之后，函数调用就立即返回给用户程序，用户程序就可以处理自己的别的事情去了，比如进一步响应来自用户的其--肭螅?鹊取６?蔽募?低惩瓿啥晕募?拇蚩?僮饕院螅�GnomeVFS 就会调用刚刚注册的 call back 例程，通知用户程序，文件已经打开。
|
|
我们在本文中了解了 Linux Kernel 中的 dnotify，可以帮助我们实时地监视文件系统目录树中的变化情况；也了解了 Gnome 桌面环境的 GnomeVFS 异步文件系统 I/O 扩展；可以帮助用户程序不至于被文件系统的请求所 Block。这两个功能对于 Linux 系统在桌面上的应用都是很重要的。
1 Stephen Rothwell, Linux Directory Notification, http://lxr.linux.no/source/Documentation/dnotify.txt
2 dnotify source, http://lxr.linux.no/source/fs/dnotify.c
3 FAM Project, http://oss.sgi.com/projects/fam/index.html
4 Ettore Perazzoli, Unix filesystem extensions in the GNOME environment, http://www.usenix.org/events/usenix2000/freenix/full_papers/perazzoli/perazzoli_html/paper.html
| ||
| 赵蔚，自由职业者，专业从事 Linux 及 Open Source 的咨询业务。 | |
Subscribe to:
Posts (Atom)