Browsed by
月度归档: 2013年10月

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

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

(感谢 @文艺复兴记(todd) 投递此文)

组件复用技术的局限性

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

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

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

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

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (38 人打了分,平均分: 4.13 )
Loading...
二维码的生成细节和原理

二维码的生成细节和原理

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

好烂啊有点差凑合看看还不错很精彩 (103 人打了分,平均分: 4.40 )
Loading...
伙伴分配器的一个极简实现

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

(感谢网友 @我的上铺叫路遥 投稿)

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

好烂啊有点差凑合看看还不错很精彩 (32 人打了分,平均分: 3.78 )
Loading...
C++11的Lambda使用一例:华容道求解

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

(感谢网友 @bnu_chenshuo 投稿)

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

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

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

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

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

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (20 人打了分,平均分: 2.95 )
Loading...
C++面试中string类的一种正确写法

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

(感谢网友 @bnu_chenshuo 投稿)

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

  1. 能像 int 类型那样定义变量,并且支持赋值、复制。
  2. 能用作函数的参数类型及返回类型。
  3. 能用作标准库容器的元素类型,即 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

好烂啊有点差凑合看看还不错很精彩 (38 人打了分,平均分: 3.71 )
Loading...
C++模板”>>”编译问题与词法消歧设计

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

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