贪玩的程序员

Sed单行脚本学习笔记 redraiment, 2009-12-31 回家真好 　　前段时间忙着找工作、项目结题、写报告……反正是总有做不完的事情，哈哈。好在暂时告一段落了，应老妈强烈要求回家休息几天。这次回家除了这身衣服，只带了一本《 sed与awk 》，我觉得这种小册子最适合茶余饭后休闲之用。如果你也有兴趣学 sed ，推荐你一起看《 sed与awk 》（可以在 谷歌图书 在线阅读英文版:D）。 　　花了两天时间，看完了前面 sed 的部分。要掌握一个工具就要熟悉它的规则，man 等参考手册向我们介绍这些规则，教程则演示如何使用这些规则，但要将这些规则运用自如，还需要去理解别人的代码并尝试自己解决问题。在 SourceForge 上有份经典的文档：《 SED单行脚本快速参考 》（单行脚本要求命令行长度小于65个字符），由 Eric Pement 整理， Joe Hong 翻译，通篇阅读后获益良多，故撰此文和大家分享。 精彩脚本摘录 # 在每一行后面增加一空行 sed G 　　在参考手册中，命令G的作用是“将换行符后的保持空间内容追加到模式空间”。就像前文提到的，看过教程后只是熟悉了规则，还不能将规则运用自如，我自己写的代码是：sed 's/$/\n/'，就是因为我还不熟悉每个命令会对模式空间产生什么影响。所以看到这段参考代码时感觉眼前一亮：“原来还可以这样写！” # 显示文件中的最后10行 （模拟“tail”） sed -e :a -e '$q;N;11,$D;ba' 　　假设文件有 N 行（N 大于10），显示最后10行也就意味着删除前的 N-10 行。在多行模式中，命令“D”可以删除模式空间中第一行；命令“N”可以将下一行追加到模式空间中，建立多行模式。因此问题转化为：“1)将整个文件的内容放入一个模式空间中；2)删除前 N-10 行。”其中问题1)通过控制语句“b”来解决：sed ':a; N; ba'；至于问题二，模式“1,$”代表文本中的所有行，因此紧跟着的命令被执行N次，同理，模式“11,$”匹配后面的 N-10 行，因此“11,$D”一个执行了 N-10 次。 　　其实，在 GNU sed 中，命令“$q”是可以删掉的，因为在最后一行执行命令“N”就会因出错而自动退出。 　　另外，在

戏说C语言变量 redraiment, 2009-12-18 好玩的问题 　　今早帮老师去答疑，一位同学跑来问：“使用 printf 输出 %d、%c 时，后面传的参数都是变量的值，为什么 %s 看起来和它们不一样，要传一个地址？”我说：“小伙子很有前途，一般人不问这样的问题，哈哈！” 　　这个问题类似 Java 中基础类型传递值、对象传递引用，这么设计是为了提高效率。对于还没学完C语言的初学者来说，如果我给他扯一堆“底层设计”或“效率”等显然不合适，还极有可能掉进“值传递还是址传递”等文字游戏漩涡中，估计到了最后也只能在他听得晕头转向时搪塞一句“当初就是这么设计的”。为了尽快得给他满意的答复，我只要想办法让 %s “看起来”和其他标记一样就行了，于是写了如下的代码： #include <stdlib.h> #include <stdio.h> typedef char STRING[80]; int main ( void ) {     STRING s = "redraiment";     int i = 1;     printf("%s, %d\n", s, i);     return EXIT_SUCCESS; } 　　然后我告诉他：“因为C语言不够抽象，让你知道了太多的底层实现细节，比如你知道字符串在内存中是以字符数组的形式保存的。现在我用 typedef 定义了一个字符串类型，把这些细节屏蔽掉。通过 STRING s; 来定义一个名字是 s 的字符串类型变量，这样就和用 double d; int i; 等方式定义变量一样，你无需了解它们在内存中如何实现。此时，对于 printf 来说，%s、%d 后面跟着的 s, i 都是一回事了，它们都是变量的名字，里面保存着不同类型的数据。”很幸运，前面的话解决了他的疑惑，让我剩下不少口水:P。 指针和数组的定义是个BUG 　　我初学C语言时，也有过类似的困惑：指针和数组别样的定义方式让我以为它们有别于普通类型。所有普通类型、自定义的结构体类型的定义方式都是 TYPE name，数据类型后面紧跟着变量名。因此，就理论上来说，你定义一个指针 int* pi，其中表示指针类型的“*”应该从属于 int。但很遗憾，实际上它

好玩的数学——吉普赛读心术解密 redraiment, 2009-11-19 神奇的吉普赛读心术 　　闲着无聊窜寝室，看到一个同学在玩一个 flash 游戏：吉普赛读心术（ http://gb.cri.cn/mmsource/flash/2006/04/10/er060410001.swf ）。规则如下： 任意选择一个两位数（或者说，从10~99之间任意选择一个数），把这个数的十位与个位相加，再把任意选择的数减去这个和。例如：你选的数是23，然后2+3=5，然后23-5=18 在图表中找出与最后得出的数所相应的图形，并把这个图形牢记心中，然后点击水晶球。你会发现，水晶球所显示出来的图形就是你刚刚心里记下的那个图形。 　　咋看之下觉得很神奇，但仔细把玩两三回后你就会发现其中的奥秘： 右边的图标每次都会改变； 9、18、27、...、81 这9个图标永远是一样的。 　　假设你选择的两位数是 ab（即 ab=a×10+b），其中 1≤a≤9, 0≤b≤9 。按照规则计算就是 (a×10+b)-(a+b)=9×a，结果是 9 的倍数，∵ 1≤a≤9 ∴ 结果为 9、18、27、...、81 中的任意一个。又∵ 这9个图标是一样的，∴ 水晶球神奇地知道你记的图标。 手指计算器 　　无独有偶，记的小学数学课上老师教我们用手指计算任意两个5-10之间的数的积。 　　例如 6×8 ，一只手伸出 6-5=1 根指头，另一只手伸出 8-5=3 根指头。1+3=4，4 就是积的十位数；把两手弯曲的指头数相乘得 4×2=8，8 是积的个位数。则 6×8=48。 　　道理和上面相同：a×b=[(a-5)+(b-5)]×10+(10-a)×(10-b) 神秘的失踪 　　做这道题一定要的亲自动手才有滋味！否则就会像浮光掠影，印象不深。 　　将一个正方形分割成 7×7=49 的小方格，并按下图将它们分为“甲、乙、丙、丁、戊”五部分。 　　然后，甲块不动、乙块和丙块对调、戊块上移、丁块右移。得到新图如下： 　　经过这样重新组合拼成的新正方形，中间奇迹般地空出了一个洞！ 　　实际上这只不过是一个小戏法，上面的新图形并不是真的正方形。 观察原始图可知 △ABC 和 △AED 是相似三角形 ∴ DE:CB=AD:AC=4:7 ∴ DE=8/7 ∴ EF=DE+DF=36/7 ∴ 上图

环境驱动编程——参加算法论坛后有感 redraiment, 2009-11-07 现场回顾 　　我很荣幸地作为特邀专家入京参加 CSDN 主办的 SD2.0 大会。大会以“移动+嵌入+云”为主题，举办了三天。白天有很多名家讲座，晚上还有5个主题沙龙，我参加的是算法论坛的沙龙。主持人是王尧（左轻侯），曾经先后工作于 Borland 中国公司和微软中国公司，现供职于 IBM 中国开发中心，从事 DB2 的研发工作。与会的还有五位嘉宾： 王炜：北京南天软件有限公司总架构师； 宋兴烈：起步软件公司总工程师； 云风：网易公司技术研发经理； 贾自艳：腾讯搜索技术研发中心研究员； 顾森：北大在校学生（ http://www.matrix67.com/ ）。 　　论坛围绕“在新一轮技术浪潮中，算法又重新站到了重要位置”这一话题展开讨论。本来有几个问题想和各位嘉宾讨论，但由于时间不足，加上我住处较远，只好忍痛在 21:20 出去赶班车，到家已经 23:40 了。不过收获还是不少，我结合大会上其他专家的一些观点，将其整理出来和大家分享。 算法重获重视 　　IT 行业经历了大型机时代、PC 时代、互联网时代，以及即将到来的移动终端+云计算时代。早期由于硬件的先天不足，需要靠软件后天来补；随着硬件的高速发展，一个普通的算法在十八个月以后性能就可以提升一倍，而且大部分经过高度优化的算法都被打包成类库，需要可以方便地调用；但随着互联网时代的到来，用户能够主动参与建设互联网，算法要处理的不再是几台 PC 中存储的数据，而是整个互联网中的信息。 　　引用李德毅院士的话：“ 集中统一的调度，顺序的、确定的输入，不能描述互联网的工作机理和交互机理，互联网突破了图灵机的描述范畴。 ”李院士将云计算定义为传统的“图灵计算”结合“大众计算”，“大众计算”意味着至少能处理这浩如烟海的互联网信息，因此算法也必须与时俱进。 环境驱动编程 　　在讨论中，王玮一直强调要灵活地运用算法，这个我以前提的“ 工具理论 ”不谋而合。他现场举了个例子：字符串匹配算法中，Rabin-Karp 算法理论上并非最优的，但在实际运用地比较好。这是由于硬盘的I/O效率远低于内存等高速存储器，并非理想的高效随机存储器。其他匹配算法都需要反复读取前面的数据，而 RK 算法只需按顺序从前往后以此处理，在处理大数据时避免了大量

用C语言写解释器（五）——其他一些东西 redraiment, 2009-11-05 写完解释器之后 　　这一篇文章我只想和大家侃侃编程语言的事情，不会被放到书中。因此可以天南地北地扯淡，不用像前几篇一样畏首畏尾的了。 　　经过前面几篇文章的讨论，已经把用纯 C 语言来实现一个解释器的方法介绍完了。但那些是写给我校 C 语言初学者看的，并不只是你，我得也觉得很不过瘾 ^_^。因此准备继续深入学习编译原理等课程，希望有志同道合的朋友和我一起交流！ 富饶的语言（工具） 　　在前几篇文章中一直在鼓吹我拍脑袋想出的语言四大要素：“内存管理”、“表达式求值”、“输入/输出”、“按条件跳转”，在这篇文章中您就姑且信一回当它是真的。按照这四条准则去匹配，汇编语言是完全符合的。那为什么又需要 C 语言、Java、C# 等高级语言？这是因为编程除了需要“语言”之外还需要“抽象”！ 　　“抽象”是个很有效的工具，相信你在为别人介绍自己房间时不会具体到每个木纤维、油漆分子和铁原子。同样的，我们也不乐意总是写一堆 JNZ、JMP 指令，而仅仅是为了实现 if、for、while 等控制结构。C 语言等高级语言提供的抽象的层次更高、表现力更强，允许用更少的语句描述更多的操作。感谢如此富饶的语言为我们带来不同的视角去审视这个世界。 　　高级语言相较于低级语言属于更高地抽象层次，高级语言之间的差别主要体现在适用范围上。比如一些语言适合写 WEB 程序，另一些适合做数值分析等。术业有专攻，你只需根据自己的问题来选择一门合适的语言。 什么时候需要创造新的语言 　　当我们碰到一类新的问题时，首先考虑的就是定义新的数据结构，并设计多个函数去操作它，最后将它们独立出来打包成一个类库方便在其他地方调用（比如处理图形图像的 OpenGL 库）。上面已经提过，每种语言都有它适合的领域，强行将一门语言用在它不擅长的领域中就出现冗长、繁琐的代码。自然语言也是如此：英语中有种语法叫虚拟语气，描述的是一种假设，并非事实。比如“If I have time, I will go to see you. ”。如果按原意一字不差地翻译相信会很繁琐，我知道台湾作家痞子蔡在使用中文式的虚拟语气很有一套： 如果我还能活一天， 我就要做你的爱侣。 我能活一天吗？可惜。 所以我不是你的爱侣。  ——《第一次亲密接触》 　　上面

用C语言写解释器（四）——语句分析 redraiment, 2009-11-02 语句 　　在前面的章节中已经成功实现了内存管理和表达式求值模块。之所以称表达式求值是解释器的核心部分，是因为几乎所有语句的操作都伴随着表达式求值。也许你已经迫不及待地给 eval 传值让它执行复杂的运输了，但目前来讲它充其量只是一个计算器。要想成为一门语言，还需要一套自成体系的语法，包括输入输出语句和控制语句。但在进行语法分析之前，首先需要将 BASIC 源码载入到内存中。 BASIC 源码载入 　　在《用C语言写解释器（一）》中附了一段 BASIC 参考代码，每一行的结构是一个行号+一条语句。其中行号为 1-9999 之间的正整数，且当前行号大于前面的行号；语句则由以下即将介绍的 3 条 I/O 语句和 8 条控制语句组成。为方便编码，程序中采用静态数组来保存源代码，读者可以尝试用链表结构实现动态申请的版本。下面是代码结构的定义。 // in basic_io.h #define PROGRAM_SIZE (10000) typedef struct {     int ln;     // line number     STRING line; } CODE; extern CODE code[PROGRAM_SIZE]; extern int cp; extern int code_size; 　　其中 code_size 的作用顾名思义：记录代码的行数。cp （0 ≤ cp < code_size）记录当前行的下标（比如 cp 等于5时表明执行到第5行）。下面是载入 BASIC 源码的参考代码，在载入源码的同时会去除两端的空白字符。 // in basic_io.c void load_program ( STRING filename ) {     FILE *fp = fopen ( filename, "r" );     int bg, ed;     if ( fp == NULL ) {         fprintf ( stderr, "文件 %s 无法打开！\n", filename );         exit ( EXIT_FAILURE );     }     while ( fscanf (

用C语言写解释器（三）——中缀转后缀 redraiment, 2009-11-01 操作符排序 　　如果你忘记了后缀表达式的概念，赶紧翻回上一篇《 用C语言写解释器（二） 》回顾一下。简单地说，将中缀表达式转换成后缀表达式，就是将操作符的执行顺序由“优先级顺序”转换成“在表达式中的先后顺序”。因此，所谓的中缀转后缀，其实就是给原表达式中的操作符排序。 　　比如将中缀表达式 5 * ((10 - 1) / 3) 转换成后缀表达式为 5 10 1 - 3 / *。其中数字 5 10 1 3 仍然按照原先的顺序排列，而操作符的顺序变为 - / ×，这意味着减号最先计算、其次是除号、最后才是乘号。也许你还在担心如何将操作符从两个操作数的中间移到它们的后边。其实不用担心，在完成了排序工作后你就发现它已经跑到操作数的后面了 ^_^。 　　从中缀表达式 1+2×3+4 中逐个获取操作符，依次是 + × +。如果当前操作符的优先级 不大于 前面的操作符时，前面操作符就要先输出。比如例子中的第二个加号，它前面是乘号，因此乘号从这个队伍中跑到输出的队伍中当了“老大”；此时第二个加号再前面的加号比较，仍然没有比它大，因此第一个加号也排到新队伍中去了；最后队伍中只剩下加号自己了，所以它也走了。得到新队伍里的顺序 × + + 就是所求解。下面的表格中详细展示每一个步骤。 序号 输入 临时空间 输出 1 + 2 × + 3 + + × 4 + × + 5 + + × 6 + × + 7 * + + 　　相信你心里还是牵挂着那些操作数。很简单，如果碰到的是操作符就按上面的规则处理，如果是操作数就直接输出！下面的表格加上了操作数，将输出完整的后缀表达式。 序号 输入 临时空间 输出 1 1 2 + 1 3 2 + 1 4 × + 1 2 5 3 + × 1 2 6 + + × 1 2 3 7 + × + 1 2 3 8 + + 1 2 3 × 9 4 + 1 2 3 × + 10 + 1 2 3 × + 4 11 1 2 3 × + 4 + 　　得到最终结果 1 2 3 × + 4 + 就是所求的后缀表达式。下面是程序中的参考代码（有删减）。 操作符优先级 　　上一节介绍了中缀转后缀的方法。其中关键

用C语言写解释器（二）——表达式求值 redraiment, 2009-10-31 内存管理 　　既然是表达式求值，自然需要在内存中保存计算结果以及中间值。在《 用C语言写解释器（一） 》中提过：变量要求是若类型，而 C 语言中的变量是强类型，为实现这个目标就需要定义自己的变量类型，参考代码如下（注释部分指出代码所在的文件名，下同）： // in basic_io.h #define MEMERY_SIZE (26) typedef enum {     var_null = 0,     var_double,     var_string } variant_type; typedef char STRING[128]; typedef struct {     variant_type type;     union {         double i;         STRING s;     }; } VARIANT; extern VARIANT memery[MEMERY_SIZE]; // in expression.h typedef VARIANT OPERAND; 　　程序自带 A-Z 26个可用变量，初始时都处于未赋值（ver_null)状态。所有变量必须先赋值再使用，否则就会报错！至于赋值语句的实现请参见后面语法分析的章节。 操作符 　　表达式中光有数值不行，还需要有操作符。在《 一 》中“表达式运算”一节已经给出了解释器需要实现的所有操作符，包括“算术运算”、“关系运算”和“逻辑运算”。下面给出程序中操作符的定义和声明： // in expression.h typedef enum {     /* 算数运算 */     oper_lparen = 0,    // 左括号     oper_rparen,        // 右括号     oper_plus,          // 加     oper_minus,         // 减     oper_multiply,      // 乘     oper_divide,        // 除     oper_mod,           // 模     oper_power,         // 幂     oper_positi

用C语言写解释器（一）——我们的目标 redraiment, 2009-10-18 起因 　　最近，我们学院老师联系我，希望我能提供一段用 C 语言编写的 BASIC 解释器，用于 C 语言课程设计教学。我前段时间也正好着迷于“语言”本身，本就有打算写一个解释器，这下正中我下怀，于是欣然接受。 　　以前在图书馆看过梁肇新的《编程高手箴言》，第四章“编程语言的运行机理”中就包含了一段 C 语言编写的 BASIC 解释器代码，但代码好像并不完整（我翻了好几遍，都没发现函数 get_token 的实现代码）；再者，这次的代码还有其他用处，不宜牵涉版权问题；最后的原因是我有“想自己编码”的冲动 ^_^。综上所述，我要从零开始用 C 语言来编写一个 BASIC 解释器。 前置知识 　　1. 要编写解释器，首先就要明白什么是解释器（详细的解释请参看维基百科： http://zh.wikipedia.org/zh-cn/解释器 ）。盗用《编程高手箴言》里的话： 解释程序就是一个字符串的解释器 （P165 解释语言的原理）。所以，如果仅仅是为我个人编写的话，我宁可会借助 lex & yacc 甚至 perl，而不会纯粹用 C 语言来写。 　　2. 在起因中已经提过，这个程序会在学弟学妹们学完 C 语言后作为综合实验。因此需要你熟悉 C 语言的语法、单链表添加/删除节点等操作以及栈的概念（这些内容大部分都能在 C 语言的教材中找到），一些相对冷僻的技术（例如 setjmp/longjmp）则不会出现在程序中。 关于语言 　　我在《 编程和语言之我见 》一文中提过，编程是一个很宽泛的概念。从某种意义上来说所有的软件都是一种特定的语言，但根据程序本身的灵活性可以分为“硬编码”、“可配置”、“可控制”和“可编程”四类（详见《 四类程序 》）。如果一个程序的灵活性达到了“可编程”，它的配置文件就可以被看作一种“编程语言”，而该程序本身也就是一个“解释器”。 　　要做到“可编程”，程序至少应该具备“输入/输出”、“表达式运算”、“内存管理”和“按条件跳转”四个功能（详见《 用DOS批处理来做数字图像处理 》）。这正好对应了冯·诺依曼计算机的结构：以运算器和控制器为中心，输入/输出设备与存储器之间的数据传输都要经过运算器。下面

庆中秋：用Windows XP桌面图标玩贪吃蛇（原理） redraiment, 2009-10-04 到处都有好玩的玩意儿 　　计算机的世界里离散的：内存从 0 -> 2n 编号；整个屏幕的画面也是由许多颗像素点组成……如果你不介意的话，把脸尽量地贴近显示器（或者电视屏幕），你会看到整个屏幕是由一颗颗显示不同颜色的小颗粒拼成的。如果这样感受还不深，那你还记得小时候玩过的最初型掌上游戏机吗？如下图： 　　其中经典的飞机、坦克、俄罗斯方块等都是由一个个正方形的黑色方块拼成的。 　　放眼周边的世界，到处都有这样规则排列的、方方正正的“游戏元素”：摩天大楼的窗户、大教堂的座位、从楼上往下看的人群……当然还有今天要介绍的桌面图标！在优库上一搜索就会出现很多结果，有用寝室楼电灯玩贪吃蛇的、也有军训时集体玩 AK47 阵列的等等，原理都是这样～ 　　在看完这篇文章后，你也可以尝试照样画葫芦，比如开启很多个“记事本”，将他们的窗口调整成四四方方的，然后用它们玩俄罗斯方块。 ^_^ 程序原理 　　我在优库上发布了视频——用 Windows XP 桌面图标玩贪吃蛇（视频地址为  http://v.youku.com/v_show/id_XMTIyODk2Njky.html ），一些朋友在评论中猜测程序原理：有人说是用批处理，还有人说是用汇编，甚至有人直接否定说是我用静态帧拼接起来的，呵呵。其实没大家想的这么复杂，我的程序主要是用 VB 开发的（为方便以后使用，移动桌面图标的代码用 C 语言写，并打包成 DLL 文件。程序的核心语句就是下面这句话： SendMessage ( hwnd, LVM_SETITEMPOSITION, i , MAKELPARAM( x , y ) ); 　　 SendMessage 是系统调用，可以向指定的窗口发送消息。整条语句的作用是向桌面发送消息，请求将第“ i ”个图标移动到坐标“ x,y ”位置。下面按照视频里播放的顺序依次介绍原理： 一、创建文件 　　在视频的最开始，我开启了一个命令提示符执行一条命令。可能正是因为这个原因让大家误以为这个程序是用批处理写的。如果你看了我上次的高清AVI版视频，就知道我命令是：“ for /l %d in (1,1,16) do echo. >%d.txt ”。正如网友“ Sypeace

迎国庆，DuplexPipe 发布 0.3.0 版 redraiment, 2009-10-01 　　今天是中华人民共和国建国六十周年，普天同庆！作为一个程序员，当然是努力工作报效祖国啦～特地抽空完善 DuplexPipe ，主要更新如下： 实现了 UDP 通信模式； 增加了对多语言的支持，Download 中提供中文版，你还可以通过源码自行编译英文版； 修正了一些 v0.1.0 中的小错误。 　　最新版的源码以及 JAR 包请到项目主页（ http://code.google.com/p/duplexpipe/ ）下载。有了 UDP 模式，现在连接模式一共有以下四种： TCP 监听模式 TCP 连接模式 UDP 监听模式 UDP 连接模式 　　根据两个连接模式排列，可以得到 4×4=16 种模式。由于类似“ TCP 监听模式 -  TCP 连接模式”和“ TCP 连接模式 - TCP 监听模式”等模式属于同一种，排除重复项后总共剩下以下十种模式： TCP  监听模式 -  TCP  监听模式 TCP  监听模式 -  TCP  连接模式 TCP  监听模式 -  UDP  监听模式 TCP  监听模式 -  UDP  连接模式 TCP  连接模式 -  TCP  连接模式 TCP  连接模式 -  UDP  监听模式 TCP  连接模式 -  UDP  连接模式 UDP  监听模式 -  UDP  监听模式 UDP  监听模式 -  UDP  连接模式 UDP  连接模式 -  UDP  连接模式 　　到这里还没有结束。我们知道 UDP 属于非安全连接，通讯之前没有经过三次握手确认。因此在“ UDP 连接模式端”发送数据包到“ UDP 监听模式端”之前，“监听端”并不知道“连接端”的位置，所以也就无法主动给“连接端”发送数据。而我们的 DuplexPipe 只是一个数据转发工具，本身并不向两端程序发送任何多余的信息。因此第十种模式“ UDP 连接模式 - UDP 连接模式”并不能正常工作。于是，真正能建立通讯的模式就只剩下前面九种。我暂时想不出解决方法，如果其他朋友知道如何解决（当然不能让 DuplexPipe 主动发送冗余数据），欢迎联系我（ redraiment@gmail.com ），谢谢！ 相关