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

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

2013年10月31日 Todd 评论 97 条评论 47,482 人阅读

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

组件复用技术的局限性

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

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

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

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

…

阅读全文 Read More

( 37 人打了分，平均分： 4.11 )

二维码的生成细节和原理

2013年10月29日陈皓评论 165 条评论 393,588 人阅读

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

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

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

2013年10月09日 Leo 评论 55 条评论 65,155 人阅读

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

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

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

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

2013年10月09日 Solstice 评论 12 条评论 41,785 人阅读

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

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

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

2013年10月09日 Solstice 评论 40 条评论 66,012 人阅读

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

( 34 人打了分，平均分： 3.76 )

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

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

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

享受编程和技术所带来的快乐 – R.I.P 一路走好

Browsed by
月度归档： 2013年10月

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

2013年10月31日 Todd 评论 97 条评论 47,482 人阅读

组件复用技术的局限性

二维码的生成细节和原理

2013年10月29日陈皓评论 165 条评论 393,588 人阅读

基础知识

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

2013年10月09日 Leo 评论 55 条评论 65,155 人阅读

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

2013年10月09日 Solstice 评论 12 条评论 41,785 人阅读

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

2013年10月09日 Solstice 评论 40 条评论 66,012 人阅读

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

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