月度归档： 2013年10月 | 酷壳

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

2013年10月31日 Todd 评论 97 条评论 55,659 人阅读

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

组件复用技术的局限性

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

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

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

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

…

阅读全文 Read More

(38 人打了分，平均分： 4.13 )

二维码的生成细节和原理

2013年10月29日陈皓评论 166 条评论 429,926 人阅读

二维码又称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

(105 人打了分，平均分： 4.41 )

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

2013年10月09日 Leo 评论 55 条评论 76,087 人阅读

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

提起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

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

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

2013年10月09日 Solstice 评论 12 条评论 47,333 人阅读

（感谢网友 @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

(20 人打了分，平均分： 2.95 )

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

2013年10月09日 Solstice 评论 40 条评论 72,888 人阅读

（感谢网友 @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

(39 人打了分，平均分： 3.74 )

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

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

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

酷壳 – CoolShell

享受编程和技术所带来的快乐 – Coding Your Ambition

Browsed by
月度归档： 2013年10月

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

2013年10月31日 Todd 评论 97 条评论 55,659 人阅读

组件复用技术的局限性

二维码的生成细节和原理

2013年10月29日陈皓评论 166 条评论 429,926 人阅读

基础知识

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

2013年10月09日 Leo 评论 55 条评论 76,087 人阅读

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

2013年10月09日 Solstice 评论 12 条评论 47,333 人阅读

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

2013年10月09日 Solstice 评论 40 条评论 72,888 人阅读

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

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