Code Sea
烧饼的技术乱讲
CG自学练习一：使用OpenGL绘制Koch Snowflake
28 二 2011这篇文章来源于Standford Univ.的CS148课程的第一周Assignment，作业内容是要求用基本的OpenGL的图元绘制知识来创作一些有趣的图形。
一、Knoch Snowflake介绍
我选择的是绘制鼎鼎有名的Koch Snowflake，它是最早有描述的分形图像之一，因为形状类似雪花且每一边都是基于Koch Curve而得名。从本质上来说，Koch Curve的构建可以用优美的递归形式来描述：
- 一条线段平均分成三段，
- 基于中间那条线段的位置绘制一个等边三角形，并且指向线段的外侧，
- 移除该条线段
而Koch Curve正是通过有限次地不断重复以上三步所得到的曲线，下图展示了递归0-4次时的曲线：
Iteration 0: 
Iteration 1: 
Iteration 2: 
Iteration 3: 
Iteration 4:
……
二、绘制Koch Snowflake
那么应该如何利用OpenGL的基本图元（Primitives）来绘制呢？一开始的时候我设想的是根据预期的迭代次数，找到一个通用公式，从而计算出对应的顶点坐标，然后再用GL_LINE将它们连接起来即可，但是找到这么一个公式比较困难。突然我想到了小时候玩的logo语言，利用代码控制屏幕中小乌龟的位移，它走过的地方就画出一条线，基于Koch曲线如此优美的递归定义，用这种一笔画的方式来绘制，就会非常方便。为了采用这种方法，我们需要定义下列两个绘制函数：
- draw_line用于从当前位置绘制一条长度为length的线段
- turn将改变当前画笔的方向angle_in_degrees个角度，根据图形学的惯例，逆时针（counterclockwise）方向为正
这两个方法的实现将会在下文简述
C++语言: 绘制函数// drawing functions
void draw_line(double length);
void turn(int angle_in_degrees);
有了绘制函数和Koch曲线的递归定义，要画出它来就非常简单了：
C++语言: 绘制Koch Snowflakevoid koch_curve(unsigned order, double length)
{
if ( 0 == order ) {
draw_line(length);
} else {
order -= 1;
length /= 3;koch_curve(order, length);
turn(60);
koch_curve(order, length);
turn(-120);
koch_curve(order, length);
turn(60);
koch_curve(order, length);
}
}void koch_snowflake(unsigned order, double length_of_side)
{// Assume current direction is horizontalturn(60);
koch_curve(order, length_of_side);
turn(-120);
koch_curve(order, length_of_side);
turn(-120);
koch_curve(order, length_of_side);
}
下图为7阶Koch Snowflake的绘制结果：
三、绘制函数的实现
1. draw_line的实现
为了维护当前“画笔”状态，我们需要两个全局变量：
- CURRENT_POS用于记录当前“画笔”所在的位置
- DIRECTION用于记录当前“画笔”的方向
当我们知道了线段的一个端点
以及线段的方向
，可以由该线段的长度很轻松地得到线段的另一个端点
。将这两个端点放入glBegin()和glEnd()块中即可
2.turn的实现
由于向量本身只表示长度和方向，与起始位置无关，因此要令当前“画笔”的方向向量转过一个角度，可以认为在原地旋转该角度即可，而不需要像其他图形一样需要再考虑与世界坐标系原点来回平移的变换。于是我们可以得到方向向量旋转的变换矩阵为：
至此，一个简单的绘制Koch Snowflake程序便可以工作良好了。需要注意的是，在这个程序中每一帧都需要对整个图形的坐标进行一次计算，当阶数很大时会占用很多的CPU资源，可以使用Vertex List或者vector来保存已经计算好的坐标再进行绘制。
依照着这个思路，可以很方便的绘制一些优美的图形，如：
- Spirography：http://mathworld.wolfram.com/Spirograph.html
- Variants of Koch Curve：http://en.wikipedia.org/wiki/Koch_snowflake#Variants_of_the_Koch_curve
- Space-filling Curve：http://en.wikipedia.org/wiki/Space-filling_curve
四、参考文献
[1] Koch Snowflake: http://en.wikipedia.org/wiki/Koch_snowflake
[2] OpenGL Programming Guide: http://www.amazon.com/OpenGL-Programming-Guide-Official-Learning/dp/0321552628/ref=sr_1_1?ie=UTF8&qid=1298881745&sr=8-1
[3] Neils Fabian Helge von Koch’s Snowflake” http://www.efg2.com/Lab/FractalsAndChaos/vonKochCurve.htm
重装Windows之后Grub2引导的修复
In: Linux
24 一 2011前一段因为一些意外重装了两次系统，之前Win7和Gentoo并存的和谐景象也随之远去，最近准备重返Gentoo，于是今天中午着手修复grub2。
一开始我的设想是跟着Gentoo Handbook的指示来，只是其中编译系统等步骤我都可以跳过，只需要加载好目录，安装grub2就行了，步骤如下：
mount /dev/sda3 /mnt/gentoo
接下来chroot到已经存在的系统
mount –t proc none /mnt/gentoo/proc
mount –o bind /dev /mnt/gentoo/dev
chroot /mnt/gentoo /bin/bash
env-update
因为之前已经安装过grub2，所以我这里想当然地觉得只需要把grub2安装进MBR里面去就可以了
grub-install –root-directory=/mnt/gentoo /dev/sda
接下来满心欢喜地重启电脑，"grub is loading"，一切如常，可是接下来却没有出现系统选择界面，而是grub的bash-like终端，这……
于是我慌乱了，用Live CD重启进入gentoo。一开始我以为是grub2的设置并没有挂载上去，所以把/boot/grub/grub.cfg给删除后用
grub-mkconfig –o /boot/grub/grub.cfg
重新建立了一个配置文件，重启，如故。上网搜了一些如何从grub终端启动、修复grub的文章，虽然都是使用grub的语法，但是这令我大致明白了对于grub2来说，grub.cfg就相当于一个批处理文件（不知道这样描述是否恰当），当选择一个启动项之后，将在后台按顺序执行该menuentry内的命令。想明白这点后，我重新用Live CD进入了Gentoo，把启动命令序列抄了下来，然后重启，依次输入这些命令
insmod part_msdos
insmod ext2
set root=’(hd0,msdos3)’
linux /boot/gentoo-kernel-xxxx root=/dev/sda3 ro
然后输入boot，成功！引导进系统以后重启，仍然到了grub终端，怎么回事呢，按上述方法进系统，重新安装了一次grub2
grub-install /dev/sda
再重启，熟悉的启动界面回来了。因为还是一个菜鸟，所以我还没有想明白为什么用Live CD启动完安装grub却无法使用/boot/grub/grub.cfg配置文件，而引导进某一已存在的系统后还要重新安装grub2才可以，原因待考，等弄明白后再来更新（TODO）。
以上就是花了一个中午解决的在Win7+Linux共存被打破，重装Windows之后如何修复grub2安装的步骤。
- No Comments
- Tags: gentoo, grub2, linux
硬件问题也是不可小视的——记一次USB鼠标无法识别的悲惨经历
In: Miscellaneous
7 一 2011前两天的一个下午，我把同步完成的ipod弹出，然后并没有按照惯例拔下USB接口，而是拔下了数据线与ipod连接的一端，这时候悲剧发生了，整台机器的USB设备发生异常，USB鼠标不能使用，ipod再插入时也无反应，唯一幸存的是移动硬盘。并且此时右下角不断弹出”USB Device not Recognized”，且扬声器中不断传来插入设备和弹出设备的提示音，像蚊子一样煞是烦人。无奈只好放下手头的工作，开始解决问题。
第一步，万年不变地先重启一次，可是居然系统都进不去了，再重启后提示需要修复启动问题，然后使用System Repair修复未果，使用System Restore恢复到前一天的还原点，重启后系统可以进入，但是故障依旧。
第二步，由于这个故障并不是由病毒引起，因此不需要对可疑进程以及对进程活动进行监控，于是打开Event Viewer，查看系统日志，发现一些奇怪的日志，例如模块加载失败，磁盘发现错误等。
由现象我的第一推断是驱动出了问题，跟据搜索的一些中文结果也基本上是和驱动有关的。此时因为被右下角不断弹出的提示气泡和提示音弄的快疯了，再加上系统刚刚重装不久，重装的损失并不大，于是果断决定再重装次吧。Win7的硬盘安装还是很给力的，不到20分钟就完事儿了，进去系统，什么事情都还没做呢，该死的冒泡提示又来了（在所有USB外设均未接入的情况）……我还心存佼幸，认为虽然之前重装系统没有出现过这种情况，但是一切等我装完其他设备的驱动再说。无趣的一通安装过程之后，故障依旧。不甘心，在任务管理器中一个一个地禁用USB Controller，一个一个地试，等到恼人的提示没有了之后，其他USB设备也都没法使用了，我把主USB2.0控制器给禁用了……
我死心了，基本上认为这是属于硬件故障，准备过两天回家以后去检修了。此时心情跌落到了谷底，一堆软件又要重新安装，系统还一直不正常，开着控制器么恼人，不开着控制器么移动硬盘和招行不能用了。后来耐着性子先把未知USB设备的提示窗关掉（方法：Device Manager → 对应控制器的”Properties” → “Advanced” Tab → Check “Don’t tell me USB errors”）。这下提示气泡没有了，但是插入弹出设备的提示音还是困扰着我，索性禁了扬声器，终于看起来一片详和的气氛了。
但是在整个过程中因为需要重启过几次电脑，都常常自检不过，或者提示磁盘错误，或者系统无法启动。内心很纠结，很不爽， 这种问题，回去还要检修硬件，不如换台本本，工作怎么办，头脑一片混乱。静了一会儿心之后决定在英文社区寻求一下帮助，看了几篇贴子也都是驱动问题，接下来的一篇，抓住了我的眼球：http://www.online-tech-tips.com/computer-tips/usb-device-not-recognized/。
该文作者碰到的故障和我的类似，某天突然系统不认USB设备了。但是USB接口并没有坏，鼠标插上之后它的Track灯还亮着，ipod还能继续充电。于是作者和我一样按照正常的方法开始处理，同样未果。不知道他是怎么来的灵感，解决方法很简单：“UNPLUG YOUR COMPUTER FROM THE POWER SUPPLY”。不需要修改注册表，不需要重装驱动等，只需要完全断开计算机的电源（包括交流电以及本本的电池）。作者分析，现代的计算机如果插着电源或者挂着电池，主板仍然在接受供电，而主板上就连着USB控制器以及USB设备，有些时候，因为某种故障主板需要做一次重启，USB设备不认很可能就是因为主板的小故障引起的，重启就能让主板重新识别USB设备。
抱着试一试看的心态，我把电源拔掉，稍等几分钟，开机，成功！于是我兴奋地到Twitter上发推，结果 @Hanliinter 说他之前一个学弟就碰到这个情况，正要拿到售后那里去检修，把电池拔掉以后发现，诶故障消失了。郁闷啊，不过每一次在发现、探寻和解决自己系统故障的时候都会特别开心，而且能够学到很多知识。做此记录，以供后来有此问题者参考。
- (4) Comments
- Tags: Hardware, USB, 故障检测
从C/C++程序员角度看Python的动态类型
10 十 2010Python是一种功能强大且完善的动态高级语言，目前被广泛地应用在计算机开发的各个领域。作为动态语言，Python的一个特点就是它支持动态类型（Dynamic Typing）和强类型（Strong Typing）。
动态类型是指在编写代码的过程中，程序员不需要将某个变量声明为某种类型，而是解释器根据变量的赋值动态地分配内存、赋值并将该变量绑定到对象上。它不同于静态类型（Static Typing），后者对于从事C、C++、Java、C#等面向对象语言开发的人来说，再熟悉不过了。静态类型语言在声明变量的时候，需要指定该变量的类型，从而编译器在遇到该类型的对象时，会分配对应的空间并且赋值。让我们来看两个例子：
var = 123 #可直接指向其他类型的对象，不需要转换对象类型
str = 1; //Error: string类没有重载整数的赋值
从上述例子中我们可以看出，在Python里类型并不与变量绑定，变量只是对象的一个别名，一个变量可以赋予任何类型的对象值——事实上Python的处理也是如此：类型与对象进行绑定，变量名只是对象的一个表示，在表达式中变量名将被展开成为对象进行求值。而C++等静态类型语言则不同，类型与变量绑定，当出现该变量时，编译器会根据变量的类型进行求值，程序员不能轻易地将不同类型的值赋予该变量。
强类型指的是运算符或者函数调用的合法与否依赖于操作数或者参数的类型是否为预期类型。比如"23" + 1这样的表达式就不被强类型语言接受。
Python的值传递方式是全局by-ref，这点与C#及Java类似。接下来本文就将以C/C++程序员的角度理解Python的动态类型机制。
前文中曾经提到，在Python中，类型并不与变量绑定，一个类型绑定一个对象，那么解释器在碰到一个变量的时候要如何解析该变量的类型和值呢？答案是通过给一个对象赋以额外的信息。在Python中，我们可以将一个对象看作是一个结构体：
Type* type;
int refCount;
char* obj;
} PyObj;
该结构体分成三个部分：type，指向一个类型对象，该对象表明当时对象的类型（在Python中，所有的值都是对象，包括类型、函数等）；refCount，表示该对象的引用次数，当该对象的引用次数为0的时候，GC将会自动回收内存空间；obj，真正对象存放的地方。我猜测，其他动态类型语言的实现细节从整体上看应该也是如此布局。也正是由于在动态类型语言中，解释器要知道一个变量所指向对象的类型，必须先从变量所指的地址得到该对象的类型，再对该对象进行一系列的操作，因此效率相对于静态类型语言而言要低。因为静态类型语言的编译器维护一张符号表，在表中记录着变量对应的类型，可以很方便地将相应操作直接转变为机器码或者字节码，而不用在运行时检测对象类型，效率会提高许多。
那么Python的引用语义是如何实现的呢？答案同C++类似，使用指针机制，然而Python中变量并没有其绑定的类型，这点与void指针很像。我们都知道，在C/C++中如何解析一个指针所指向内存的内容是通过该指针的类型来完成的，而void指针可以指向任意一块内存空间，只是编译器不知道该如何解析而已。在Python中类似，在前文的例子中我们可以得到一个void指针var，对该变量的操作则是如前如述通过与对象绑定的额外的类型信息获得的。知道了这点之后就可以很容易地理解Python的共享引用：
1) 共享引用和In-place修改
观察这么一段代码：
>>> a = 3
>>> b = a
此时变量a和b指向的是同一块内存地址：即整数3这个对象，转换成对应的C++代码可以是：
void *a = &3 // 此处3是常量，而Python中3是一个对象，注意区别
void *b = a
从C++代码中很容易就得出a、b所指向地址相同的结论。因此在Python中处理共享引用一个可更改对象（如List、Dictionary和Set）时要特别小心，例如：
>>> L1 = [2, 3, 4] # A mutable object
>>> L2 = L1 # Make a reference to the same object
>>> L1[0] = 24 # An in-place change
>>> L1 # L1 is different
[24, 3, 4]
>>> L2 # But so is L2!
[24, 3, 4]
由于L1、L2指向的同样一块内存空间，因此对L1的修改同样会引起L2指向对象的变化，可以使用将引用语义转换至拷贝语义来规避这种潜在的语义错误：
>>> L1 = [2, 3, 4]
>>> L2 = L1[:] # Make a copy of L1
>>> L1[0] = 24
>>> L1
[24, 3, 4]
>>> L2 # L2 is not changed
[2, 3, 4]
2) 对象比较
在C++中，比较运算符“==”在其操作数为指针时，返回的结果是两个指针对指向的地址是否相同，当其操作数为对象时，则是比较数值是否相等或者根据重载的运算符的行为来定义。而在Python中，由于其引用语义实际是通过指针的机制来实现，对于比较两个变量的行为就要特别注意。一般地，==运算符比较的是两个变量的值是否相等，例如：
>>> L = [1, 2, 3]
>>> M = [1, 2, 3] # M and L reference different objects
>>> N = L # N and L reference the same object
>>> L == M # Same value
True
>>> L == N # Same value
True
在讨论共享引用的时候我们说过，N和L指向的是同一内存地址，因此无论Python中==运算符的语义为何，得到的结果都应该是True，而从比较L和M这两个虽然指向内容一样，但是对象的地址却不同的例子中我们可以得到==运算符的确切语义。那么如果想知道两个变量是否指向同一个对象应该如何编写代码呢？答案是使用is表达式：
>>> L is M # Different objects!
False
>>> L is N # Same object
True
总结：
本文尝试从C/C++程序员熟悉的指针角度，简略地探讨了Python中动态类型的实现机制，分析了对象的内存布局，变量的共享引用机制。
- No Comments
- Tags: C/C++, Dynamic Typing, Python
研二了，天天放暑假一样，没有课，除了老板的项目，其他时间都可以自我支配。看了笑来的很多文章，心中对怎么学习英语也有了自己的认识。
- 首先在iTunes上面订阅了NPR（National Public Radio）的一些热门节目，比如说CarTalk之类，然后平时一个人独自往返实验室、寝室、食堂的时候就听一听，使自己接触英语的时间尽量多，创建一个良好的听力环境
- 精听一些开放课程或者英语教学Podcast（比如ESL，虽然它语速很慢，但是这个Podcast可以提供一些情景对话或者情景用法，可以丰富自己的用法库），在此之前先精读script，做到记下不认识的单词，理解整段话的意思后再多听几遍音频。
- 暑假新近购入一台Kindle DXG，看书的效果真不是盖的，准备跟着BabelCollege的一起读原版活动认识看完一本英文原著。英文的技术书读过几本，但是一旦到了非专业领域就两眼一抹黑了，基本没怎么读过原著。万事开头难，坚持读完一本，以后就是康庄大道了。
在此隆重推荐笑来近期举行的一次活动，一起读原版之《Justice – What’s the right thing to do?》，原文转载如下：
之前，BabelCollege.com推出“大家一起读原版活动”，尝试的第一本书是Malcolm Gladwell的Outliers，读者参与踊跃，现在已经有很多读者读完该书。
BabelCollege.com再接再厉，为用户开发了根据原文句子提问的系统。这次，大家一起读的是哈佛大学的公开课“Justice – What’s the right thing to do?”。
2009年12月初，我曾在博客上介绍过该课程，随后又为该课程制作了srt格式的英文字幕。又因为觉得该课程的内容是每一个“受过高等教育”的人都应该了解的，所以就一直把该课程的视频链接放在博客首页的右侧。这一年多以来，很多读者都来信说看过该课程之后又多惊人的收获……我个人是坚持不懈地将该课程推荐给每一个正在准备留学的学生，告诉他们，这样的常识如果竟然不知道的话，出去之后肯定处处吃暗亏……
BabelCollege.com从这一周开始，每周更新一个视频的字幕（课程总计24节，12段视频，每段视频相当于有两节课），有想彻底弄明白这个课程的同学，可以把字幕精读一遍，然后再开始看视频。视频看过之后，再有不懂得地方，可以回到BabelCollege.com的字幕文本页面上，找到相应的句子提问。
其实，硬着头皮精读完第一本原著（或者剧集什么的），以后就轻松了。很多人一辈子不行，其实只不过就是差这么一下子而已。
我多少有点奇怪，每当我提到精读的时候，总是有人问“您所说的精读是什么？” 这难道是个需要解释的概念么？好像真的是，要不然怎么会有这么多人问呢！
所谓精读，顾名思义，就是，一个字不落地读，搞清楚每个字，每句话的意思，确保自己没有任何遗漏。我妈妈当年是这么教我的：“随便看看就可以的书，你看他干嘛？！”于是，我读书从来都是精读。否则干脆不看。人们为什么讨厌精读呢？我其实过去写过一篇文章解释这事情。
希望这个小小的功能，能够帮助那些肯花时间提高自己英语水平的同学更进一层楼！
给笑来做个小广告，有兴趣的同鞋们一起来试试吧！
- No Comments
- Tags: English, Justice, 一起读原版
生成n个数的全排列（Permutation）
In: Algorithm
23 三 2010一直以来我对数的排列这类算法问题都感到很头痛，曾经囫囵吞枣看过一些算法，可是浅尝辄止，没有实际操作所以每次都忘记。上周三算法分析与设计课的内容是递归，老师正好提到了排列数这一问题，于是就有机会稍微进行一些研究。
一个排列（permutation）就是对一组对象或者数值按照某种特定的方式进行排列组织（ar-rangement），为了方便起见我们以一个数集{1, 2, 3}为例，它的全排列共有3!=6种，即{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}，上述列举排列的顺序又称为按字典序列举排列，具体将在下文进行叙述。
一、字典序
在Wikipedia中，字典序的解释是这样的：
In mathematics, the lexicographic or lexicographical order, (also known as dictionary order, alphabetic order or lexicographic(al) product), is a natural order structure of the Cartesian product of two ordered sets.
如果你拥有一个字典，那么里面所有的字符串都是按照字典序来进行排序的，假设有两个字符串：
a1, a2, …, an
以及
b1, b2, …, bn
若存在一个m>0，使得对于所有的i<m有ai=bi，并且am<bm（i>m时ai与bi的关系不用考虑），那么称ap, 1≤p≤n的字典序小于bq, 1≤q≤n。由这个定义可以很容易的发现这样一个事实，当同样长度的一串数值、字符串需要按照字典序排列时，进行比较的位数i总是从n递减至1，例如：1234<1243, 1234<1342, 1243<1342，所以这三个串的顺序是：1234<1243
<1342，比较的位数依次是第3位和第2位；而从高位降低一位进行比较的条件则是对于此时的i，有ai+1≥ai+2≥…≥ai+n，例如当i=2时，12345<12354<12534<12543，此时a3≥a4≥a5，于是接下来将把2替换成字典中下一个数字3来进行排列，这个特点将在本文的最后一个方法中得到应用。
二、利用递归解决全排列问题
下面就让我们来看一个具体问题，给定一串数字：{a1, a2, …, an}，它们两两之间并不重复，要求输出由这些数字组成的全排列。乍看之下似乎可以用穷举法解决，由于n个数字的全排列个数是n!，故而穷举法的时间复杂度为O(n)。那么利用什么数据结构来穷举呢，由于全排列我们需要考虑每一位的各种情况，确定了一位的数字以后就继续试验下一位……也就是说当确定一种可能性之后就会沿着这条路径一直往下，直到确定最后一位数字，这个行为和深度优先搜索算法比较相似，因此我们可以用树来表示穷举的全过程，下图以求{1,2,3}的全排列为例如此方法进行说明：
图一 利用递归生成{1,2,3}的全排列
从上图我们可以看到，每一个排列就是从根结点到叶子结点的一次遍历，其伪代码如下：
2 for each s in S
3 A[i]=s
4 call Permutation(A,S-{s},i+1)
5 repeat
6 end Permutation
三、含有重复数字的全排列问题
上述方法很直观，可是存在着一个问题，那就是它无法判断出某些数是否重复，它只是很单纯的穷举着所有可能出现的排列，例如1,2,2,4这四个数实际排列数为：4!/2!=12种，而上述算法仍然会得出24个结果，它无法区分1,2,2,4和1,2,2,4是一个重复的排列，应该只列举一次。可是递归的方法又非常直观非常方便啊，应该怎么办呢？其实只要在原方法上做一点小改动，人为的多设置一个集合，该集合包含了原集合中所有不重复的数字，从而树同一级的分支用该集合中的数字做为标签进行搜索，这样能够避免同一级出现重复计算的情况，下面以1,2,2为例说明上述方法的错误以本方法的改进：
图二 传统方法处理有重复数字的集合时会产生非预期的结果
改进后的伪代码：
2 find a set B that contains no-duplicated number
3 for each b in B
4 A[i]=b
5 call Permutation(A,S-{b},i+1)
6 repeat
7 end Permutation
从代码中可以看出改进方法只是用一个不包含有重复元素的集合来代替原集合，并用新的集体进行迭代，转化成树形结构如下图所示：
图三 改进方法生成全排列
听老师上课的时候说这是一道微软来我们学校面试的考题，其实高爷爷在TAOCP第四卷分册2用了整个分册的内容讨论了如何生成全n元组(n-tuples)和全排列的问题，书中所述的第一个按字典序生成全排列的方法即可以在不必考虑给出的数集中是否有重复数字的情况下完美的生成全排列：
四、Algorithm L in TAOCP （字典序排列的生成）
Algorithm L是一个很经典的算法，它简单、灵活，对于给定的输入a1, a2, …, an（要求该输入必须是排好序的，即a1 ≤ a2≤ … ≤ an）可以生成该集合的全排列，按字典序输出，并且可以很好的处理给定的输入中有重复数字的情况。注意到这个算法对于输入的要求必须是有序的，而前面两个算法无论输入的顺序是递增、递减、乱序都可以很好的工作。
这个算法还有一个特点就是它的输出将排列按照字典序输出，那么在设计算法的时候肯定会需要用到字典序的一些特点，让我们来回顾一下上文所述——字典序的比较是从最高位开始逐渐递减至最低位，每次递减的时机是从该位开始至最高位，所有的数字呈从大到小的顺序排列，明白了这个特点就能够很轻松的理解L算法。
让我们先来看一下L算法的思路：
- 找到能够满足下一步递增aj的索引j，即当前比较的位数j
- 将aj递增到尽可能小的下一个值
- 将a1…aj开始的排列置于当前最适合的字典序模式（即aj+1至an按从小到大的顺序排列）
L算法基本上按照思路，共分成4步
L1. [输出] 输出排列a1…an；
L2. [找到j] 令j←n-1，如果aj≥aj+1则将j自减1，直到aj<aj+1。这步的作用就是找到使从j位至最高位所有的数字呈从大到小的顺序排列的这个j，该位就是下一步需要改变（增加）的值。
L3. [更改aj] 令l←n，如果aj≥al则将l自减1，直到出现aj<al，（updated 此时交换aj←→al）
。这步的作用就是找到从第j位至最高位中，大于aj的最小数值，该数值就是下一个字典序中aj的值。
L4. [反转aj...an] 令k←j+1，l←n，如果k<l，交换ak←→al，自增k，自减l，再重复此交换直到k≥l。这步的作用是使由a1…aj开头的排列恢复到字典序的最小位置。
这种文字的步骤似乎比较难以理解，下面一个例子对算法的步骤加以说明：
(1) 整个算法的核心就是找到需要改变的j值，例如13287651，注意到最后四位已经按照从大到小的顺序排列，也就是说13287651是处于132xxxxx这个排列在字典中的最大值，那么下一个排列就要通过修改第3位的2获得。——这是L2.步骤解决的问题
(2) 那么这个2要替换成什么数值才行呢，在132之后一共有五个数字，1,5,6,7,8，让我们来比较它们的大小：13187652<13287651<13587621<13687521<13782651<13827651，可以看到，在字典中紧跟着13287651的排列是13587621，也就是将要替换的2与后面所有数值中大于2的最小数字进行代换。——这是L3.步骤解决的问题
(3) 在替换了2之后，排列变为了13587621，注意到在寻找j的时候我们已经保证了最后五位是按从大到小的顺序排列的，又由于替换的数字是大于aj所有数字当中最小的，所以在替换之后我们仍可以得到一个有序的数列，这个数列是135xxxxx这个形式的所有排列中最大的，于是我们要对它进行反转，这样得到的数列顺序为从小到大，同时也是所有排列中最小的。——这是L4.步骤解决的问题。
之前看到有关求全排列的问题时我也常常看到介绍的就是这个通用算法，可惜当时一直没有认真去琢磨其中每步的作用，所以一直对这个问题敬而远之，在高爷爷的书中还有介绍更多更详细的算法，出于敬畏我有时间了再研读它吧。
五、参考文献
1. Permutation (wikipedia):
http://en.wikipedia.org/wiki/Permutation
2. Lexicographical order (wikipeida):
http://en.wikipedia.org/wiki/Lexicographic_ordering
3. Donald Knuth. The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing. Addison-Wesley, 2005. ISBN 0-201-85393-0.
- (5) Comments
- Tags: permutation, 排列, 算法
浅谈字节序（Endianness）
In: C/C++
5 三 2010假期里面在家里忙尹老师的激光项目，阅读文件格式文档的时候看到关于字节序（Byte Order）的要求：
For values which span more than a single byte, the multiple byte ordering followed is that of the Big Endian / Motorola standard. The most significant byte will occur first, the least significant byte last
想起以前在汇编语言和数字逻辑的时候也有接触到一些这个概念，已经有点模糊了，搞不清楚哪个是低位在前哪个是高位在前。后来在Wiki和Google的帮助下也算摸清楚了一些Endianness的概念。
一、字节序的起源
在计算机中，字节序（Endianness）是数据中单独的可取地址的亚型（words，bytes和bits）在外部存储器中存储的顺序。通常在提到四字（ddword）、双字（dword）和字（word）的时候需要考虑其实际的字节顺序，为了简便起见它的英文也常常表示为Byte Order。
Endianness这个词源自1726年Jonathan Swift的名著：Gulliver’s Travels（格列佛游记），在书中有一个故事，大意是指Lilliput（小人国）的领导下了一道指令，规定其人民在剥水煮蛋时必须从little-end（小的那一端）开始。这个规定惹恼了一群觉得应该要从big-end（大的那一刻）开始剥的人。事情发展到后来，竟然演变成一场纷战。支持小的那端的人被称为little-endian，反之则被称为big-endian（在英语中后缀“-ian”表示“xx人”的意思）。1980年Danny Cohen在他的论文“On Holy Wars and a Plea for Peace”中第一次使用了Big-和Little-这两个术语，最终它们成为了计算机通过网络与其他计算机连接时所要考虑的极其重要的一个问题。
二、字节序的种类和其表示
那么为什么要引入字节序呢。我们都知道，计算机存储中最小的单位是位（bit），而8bit构成一个字节（byte）。在一个32位的CPU中，字长为32bit，也就是4byte，数据要想存放在内存中供CPU读取和写入，就需要拥有一定的存放顺序。这样不同的CPU可接受的字节序有可能不同，那么在设计硬件和软件时数据的存放问题也需要分开考虑。
数据都有所谓的“有效位（Significant Bit）”，顾名思义它表示了“数据存放有效的位置”，而字节序的分类就是依赖于有效位来进行划分的。在一个字节当中，数据的有效位的顺序已经得到了大多数硬件生产商的共识，那就是最高有效位优先（Most Significant Bit First），例如我们用8位二进制数来表示十进制数123为01111011，其第一位的0就是最高有效位，而最后一位的1就是最低有效位，在一个字节当中，几乎当前所有的硬件都采用了这种直观的字节序。
然而情况在离开了单字节时就有所不同了。不同的硬件产商对于数据占据多个字节时拥有怎样的字节序有着不同的理解，具体说来分为以下三类：
- Big-Endian（大字节序）：最高有效字节优先，更高的字节有效位占据着更低地址的内存空间，其在内存中的表示与直观吻合，
- Little-Endian（小字节序）：最低有效字节优先，更低的字节有效位占据着更低地址的内存空间，其在内存中的表示与直观相反，以及
- Mixed-Endian（混合字节序）或者Middle-Endian（中字节序）：在16位字（word）中的字节序与32位字（dword）中的字节序不相同。这种类型的字节序较为少见。
一些知名的使用Little-Endian的处理器体系结构包括了：x86、6502、Z80、VAX以及PDP-11，使用Big-Endian的处理器通常是Motorola的处理器，例如：6800、68000、PowerPC（即Macintosh在迁移到x86之前所采用的处理器）以及System/370。这也是为什么在文章开头提到的文档中使用Big Endian / Motorola standard这样的词汇的原因。
更进一步的，像ARM、PowerPC、Alpha、SPARC V9、MIPS、PA-RISC和IA64等体系结构可以支持可切换的字节序这样的特性，这个特性可以提高效率或者简化网络设备和软件的逻辑。这种可切换的字节序被称为Bi-Endian，用于硬件上意指计算机或者传递数据时可以使用两种不同字节序中任意一种的能力。
文字不够直观，下面以数值0x0A0B0C0Dh为例说明Big-Endian和Little-Endian在内存布局上的不同：
- Big-Endian在内存中的表示
| increasing addresses → | |||||
| 0Ah | 0Bh | 0Ch | 0Dh | ||
在这个例子中，最高有效字节（MSB）为0Ah，储存在最低地址的内存中；次高有效位为0Bh，储存在接下来的内存中，依此类推。这种字节序与从左向右的顺序读取十六进制数值非常类似。
以16位元素大小查看：
| increasing addresses → | |||||
| 0A0Bh | 0C0Dh | ||||
最高有效元素现在保存的是0A0Bh，接下来的元素保存0C0Dh.
- Little-Endian在内存中的表示
| increasing addresses → | |||||
| 0Dh | 0Ch | 0Bh | 0Ah | ||
在这个例子中，最低有效字节（LSB）的值为0Dh，储存在最低地址的内存，其他字节依照字节有效性的递增依次存放。
用16位元素大小表示
| increasing addresses → | |||||
| 0C0Dh | 0A0Bh | ||||
最低有效16位单元储存的是值0C0Dh，紧接着储存值0A0Bh。
三、字节序的重要性及其应用
如前所述，不同硬件的体系结构接受不同字节序的数据表示，因此当同一个文件在不同的机器中进行读取和写入的时候，其所支持的字节序就显得尤为关键。设想在x86计算机中将(123888)10写入二进制文件中，由于x86支持Little-Endian，所以该数在文件中保存为(0000003F1E)16。当在PowerPC计算机中读取该整数时，由于它支持的是Big-Endian，故读取的结果将是(16158)10，大相径庭。
同样的情况也会出现在网络传输当中，当你从支持一种字节序的机器发送数据到支持相反字节序的机器时，将会得到非预期的结果。这种错误在网络传输当中尤为突出，因为你无法决定发送你所需文件机器所支持的字节序，因为这些机器可能分散在世界各地，不是人为所能控制的。
为了更明确的说明上述问题，考虑下列代码：
02 #include <string.h>
03
04 int main (int argc, char* argv[]) {
05 FILE* fp;
06
07 /* Our example data structure */
08 struct {
09 char one[4];
10 int two;
11 char three[4];
12 } data;
13
14 /* Fill our structure with data */
15 strcpy (data.one, “foo”);
16 data.two = 0×01234567;
17 strcpy (data.three, “bar”);
18
19 /* Write it to a file */
20 fp = fopen (“output”, “wb”);
21 if (fp) {
22 fwrite (&data, sizeof (data), 1, fp);
23 fclose (fp);
24 }
25 }
这是一段很简单的C语言代码，作用就是向一个data结构体赋值并且将它写入文件当中，从结果Listing 2和Listing 3当中我们就可以看到支持不同字节序的机器在处理数据时候存在的不同。
Listing 2. hexdump –C output on big-endian machines
00000000 66 6f 6f 00 01 23 45 67 62 61 72 00 |foo..#Egbar.| 0000000c |
Listing 3. hexdump -C output on little-endian machines
00000000 66 6f 6f 00 67 45 23 01 62 61 72 00 |foo.gE#.bar.| 0000000c |
注意力好的同学一眼就能发现，在写整数的时候，数据保存的顺序依赖于不同的机器，而字符串却不受此影响，这是为什么呢？这就牵涉到字节序是如何如代码进行影响的了。
字节序并不会影响数据存储的所有方面，例如对一个整数进行bitwise或者bitshift的操作，你是不需要去注意对应的字节序的。因为多字节的顺序是由计算机来维护的，对于程序员来说，一个整数的最低有效位仍然是最低有效位，最高有效位亦然，并不会由于它在计算机底层存储模式的改变而影响到有效位的含义。
同样的，字节序不会影响到C风格字符串在计算机底层的存储顺序，这是为什么呢？考虑到一个C风格字符串的实质是一个包含着许多char的数组，每一个char在现代计算机中几乎都是表示计算机中的一个字节。因此，当读写C风格字符串时，其最小的元素单位是一个字节；而且数组在内存单元中地址的排列顺序是递增的，例如定义char str[5];这么一条语句，假设&str[0]的地址为1000，则&str[1]的地址为1001，依次类推。所以不论从直观含义或者底层技术来看，字符串的存储都是相对字节序独立的，这个特性将应用在接下来的许多小技巧中。
那么字节序除了影响到多字节数据在内存中的存放顺序以外，在写代码的时候还有什么需要注意的呢？当对一个数据进行类型转换的时候，需要记住特定的字节序很可能影响到类型转换的结果。假设我们有Listing 4所列的这么一段代码
4 x = *(short *) endian;
那么最后得到x的结果是多少呢？是不是简单的就是endian数组的第一个元素1呢？答案是错，x的数值需要根据运行时的环境来决定。让我们回忆一下C语言的指针指向多大的内存以及怎么去解释所指的这块内存是由指针所指向的类型来确定的，在上述代码中，将endian数组的首元素指针强制转换成short *的指针，那么编译器在解释它的时候将不再把它指向的内存空间视为1 byte，而是short的长度——2 byte；更重要的是当我们对这个指针解引用的时候将会得到的值会是什么。再回到上面所提到的字符串或者字符数组在计算机中就是依照数组顺序存放的，那么这个时候endian数组占用了两个字节，其内存数据为：0100。当该指针强制转换为指向short的指针并解引用时，计算机将一次读取两个字节，这个时候字节序就发挥它的影响了。在支持Little-Endian的机器中x的值将是1（读取为0001），而在支持Big-Endian的机器中x的值就是256（读取为0100）。因此在对指针进行类型转换并解引用，特别是在单字节到多字节数据的转换时，要特别注意字节序是否会使得预期结果出现偏差。
单字节指针到多字节指针的转换其实并不完全像Listing 4所举例子那样恼人，它还有其他的用途，例如我们可以使用这个特性在运行时判断当前计算机所支持的字节序，这样可以使得程序员在编写代码的时候更加灵活，也使得代码更加强健（robust）。基本的思路就是先定义一个int变量1，这个变量在不同的计算机中将有两种不同的存储顺序：01000000（Little）以及00000001（Big），然后我们将指向这个变量的指针强制转换为指向字符的指针，再解引用根据它的值是0还是1就可以得出当前机器支持的字节序的，代码很简单：
4 // Big Endian
5 else
6 // Little Endian
利用char*的这种特性还可以方便的反转数据顺序以适应不同的机器，怎么编写这样的代码不如让你来思考一下？
四、参考文献
1. Endianness. http://en.wikipedia.org/wiki/Endianness
2. 关于Endianness翻译的讨论。 http://shu1tong2wen2.wikia.com/wiki/Endianness
3. Writing Endian-independent Code in C. http://www.ibm.com/developerworks/aix/library/au-endianc/index.html?ca=drs
今天自己写了一篇东西，感觉神清气爽，深刻体会到了写文章的好处。在写文字讲述一个问题的过程中，我会注意到如何完整并且清晰的讲清楚一个问题（虽然今天这个文章可能并不完整也并不非常清晰，不过总归是好的一个开始），而扩展到以后，在描述技术问题的时候，为了有理有据的说明一个方案，我会强迫自己去寻找证据论以支持我的论点，这无形中增加了知识的积累；同时，一篇好的文章要有好的组织结构，以及有条理的论述，这能提高我对问题的描述能力（现在我感觉自己极其欠缺，经常表意不清），也能提高我说话做事的逻辑性：总的来说，是大有裨益的。
其实小的时候，我阅读过很多书籍，可是为什么我的写作水平总是停留在记叙文文字空洞，议论文说服力欠缺呢，我觉得有以下几点
- 小时候对小说、史书等书籍的吸收是以情节或史实为重点的，而不是其写作手法。因此提到一个剧情我可能可以回想的起是在哪本小说上看到的，而给我一句话我几乎是想不起来在哪里见到过它。这导致了我在写文章的时候文字很空洞，很白话。以前一直不屑于模仿其他作者的遣词造句，现在我感受到了模仿之后才是创新，对于一件事物，都没有掌握其本质，何以在其之上创造属于自己的新事物呢。我应该刻意地去模仿一些常用的语句，然后再结合它们进行灵活运用。
- 平时写作不够。《Outlier》里面说到过，要在某方面达到高手的程度，需要10000个小时的实践。实践是检验真理的唯一标准，以前我一直在读书，却没有停下来，写点自己的东西，实践所看到的文字；上了大学，连书都没怎么看过了，更不用说写作了。不过写代码也是同理，看了再多的书，没有亲手实践，将其转化为可以运行的代码，时间一长也会忘记。
- 积累不够。在写议论文或者说明一个问题的时候，需要足够的论据来支持你的论点，而我平时看过的东西不注意积累，大部分在一段时间以后就忘记了，提笔忘据，自然整篇文章显得苍白。看笑来老师，Jeffery，pongba及一干人等在写博客的时候，很注意某些材料的出处，列举了之后很有说明力。现在我也注意平时的积累，例如用Delicious保存书签，用OneNote记录网摘，用XMind记录一些灵感等等。
- 逻辑混乱。大学四年没怎么接触过语文，感觉最基本的逻辑已经忘的一干二净了，让步和假设，因果和条件，在英语写作中这些逻辑关系也是同样重要的，没有逻辑的文章读起来会使人感到混乱，感到可笑，再多的论据也支撑不起一篇没有逻辑的文章。
学习的路还有很长啊，以前太不认真了。不少东西其实很早就接触到了，只是不以为然，不将其付诸于实践，还好亡羊补牢，犹未晚也。抱着学习的眼光去阅读，抱着实践的态度去写作。
- No Comments
- Tags: 写作, 感悟
立此存照，奇文共赏《Google市侩，我感到恶心》
In: 未分类
13 一 2010今天下午1时20分，百度首席产品设计师孙云丰在自己的博客中撰文关于谷歌退出中国，直指Google退出中国的姿态证明自己是市侩分子，对此感到恶心。他的博客全文如下：google宣称要退出中国，所证明的，恰恰不是市面上的那些g粉所宣称的那样，google是个人权斗士，而刚好反了过来，正好证明google是个市侩分子。google 的首席法律顾问的调调让我感到恶心。因经济利益退出，就直白白的说好了，把自己涂脂抹粉一番，还煞有介事的提到google被中国人攻击，中国异议分子的 Gmail信箱被攻击，把这些事情作为退出中国的铺垫，这种论调是侮辱中国普通老百姓的智商，但还真有可能迎合那帮目空一切，但从未到过中国、对中国没有 丝毫了解，却又喜欢对中国说三道四的西方人的假想。
只提一个假设，如果谷歌占据了中国80%的搜索市场份额，google的高管，还会这么高调的宣称要do no evil，从中国退出吗？
整个事情给我的唯一感受，就是恶心。
————–
以上是作为一个曾经的忠实google用户而说的，和百度无关。市面上沾沾自喜于了解一点google的产品技术细节将google奉为道德楷模而自封G粉的兄弟，请勿跟帖瞎喷，你们根本不懂什么叫搜索引擎，什么叫自由人权。
About this blog
I'm now a graduate student of Computer Applied Technology in Tongji University. I like Computer Graphics, Web 2.0, Magic, Music and am partially a geek. This blog is about C++, algorithm, cg, comments and other things I may get in touch with in the near future. Hope everyone enjoy this little site. Contact me: 4everlove.xu AT gmail.com
Photostream
Categories
- Algorithm (2)
- Topcoder (1)
- Application (6)
- Twitter (4)
- Comment (1)
- Computer Graphics (1)
- OpenGL (1)
- Learning (2)
- English (1)
- Linux (1)
- Miscellaneous (1)
- Programming Language (2)
- 未分类 (2)
- 烧饼: @hellothere 是这样，转换成16进制确实是1E3F，但是由于是存入“二进制”文 [...]
- hellothere: 123888转换成16进制是3F1E？应该是1E3F0吧，错误之处还请明示 [...]
- harris: Permutation(A,S,i) 1 if Len[S]=0 Then Print(A) 2 for each s in S 3 A[i]=s 4 call Permuta [...]
- SB: 可以用这个制作视频CG特效吗？ CG动画啊。 我挺想学CG的。 [...]
- vvoody: 我错了，lz删了吧 [...]
读《Introduction to Theory of Computation》
In: Comment
25 一 2010这学期让我最怨念痛苦的课就是《计算理论》了，本来我读研的初衷就是在TL里面浸淫了许久感觉到自己做为SE的学生在CS这门学科里面基础知识十分的匮乏，读了研就有一些时间补充基础，提高能力。而看到选课单的时候发现有“计算理论”这门课，我不是特别了解这个课程，只是大概知道与自动机有关。接触自动机是在大三的编译原理课上，觉得编译器是一个很神秘很powerful的“机器”，而且计算理论一听这名字就与计算机的基础似乎有着或多或少的联系，所以还是很期待的。可是……上了课之后真是觉得大失所望，一名口齿特别不清的老师，第二次课我坐在第一排，听着他讲了1个半小时，仍然有些不知所云，而且虽然他的PPT做的还是不错的，具体而不过于详细，可是他的讲课方式让人昏昏欲睡，从此我就失去了听他上课的兴趣。而考试需要复习的资料何其多，让我更加厌烦，都有种考好试就把这本借来为了复习的教材还掉的冲动。可是在复习的时候，还是感受到了这本书的价值的，而且后面的P与NP又是我在学习算法的时候很想了解一下的东西，于是就打算在回家前把它阅读完。下面来说说这本书
本书名为Introduction to Theory of Computation，顾名思义应该是一本普及入计算理论门的书籍，作者Michael Sipser，乃著名的麻省理工大学应用数学系计算理论小组的教授。全书分为三部分，涵盖了计算理论的三个方面——自动机，可计算性，复杂性，深入浅出，语言明快轻松，确实是了解计算理论的一本好教材。对于每一个引理、定理、推论，作者均会事先以非正式的语言描述证明的思路，然后再以正式的数学语言对其进行证明，这样可以更好的帮助读者了解证明的思路而不是一开始就给出证明方法令读者丈二和尚摸不着头脑。本书共11章：
因为考试，所以我特别认真的阅读了0~3章，然后自己阅读了4、5、7章，第6章看的有点晕头晕脑且该章相对于全书来说比较独立，跳过不会影响到其他知识的阅读，所以我选择了跳过，而后面四章与算法的设计和分析较为相关，本来我是计划阅读全部4章，后来因为放假了心有点散了，又想在回家前把书还掉，于是就没有继续阅读了。
这本书的优点前面已经说过了，缺点就是有些概念已经比较过时，比如下推自动机和图灵机的定义，就与孙另外推荐的一本参考书：Introduction to Automata Theory, Languages, and Computation (3rd Edition) 和wiki上面的定义有些差别，但是不妨碍这本书成为一本经典的计算理论入门书。