酷壳 – CoolShell.cn

C++模板”>>”编译问题与词法消歧设计

2013年10月02日 Todd 评论 17 条评论 17,204 人阅读

（感谢 @文艺复兴记（todd）投递此文）

在编译理论中，通常将编译过程抽象为5个主要阶段：词法分析(Lexical Analysis)，语法分析(Parsing)，语义分析(Semantic Analysis)，优化(Optimization)，代码生成(Code Generation)。这5个阶段类似Unix管道模型，上一个阶段的输出作为下一个阶段的输入。其中，词法分析是根据输入源代码文本流，分割出词，识别类别，产生词法元素(Token)流，如：

int a = 10;

经过词法分析会得到[(Type, “int”), (Identifier, “a”), (AssignOperator, “=”), (IntLiteral, 10)]，在后续的语法分析阶段，就会根据这些词法元素匹配相应的语法规则。在我学习编译原理时，教科书中对于词法分析的介绍主要是基于正则表达式的，言下之意就是普通语言的词法规则是可以通过正则表达式描述的。比如，C语言的变量名规则是“包含字母、数字或下划线，并且以字母或下划线开头”，这就可以用正则表达式 [a-zA-Z_][a-zA-Z0-9_]* 表达。但是，在实践中我发现不管是主流语言，还是自己设计的DSL都大量存在不能简单通过正则表达式进行词法分析的例子。来看C++98的模版例子：

map<int, vector<int>>

上面这段代码会被C++98编译器中报语法错误，原因在于它把“>>”识别成了位右移运算符而不是两个模版右括号，在C++98中必须在两个括号中间加空格，写成

…

阅读全文 Read More

( 25 人打了分，平均分： 3.84 )

数据即代码：元驱动编程

2013年08月09日 Todd 评论 77 条评论 58,628 人阅读

（感谢 @文艺复兴记（todd）投递此文）

几个小伙伴在考虑下面这个各个语言都会遇到的问题：

问题：设计一个命令行参数解析API

一个好的命令行参数解析库一般涉及到这几个常见的方面：

1) 支持方便地生成帮助信息

2) 支持子命令，比如：git包含了push, pull, commit等多种子命令

3) 支持单字符选项、多字符选项、标志选项、参数选项等多种选项和位置参数

4) 支持选项默认值，比如：–port选项若未指定认为5037

5) 支持使用模式，比如：tar命令的-c和-x是互斥选项，属于不同的使用模式

经过一番考察，小伙伴们发现了这个几个有代表性的API设计：

1. getopt()：

getopt() 是libc的标准函数，很多语言中都能找到它的移植版本。

…

阅读全文 Read More

( 58 人打了分，平均分： 4.03 )

数据的游戏：冰与火

2013年07月31日陈皓评论 127 条评论 82,554 人阅读

我对数据挖掘和机器学习是新手，从去年7月份在Amazon才开始接触，而且还是因为工作需要被动接触的，以前都没有接触过，做的是需求预测机器学习相关的。后来，到了淘宝后，自己凭兴趣主动地做了几个月的和用户地址相关数据挖掘上的工作，有一些浅薄的心得。下面这篇文章主要是我做为一个新人仅从事数据方面技术不到10个月的一些心得，也许对你有用，也许很傻，不管怎么样，欢迎指教和讨论。

另外，注明一下，这篇文章的标题模仿了一个美剧《权力的游戏：冰与火之歌》。在数据的世界里，我们看到了很多很牛，很强大也很有趣的案例。但是， 数据就像一个王座一样，像征着一种权力和征服，但登上去的路途一样令人胆颤 。

数据挖掘中的三种角色

在Amazon里从事机器学习的工作时，我注意到了Amazon玩数据的三种角色。

Data Analyzer：数据分析员 。这类人的人主要是分析数据的，从数据中找到一些规则，并且为了数据模型的找不同场景的Training Data。另外，这些人也是把一些脏数据洗干净的的人。

Research Scientist：研究科学家 。这种角色主要是根据不同的需求来建立数据模型的。他们把自己戏称为不近人间烟火的奇异性物种，就像《生活大爆炸》里的那个Sheldon一样。这些人基本上玩的是数据上的科学

Software Developer ：软件开发工程师 。主要是把 Scientist 建立的数据模型给实现出来，交给Data Analyzer去玩。这些人通常更懂的各种机器学习的算法。

我相信其它公司的做数据挖掘或是机器学习的也就这三种工作，或者说这三种人，对于我来说，

…

阅读全文 Read More

( 71 人打了分，平均分： 4.46 )

7个示例科普CPU Cache

2013年07月30日 Leo 评论 73 条评论 106,759 人阅读

（感谢网友 @我的上铺叫路遥 翻译投稿）

CPU cache一直是理解计算机体系架构的重要知识点，也是并发编程设计中的技术难点，而且相关参考资料如同过江之鲫，浩瀚繁星，阅之如临深渊，味同嚼蜡，三言两语难以入门。正好网上有人推荐了微软大牛Igor Ostrovsky一篇博文 《漫游处理器缓存效应》 ，文章不仅仅用7个最简单的源码示例就将CPU cache的原理娓娓道来，还附加图表量化分析做数学上的佐证，个人感觉这种案例教学的切入方式绝对是俺的菜，故而忍不住贸然译之，以飨列位看官。

原文地址： Gallery of Processor Cache Effects

大多数读者都知道cache是一种快速小型的内存，用以存储最近访问内存位置。这种描述合理而准确，但是更多地了解一些处理器缓存工作中的“烦人”细节对于理解程序运行性能有很大帮助。

在这篇博客中，我将运用代码示例来详解cache工作的方方面面，以及对现实世界中程序运行产生的影响。

下面的例子都是用C#写的，但语言的选择同程序运行状况以及得出的结论几乎没什么影响。

示例1：内存访问和运行

你认为相较于循环1，循环2会运行多快？

int[] arr = new int[64 * 1024 * 1024];

// Loop 1
for (int i = 0; i < arr.Length; i++) arr[i] *= 3;

// Loop 2
for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

…

阅读全文 Read More

( 53 人打了分，平均分： 3.96 )

加班与效率

2013年07月24日陈皓评论 194 条评论 211,614 人阅读

微博上看到了这么一个贴子，就像以前在《腾讯，竞争力和用户体验》中批评过腾讯说自己的核心竞争力是员工加班一样，我顺着Winter的回复也批评了一下这个微博——

“ 靠加班超越对手？！劳动密集型么？我要是对手的话，我就来趁机挖人了，直接摁死你……// @寒冬winter : 当一个管理者的智慧无法衡量一支团队的产出的时候，他就会把“工时”当做最后的救命稻草，死死抱住——这是他唯一听得懂的东西了。”

然后， @玄了个澄的在微博里at我说，他在微信里看了 @Fenng 关于加班的言论，希望我评论一下。我看了一下大辉的文章，虽然写得有点散乱，但是我和他的一些观点还是很类似的，我主要在这里加强一下我的看法。

关于加班

认为加班是公司的核心竞争力，或是超越对手的手段，是一种相当 Ridiculous 的想法。这说明管理者们已经想不到自己公司的核心价值了 。

…

阅读全文 Read More

( 110 人打了分，平均分： 4.63 )

类型的本质和函数式实现

2013年07月22日 Todd 评论 32 条评论 29,268 人阅读

（感谢 @文艺复兴记 （todd）投递此文）

在上一篇文章《二叉树迭代器算法》中，我介绍了一种基于栈的二叉树迭代器实现。程序设计语言和Haskell大牛 @九瓜在看过之后评论到：

这里用了 stack 来做，有点偷懒，所以错失了一个抽象思考机会。如果我们能够理解二叉树到线性表的转换过程，完全可以把 Iterator 当作抽象的线性表来看，只要定义了关于 Iterator 的 empty, singleton, 还有 append 操作，实现二叉树的 Iterator 就变得非常直观。

“错失了一个抽象思考机会”是什么意思呢？我理解九瓜的意思是基于栈的实现虽然是正确的，但它缺乏对于迭代器类型本质的理解，不具有通用性。如果能对迭代器进行合适地抽象就可以像二叉树递归遍历一样自然地得出二叉树迭代器，甚至其他更复杂的数据结构，只要我们能写出它的遍历算法，迭代器算法都可以自然推出。

类型的本质

九瓜提到了通过empty, singleton和append操作对Iterator进行抽象，我本来打算直接根据这个思路介绍函数式的二叉树迭代器实现，但是考虑到其实首要的问题在于理解类型的本质，而并不是所有人都具备这个基础，不如先普及一下类型基础再进入具体实现。那么下面我们就先来认识一下类型到底是什么？我们先以来看看表示元素对的Pair类型，可能有人一提到Pair类型马上就会在脑海中浮现出下面的结构：

…

阅读全文 Read More

( 23 人打了分，平均分： 3.61 )

C语言全局变量那些事儿

2013年07月21日 Leo 评论 92 条评论 77,417 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

作为一名程序员，如果说沉迷一门编程语言算作一种乐趣的话，那么与此同时反过来去黑一门编程语言就是这种乐趣的升华。今天我们就来黑一把C语言，好好展示一下这门经典语言令人抓狂的一面。

我们知道，全局变量是C语言语法和语义中一个很重要的知识点，首先它的存在意义需要从三个不同角度去理解：对于程序员来说，它是一个记录内容的 变量(variable) ；对于编译/链接器来说，它是一个需要解析的 符号(symbol) ；对于计算机来说，它可能是具有地址的一块 内存(memory) 。其次是语法/语义：从作用域上看，带static关键字的全局变量范围只能限定在文件里，否则会外联到整个模块和项目中；从生存期来看，它是静态的，贯穿整个程序或模块运行期间（ 注意，正是跨单元访问和持续生存周期这两个特点使得全局变量往往成为一段受攻击代码的突破口，了解这一点十分重要 ）；从空间分配上看，定义且初始化的全局变量在编译时在数据段(.data)分配空间，定义但未初始化的全局变量 暂存(tentative definition) 在.bss段，编译时自动清零，而仅仅是声明的全局变量只能算个符号，寄存在编译器的符号表内，不会分配空间，直到链接或者运行时再重定向到相应的地址上。

我们将向您展现一下， 非static限定全局变量 在编译/链接以及程序运行时会发生哪些有趣的事情，顺便可以对C编译器/链接器的解析原理管中窥豹。以下示例对ANSI C和GNU C标准都有效，笔者的编译环境是Ubuntu下的GCC-4.4.3。

…

阅读全文 Read More

( 29 人打了分，平均分： 3.86 )

二叉树迭代器算法

2013年07月14日 Todd 评论 54 条评论 41,705 人阅读

（感谢 @文艺复兴记 （todd）投递此文）

二叉树(Binary Tree)的前序、中序和后续遍历是算法和数据结构中的基本问题，基于递归的二叉树遍历算法更是递归的经典应用。

假设二叉树结点定义如下：

// C++
struct Node {
    int value;
    Node *left;
    Node *right;
}

中序递归遍历算法：

// C++
void inorder_traverse(Node *node) {
    if (NULL != node->left) {
        inorder_traverse(node->left);
    }
    do_something(node);
    if (NULL != node->right) {
        inorder_traverse(node->right);
    }
}

前序和后序遍历算法类似。

但是，仅有遍历算法是不够的，在许多应用中，我们还需要对遍历本身进行抽象。假如有一个求和的函数sum，我们希望它能应用于链表，数组，二叉树等等不同的数据结构。这时，我们可以抽象出迭代器(Iterator)的概念，通过 迭代器把算法和数据结构解耦了 ，使得通用算法能应用于不同类型的数据结构。我们可以把sum函数定义为：

…

阅读全文 Read More

( 24 人打了分，平均分： 3.13 )

Alan Cox：大教堂、市集与市议会

2013年07月08日 Leo 评论 20 条评论 24,067 人阅读

（感谢网友 @我的上铺叫路遥 投稿）

在网上搜到的Cox大叔于1998年在开源社区写的一篇文章，当时很轰动，明眼人一看就知道是针对ESR那篇《大教堂与市集》，从中可见Alan在项目管理风格上乃至个人性格上都与ESR、Linus等人不同之处。顺便说一句，Alan现在出于“家庭原因”已经离开了Linux项目，他曾经评价Linus是 a good developer but a terrible engineer ，甚至在Google+上直接说Linus就是一a*sh**e。不管如何，两位曾经十余年里并肩战斗惺惺相惜的大牛就此分道扬镳还是惹人唏嘘。

言归正传，以下为slashdot收录的英文原文： Cathedrals, Bazaars and the Town Council 。

以下是一些我对市集模式的想法，我认为这值得分享，这种模式会教你如何完全毁掉一个自由软件项目。我还举了一个我称之为“市议会”(Town Council)效应的实例（虽然那些市议员们可不这么认为，注：此处指Linux项目开发者）。

关于软件开发人员，你必须去了解一些情况。首先要了解的是真正优秀的程序员相对来说并不普遍，不仅如此，在很多其它专业领域里“真正的程序员”和一些捣乱的家伙之间的区别要比“伟大”和“普通”之间的区别要大得多，研究表明生产效率上最好的同其余的比重是30:1。

其次，你需要了解的是一大堆妄想型码农(wannabe programmer)总是善于发表意见。其中很多人患上了一种叫做“流行性热词”(buzzword)疾病，或者对他们“非黑即白”(one true path)的思考方式有着特殊的偏执，网上很多讨论都是廉价的。

…

阅读全文 Read More

( 21 人打了分，平均分： 3.62 )

IoC/DIP其实是一种管理思想

2013年07月05日陈皓评论 66 条评论 65,202 人阅读

关于IoC的的概念提出来已经很多年了，其被用于一种面象对像的设计。我在这里再简单的回顾一下这个概念。我先谈技术，再说管理。

话说，我们有一个开关要控制一个灯的开和关这两个动作，最常见也是最没有技术含量的实现会是这个样子：

然后，有一天，我们发现需要对灯泡扩展一下，于是我们做了个抽象类：

但是，如果有一天，我们发现这个开关可能还要控制别的不单单是灯泡的东西，我们就发现这个开关耦合了灯泡这种类别，非常不利于我们的扩展，于是反转控制出现了。

就像现实世界一样，造开关的工厂根本不关心要控制的东西是什么，它只做一个开关应该做好的事，就是把电接通，把电断开（不管是手动的，还是声控的，还是光控，还是遥控的），而我们的造各种各样的灯泡（不管是日关灯，白炽灯）的工厂也不关心你用什么样的开关，反正我只管把灯的电源接口给做出来，然后，开关厂和电灯厂依赖于一个标准的通电和断电的接口。于是产生了IoC控制反转，如下图：

…

阅读全文 Read More

( 36 人打了分，平均分： 3.83 )