酷壳 – CoolShell.cn- Part 10

程序的本质复杂性和元语言抽象

2013年10月31日 Todd 评论 97 条评论 37,505 人阅读

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

组件复用技术的局限性

常听到有人讲“我写代码很讲究，一直严格遵循DRY原则，把重复使用的功能都封装成可复用的组件，使得代码简短优雅，同时也易于理解和维护”。显然，DRY原则和组件复用技术是最常见的改善代码质量的方法，不过，在我看来以这类方法为指导，能帮助我们写出“不错的程序”，但还不足以帮助我们写出简短、优雅、易理解、易维护的“好程序”。对于熟悉Martin Fowler《重构》和GoF《设计模式》的程序员，我常常提出这样一个问题帮助他们进一步加深对程序的理解：

如果目标是代码“简短、优雅、易理解、易维护”，组件复用技术是最好的方法吗？这种方法有没有根本性的局限？

虽然基于函数、类等形式的组件复用技术从一定程度上消除了冗余，提升了代码的抽象层次，但是这种技术却有着本质的局限性，其根源在于 每种组件形式都代表了特定的抽象维度，组件复用只能在其维度上进行抽象层次的提升。比如，我们可以把常用的HashMap等功能封装为类库，但是不管怎么封装复用类永远是类，封装虽然提升了代码的抽象层次，但是它永远不会变成Lambda，而实际问题所代表的抽象维度往往与之并不匹配。

以常见的二进制消息的解析为例，组件复用技术所能做到的只是把读取字节，检查约束，计算CRC等功能封装成函数，这是远远不够的。比如，下面的表格定义了二进制消息X的格式：

…

阅读全文 Read More

(33 人打了分，平均分： 4.48 )

二维码的生成细节和原理

2013年10月29日陈皓评论 143 条评论 330,970 人阅读

二维码又称QR Code，QR全称Quick Response，是一个近几年来移动设备上超流行的一种编码方式，它比传统的Bar Code条形码能存更多的信息，也能表示更多的数据类型：比如：字符，数字，日文，中文等等。这两天学习了一下二维码图片生成的相关细节，觉得这个玩意就是一个密码算法，在此写一这篇文章，揭露一下。供好学的人一同学习之。

关于QR Code Specification，可参看这个PDF：http://raidenii.net/files/datasheets/misc/qr_code.pdf

基础知识

首先，我们先说一下二维码一共有40个尺寸。官方叫版本Version。Version 1是21 x 21的矩阵，Version 2是 25 x 25的矩阵，Version 3是29的尺寸，每增加一个version，就会增加4的尺寸，公式是：(V-1)*4 + 21（V是版本号）最高Version 40，(40-1)*4+21 = 177，所以最高是177 x 177 的正方形。

下面我们看看一个二维码的样例：

…

阅读全文 Read More

(76 人打了分，平均分： 4.58 )

伙伴分配器的一个极简实现

2013年10月09日 Leo 评论 54 条评论 48,236 人阅读

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

提起buddy system相信很多人不会陌生，它是一种经典的内存分配算法，大名鼎鼎的Linux底层的内存管理用的就是它。这里不探讨内核这么复杂实现，而仅仅是将该算法抽象提取出来，同时给出一份及其简洁的源码实现，以便定制扩展。

伙伴分配的实质就是一种特殊的“分离适配”，即将内存按2的幂进行划分，相当于分离出若干个块大小一致的空闲链表，搜索该链表并给出同需求最佳匹配的大小。其优点是快速搜索合并（O(logN)时间复杂度）以及低外部碎片（最佳适配best-fit）；其缺点是内部碎片，因为按2的幂划分块，如果碰上66单位大小，那么必须划分128单位大小的块。但若需求本身就按2的幂分配，比如可以先分配若干个内存池，在其基础上进一步细分就很有吸引力了。

可以在维基百科上找到该算法的描述，大体如是：

分配内存：

1.寻找大小合适的内存块（大于等于所需大小并且最接近2的幂，比如需要27，实际分配32）

1.如果找到了，分配给应用程序。
2.如果没找到，分出合适的内存块。

1.对半分离出高于所需大小的空闲内存块
2.如果分到最低限度，分配这个大小。
3.回溯到步骤1（寻找合适大小的块）
4.重复该步骤直到一个合适的块

…

阅读全文 Read More

(19 人打了分，平均分： 4.21 )

C++11的Lambda使用一例：华容道求解

2013年10月09日 Solstice 评论 12 条评论 33,343 人阅读

（感谢网友 @bnu_chenshuo 投稿）

华容道是一个有益的智力游戏，游戏规则不再赘述。用计算机求解华容道也是一道不错的编程练习题，为了寻求最少步数，求解程序一般用广度优先搜索算法。华容道的一种常见开局如图 1 所示。

广度优先搜索算法求解华容道的基本步骤：

准备两个“全局变量”，队列 Q 和和集合 S，S 代表“已知局面”。初时 Q 和 S 皆为空。
将初始局面加入队列 Q 的末尾，并将初始局面设为已知。
当队列不为空时，从 Q 的队首取出当前局面 curr。如果队列为空则结束搜索，表明无解。
如果 curr 是最终局面（曹操位于门口，图 2），则结束搜索，否则继续到第 5 步。
考虑 curr 中每个可以移动的棋子，试着上下左右移动一步，得到新局面 next，如果新局面未知（next ∉ S），则把它加入队列 Q，并设为已知。这一步可能产生多个新局面。
回到第2步。

其中“局面已知”并不要求每个棋子的位置相同，而是指棋子的投影的形状相同（代码中用 mask 表示），例如交换图 1 中的张飞和赵云并不产生新局面，这一规定可以大大缩小搜索空间。

以上步骤很容易转换为 C++ 代码，这篇文章重点关注的是第 5 步的实现。

…

阅读全文 Read More

(15 人打了分，平均分： 3.47 )

C++面试中string类的一种正确写法

2013年10月09日 Solstice 评论 38 条评论 55,528 人阅读

（感谢网友 @bnu_chenshuo 投稿）

C++ 的一个常见面试题是让你实现一个 String 类，限于时间，不可能要求具备 std::string 的功能，但至少要求能正确管理资源。具体来说：

能像 int 类型那样定义变量，并且支持赋值、复制。
能用作函数的参数类型及返回类型。
能用作标准库容器的元素类型，即 vector/list/deque 的 value_type。（用作 std::map 的 key_type 是更进一步的要求，本文从略）。

换言之，你的 String 能让以下代码编译运行通过，并且没有内存方面的错误。

void foo(String x)
{
}

void bar(const String& x)
{
}

String baz()
{
  String ret("world");
  return ret;
}

int main()
{
  String s0;
  String s1("hello");
  String s2(s0);
  String s3 = s1;
  s2 = s1;

  foo(s1);
  bar(s1);
  foo("temporary");
  bar("temporary");
  String s4 = baz();

  std::vector<String> svec;
  svec.push_back(s0);
  svec.push_back(s1);
  svec.push_back(baz());
  svec.push_back("good job");
}

…

阅读全文 Read More

(28 人打了分，平均分： 4.07 )

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

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

（感谢 @文艺复兴记（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

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

数据即代码：元驱动编程

2013年08月09日 Todd 评论 77 条评论 46,356 人阅读

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

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

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

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

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

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

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

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

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

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

1. getopt()：

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

…

阅读全文 Read More

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

数据的游戏：冰与火

2013年07月31日陈皓评论 124 条评论 67,620 人阅读

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

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

数据挖掘中的三种角色

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

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

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

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

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

…

阅读全文 Read More

(66 人打了分，平均分： 4.68 )

7个示例科普CPU Cache

2013年07月30日 Leo 评论 69 条评论 88,650 人阅读

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

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

(42 人打了分，平均分： 4.31 )