Tech

入了一个树莓派

published on

之前玩DroidQuest,把大学里没怎么听的数字逻辑全搞明白了,突然很有兴趣想动手弄点东西玩。遂入手树莓派一枚。现在只要200块出头。

照片

拿到后刷上Arch Linux,跑起来正常,可以准备买电子元件接GPIO玩了。如果能够找到4个方向运动的轮子,真想复刻一个DroidQuest里面的机器人玩哈哈。

说起来raspberry-pi的好处还是社区比较大,各种尝试都有人做,虽然做法各种粗糙,我不止一次看到3.3v的GPIO外直接接5v的设备,所以照着例子来还得小心。

Read More...

开始玩 DroidQuest

published on

这两天通过知乎发现一个神游戏:Robot Odyssey,有人在用java写了一个复刻版,叫DroidQuest。

抱着体验的态度玩了一下上瘾了啊……

游戏大概就是说,你需要借助3个机器人探索下水道恩,通过总共5个level,机器人里面长这样:

robot-inside

恩,结果就是需要通过连数字电路的方式来控制机器人,机器人里面有传感器,喷射器,天线,爪子可以供你使用,下面还有电池和开关。图中是来自游戏的tutor自带的电路,激活了爪子抓取功能,同时靠一个锁存器实现左右运动的功能…..

你还可以自己在实验室做芯片,为了过第三关的一个地方,我设计了一个遥控芯片:你可以通过控制一个机器人的天线发射信号,然后另一个机器人接收了之后再运动,这样手工操作通过了不少需要专门设计电路的地方- -

所以我现在刚刚到达了第四关。按网上的说法,第四关开始会非常有挑战,如果有幸打过去了,一定要写攻略。不过估计之前得好好学习下数字电路了…

下面是我打level2和level3时手工绘制的大地图(缩略过):

level2

level3

顺便讲一下自己做的简易chip:

  • 首先是做了一个1-bit counter:一个输入一个输出,每当输入从0变成1时输出翻转,也就是上边沿改状态
  • 然后两个1-bit counter串起来可以做成2-bit counter,再译码输出成4个信号
  • 这四个信号接机器人四个方向,同时要求天线为1的时候再运动
  • 最后就可以用另一个机器人的天线来控制这个机器人运动/停止/转向了…

如有别的在玩的人看到了,欢迎交流

Read More...

tutor真是不好读

published on

之前参加了一次Topcoder的SRM,把500pt的题目给做了。期间小心翼翼地绕开了无数trick,最后还是挂了。不过在那一次之后,我就学到了一个教训,对a除以b取下整的时候要注意负数的情况。当然这个教训不是本文的重点,我写这个事是因为比赛后我决定把这个教训记下来,但是一直没有写,直到这两天有了新的教训。想想再拖下去不像样,于是就这么写了。这个故事告诉大家,如果没有截止日期,那么什么事都很难做下去。

那么新的教训是来自哪呢?在于我最近开始研究os也就是操作系统要怎么写了。这件事得追溯到我上学的时候,在学校的二手书店里买了一本《自己动手写操作系统》,当然那个时候我兴趣广泛,这本书看了几章弄不明白就放到一边去了。我说兴趣广泛不是为了能力不足而辩解,这只是一个伏笔。我前几天在亚马逊上闲逛,看到一个日本人写的《30天自制操作系统》kindle版,立马对其产生了兴趣,于是买了下来,顺便把学校买的书从箱子中找了出来,兴致勃勃的准备开始折腾一下。

为不了解的人介绍一下,这两本书都是指南类型的书,就是有经验的人写过你说如果你要做一件事,可以先做什么,接着做什么,然后怎么样,你按照这样的步骤就可以完成这样复杂的工程了。

开始真是顺风顺水,照着书上的思路顺利的把bootloader给搞定了,但是从保护模式开始,就令人吐血了。我又懒得参考人家的代码,两本书开始讲gtd的时候,我实在是把握不住了。于是我开始了在互联网上的探索,发现了一系列优质的指南资源,比如osdev.org。通过长时间的研究,我大致把握住了下面几点:

  • cr0寄存器有一位表示是否进入保护模式
  • 保护模式下端寄存器存放的是selector,是通过gtdr这个寄存器指向的table里面的信息来将虚拟地址映射到物理内存地址的,然后gtd中间每一项有base limit flag等字段来描述这个段的信息

当然这些内容对于本文来说是无关紧要的,有意思的地方在于所有这些文章全部简单的描述了一个gtdr之后就给出了类似下面这么一个代码:

   LGDT  [gdtr]
reloadSegments:
   ; Reload CS register containing code selector:
   JMP   0x08:reload_CS ; 0x08 points at the new code selector
.reload_CS:
   ; Reload data segment registers:
   MOV   AX, 0x10 ; 0x10 points at the new data selector
   MOV   DS, AX
   MOV   ES, AX
   MOV   FS, AX
   MOV   GS, AX
   MOV   SS, AX

总之这之后一切就设定好了。我就特别悲伤的对着这段代码研究了很久,先是好不容易理解了这一坨代码其实是设置段寄存器:把cs改成0x08,把其余的改成0x10。这些描述给我留下了无尽的谜团,比如到底是如何通过gtd寻址的,在没有修改cs之前的代码怎么执行的,如果在这些指令执行到一半,我在中间干点别的事情,那么是处于什么情况。这些疑惑一直困扰着我,简直就不能接着干下去。当然这些疑点最终还是被我搞明白了。

导致我写这篇文章的是搞清楚gtd地址翻译的方法。一开始我看到描述符里有一个base字段,我就非常努力的想理解其含义。首先我是这样想的:如果我的链接器认为,程序将会加载到0x40000000这个地址,那么它里面的指令就都是根据这个地址来的,比如一个全局变量,可能就在0x41000000,而实际在物理内存中可能就是在0x010000000那么假如我的base写的是0x40000000,对应到物理地址就应该减去base了。但我又有些犹豫,觉得按照各种指南中模糊的描述来看,也有可能是加上base。这个疑问很麻烦,除非写一个内核代码来测试,但在那之前,我有幸找到了答案。便是通过Intel® 64 and IA-32 Architectures Software Developer Manuals,终极文档。里面写的清清楚楚:

The base address plus the offset thus forms a linear addressin the processor’s linear address space.

还附带了若干图例,把整个一套相关的内容都解释了,堪称完美,让我瞬间为自己到处找tutor和看别人笔记浪费的无数时间感到可惜。这样细想一下,原来不是通过减去0x40000000,而是加上0xC0000000来实现的。于是我得到了一个教训:有问题记得看手册

我必须要说一件事,写指南是一件很麻烦的事情。尤其是为初学者所写的指南,我已经在计算机别的领域有怎么也还算丰富的经验,然而初次涉及内核的开发,依然面对了重重的困难。作为一个有经验的作者,往往不容易回忆起自己刚开始摸索一件事物的时候面对的重重困难。可以回想你开始学习编程的时候,各种各样眼花缭乱的交错的概念理解起来多么困难。

而如果是一个像我这样希望对每一步的细节都非常清楚的读者,恐怕只能寄希望于作者多多花费心血讲解细节,亦或是及时指出可靠的参考材料。一个指南假如仅能通过复制粘贴然后改改其中参数的方法来使用,那么其学习价值恐怕很难得到保证。

所以我希望有志于编写指南传播经验的同学可以谨慎地进行自己的工作,让阅读的人能更好的理解。我如果有机会写点什么指南的话,必将朝着让大家理解的方向多努力。

Read More...

对长期纠结的PL和CC相关内容做一个小结 2013

published on

回顾一下在编程语言和编译原理方面的各种纠结,没有什么记录,凭记忆写。

我从高中毕业开始使用C++,到现在挺多年了。语法是靠高中看数据结构的书看会的,后来到了大学里面喜欢泡图书馆,大一时靠读了不少C++的经典奠定的基础,像是Effective C++,Exceptional C++等系列,有蹭着和学软件工程的同学讨论项目,自己翻一翻设计模式什么的书,学会了一点怎么用C++写项目,算是我第一个用着很熟悉的语言了(之前用过VB Pascal,均仅限于学习写所要的程序的必要的知识部分)。

在大二的样子,出于学习算法的目的也要考虑编译方面的算法,于是在图书馆了翻了不少相关的书,诸如传说中的三件套:龙书,虎书,鲸书,当然还有一些其他的玩意。比较喜欢的是虎书,所以借过好几次,慢慢的读。看的是虎书的C语言版,不过这就是按照ML语言版改写过来的,对象都是申请了之后不考虑释放的,里面实现的语言的语法也是参考者ML来的。我从那里面学到了不少东西,而且第一次注意到写程序还可以使用immutable的数据结构。也喜欢上了ML的语法。

再后来因为自己写游戏的原因,学习了lua语言,反反复复的用,把大部分特性都搞的差不多明白了,后来干脆把源码也全部看了一遍。lua这条线的话,后来发现了LuaJit这样一个玩意,遂对Jit产生了兴趣,在网上找了一些paper和code看了一下,之后又读了intel和amd x86-64芯片的手册,可是最后还是没有自己去写一个。

因为经常和lua拿来放在一起讨论的Google所做的JavaScript引擎v8,所以其相应的代码也拖下来读了一些,结果学了不少C/C++中的宏的使用技巧。

另外在学校的图书馆里找到了一本转本讲垃圾收集的书,里面对各种方法的各种讨论让我大开眼界,每一种现在用的收集策略都讨论了各种优化方法。我才意识到,原来这东西有这么多人研究啊。后来在LuaJit的Wiki上也发现一篇讲gc的内容,看起来还在等人赞助他加进去。

之后因为看两大名作SICP和CSAPP的缘故,接触到了Scheme,当然这不是最早接触的Lisp,最开始是高中的时候开始学着用Emacs,那是就摸索着写了一点Emacs Lisp。所以用Scheme的时候没有什么语法不适应的障碍,反而看SICP学了不少函数式编程的知识,当时触动特别的大,因为是第一次直接的接触到函数式编程相关的内容。

后面因为黑客与画家的原因看过一点Common Lisp,实在是不喜欢就弃了。所以Lisp这条路线基本一直是喜欢scheme的。scheme这条线下来,先是发现了有continuation和cps这样的东西,但是靠网上依稀的资料不是很明白,直到后面看了EOPL和PLAI,自己写解释器,慢慢就搞明白了。看到Y-combinator,然后自己推导过后,也学会了。后面也专门看过用Scheme的实际项目:Lilypond,可惜量太大,实在没耐心分析到最后。宏是最后在Cousera上选了一门Programming Language的课,听讲义学的。我个人绝对是听觉型的学习者,特别喜欢听老师讲,但老师太难找了,还是不得不努力的看了不少书。

Scheme这边发展后后面,对于怎么实现函数式语言的优化编译器又产生了性质,还找了一些书和paper,讲怎么写函数式语言的编译器,或者诸如对于动态语言,怎么通过尽量的静态分析,可以消除大部分运行时的类型检查。

还有一条线是考虑学一点实用的语言,于是看了Python和Ruby,Python没怎么看书,就随便看看tutor,看看别人的程序,然后慢慢居然也用熟了,Ruby正儿八经看了影印版的The Ruby Programming Language,最后还是没记住多少,学语言果然还是靠多写。再想想看个速度快点的,于是学了Go,看了tutor,最后还是没怎么用。一般还是C++/Python使用最多。

再有一条线就是几度尝试Haskell,尝试着看了一些资料,Tutor或者书。觉得实在是一门麻烦的语言,平时用来解决一般的问题都要采用这样的思路没必要,故没能更近一步。

然后再回到C++吧,后来网上看过不少C++11的资料,然后看到了公开课cppgm,可惜知道的比较晚,人家已经开始了,看到其使用的材料的是C++的标准。想到自己从没看过C++的标准,于是网上搞了一份,不过一直没什么机会想起来把他看下去。

最后是最近在Coursera上搞了一门PL的课,认真学了一点ML的语法,复习了scheme/Racket,学会了在scheme中怎么写宏,然后又复习了一点ruby的语法,发现忘了不少。期间还有纠结在要不要去学scala,要不要自己再写一个新语言的编译器,啊这些恐怕要留待明年继续纠结了。

写完了之后总觉得还漏了些什么,诸如LLVM之类的,反正估计永远都难以写完整了,先这样好了。

Read More...

Go 语言中的 Slice

published on

按之前的笔记中许诺的,这回专门来讨论一下Go语言中的Slice。

构造

首先,我们可以看看这个东西是怎么实现的: 用C++来表示,它应该就是这样一个struct:

template <typename T>
struct Slice {
    T* buf;
    size_t size;
    size_t capacity; 
}

其中buf指向了一个数组,size是当前Slice的大小,capacity是指向的数组有多长。

相应的就有两个重要的函数lencap,分别返回sizecapacity

如果你了解C++的标准库,会不会觉得这个结构很眼熟?对了,C++中的vector就是这么实现的。当然在Go中,得益于gc机制,Slice就可以放开手做更多的事情了。

首先看Slice的构造, 两种方式:

  1. 为buf新申请一段空间: make([]T, length) or make([]T, length, capacity)
  2. buf指向已有的数组: a[low:high]

vector不同的是,可以Slice指向已有的数组,而vector不能。

代替vector

我们先看最基础的功能,使用Slice来代替C++中的vector。

此时所需要的两个最核心的功能就是push_backpop_back,使用Slice的时候可以使用这两个函数的强化版本:

push_back对应到append,在Go里面可以使用append添加一个或者多个元素到Slice的结尾。由于从文档中看不出来会不会使用capacity*2的策略,所以如有需要可以自己写一个push_back如果需要扩展capacity就乘2好了。

pop_back就很简单了,直接用Slices功能,从现有的里面切出来一段新的即可。

由于上面说到自己实现append,那么就需要一个copy函数,把旧的Slice中的内容复制到新的中,这个函数语言中也已经提供了~

当然上面说了这么多,因为对于这些函数来说,可能会通过指向一个新的Slice来完成扩展的操作,所以不会和vector的接口做的完全一样。不过为了使用方便,我们当然可以把它做得完全一样,只要自己写一个struct将Slice包一下就好了。

表示已有数组区间

有时候,我们并不是需要动态改变Slice的大小,只不过是想要表示一个现有数组的一段。你有没有在用C/C++时在程序中出现过类似下面的函数签名:

void func(T* arr, int left, int right)
void func(T* arr, int size)
void func(T* begin, T* end)

现在好了,只要一个Slice,里面这些信息都包含了。看到那里面的beginend会不会让你想到很多的函数呢,是的,现在他们可以只需要一个参数了:)

少量用到数组区间的算法的例子:

  • 快速排序
  • 线段树

小结

这里简单的讨论了go语言中Slice的内部结构和一些使用场景。许多别的语言中要实现一个类似的玩意也不难,在没有gc的语言中如果要使用需要留意,用起来可以带来一些便利性。

Read More...

cppgm - C++大师认证

published on

在网上闲逛的时候意外发现了这个非常强悍的在线公开课。你在Google上用cppgm作为关键搜索,马上就能找到这个强悍的项目的主页。

就目前从主页上能得到的信息来看,这个项目是从今年(2013)年初开始,到目前已经有不少任务了。下一轮是从2015年开始,现在主页上已经可以通过他们的邮件组来接收下一轮的信息了。

目前这一轮的目标是C++11,看完成目标非常imba啊:

  • 与最新的C++11标准兼容
  • 不使用第三方库,仅由标准的C++编写
  • 生成Linux x86_64的目标代码
  • 完整的工具链:预处理器,编译期前端/后端,汇编器,链接器以及标准库
  • 自举并且通过充分的测试

我找到了这个课程刚出来的时候在reddit上引起的讨论,群众主要有两个担心的地方

  1. 没有任何组织者的资料,只是一个CPPGM Foundation,不知道是谁搞的。现在看about页面里面可以找到instructor的信息,看了看以前在Apple和Intel呆过,大概还算靠谱。
  2. 工作量太大了。看上面的第四条,这课程野心真心不小,要兼容C++11拿数千页标准,然后实现这么一大堆的东西,绝对不是什么简单的事情。

于是有群众怀疑是不是某个秘密组织的招募活动…

当然看现在官网上的论坛,还是有不少人做的挺欢乐的。而且课程很严,只要一个assignment超过deadline就byebye了……

就我个人来说,我个人是C++的爱好者,所以还是很倾向于参加这么一个活动的。就是这个玩意的工作量真是不小,而且有一个限制:为了避免抄袭,不能在网上发布你的代码。只有在作为应聘或者申请某些材料的时候向组织者申请许可。

感觉有了这个限制就很不爽了,毕竟这玩意工作量这么大,做出来不让放出来的话,没有这儿成就感的驱使还是很难做到坚持到最后的。不过到2015年下一轮开始之前的时间还早,我还可以慢慢在纠结着。而且说不定期间出现了什么牛逼的玩意就让我不想深入折腾C++了(要是rust给点力,以后就是它了)。当然15年C++14也差不多了,估计也会挺带感的。

欢迎大家一起关注~

Read More...

使用Apache代理SSH

published on

有时候需要通过代理连ssh, 记一下其中一个方法,在代理服务器上起一个apache作为代理。核心部分,主要是配置。

配置apache作为ssh的代理

  1. 编译apache, 带上proxy的插件。 ./configure --enable-proxy --enable-proxy-connect --prefix="路径" make make install
  2. 修改conf

    • 加入正向代理: ProxyRequests On ProxyVia Full AllowCONNECT 22
    • 不控制权限 <Proxy *> Order deny,allow Allow from all </Proxy>
    • 另注意Listen命令描述了监听哪个端口,一般默认应该是80,可以自己改
  3. 加入密码验证

    <Proxy *>
    Order deny,allow
    Allow from all
    AuthType Basic
    AuthName "Password Required"
    AuthUserFile password.file
    AuthGroupFile group.file
    Require group usergroup
    </Proxy>
    
    • 其中密码文件的得来: htpasswd -c password.file username
    • group.file文件内容: usergroup: username 这两个文件都放在apache的根目录下
Read More...

Go语言观察笔记 [中]

published on

方法的定义

Go中可以给Struct定义方法(只要是同一包中,非结构体也可),类似给一个类添加成员。只是这个方法定义的时候不写在Struct中,只要是同一个包中的文件都可以对它扩展,为它添加方法。这个设计还是很好的。有点类似C++中的namespaceclass,你可以在class中定义public static的成员来实现和namespace同样的效果,但是namespace可以把这些内容拆到不同的地方,而不用挤在一起。

写法:

func (v *Vertex) Abs() float64 {
    return math.Sqrt(v.X*v.X + v.Y*v.Y)
}

然后有一个新的类型:接口

type Abser interface {
    Abs() float64
}

接口类型的变量可以保存任何一个实现了其中对应函数的类型的值,有点类似duck type的感觉。这带有一点在显示的实现声明和纯动态类型中间的折衷把,属于用不那么严格的约束来换取便利。

这个玩意如何比较好的实现是个有意思的事情。初步估计应该是类似一个vtable那个的结构,每个值都是一个闭包。当然因为这里的闭包的环境实际上都是共享的,所以存一个指针就好了,恩这样创建一个新的时候也只要设这一个指针,别的设置在编译期都可以搞定。

这件事情我之前在玩lua的时候倒是干过。我用C++的模版元编程机制实现了一个把C++的类自动导入到lua中的办法,在lua里面就是用table + closure来实现的。方便我可以自己写成:

a.do_sth();
-- but not  a:do_sth()

因为luaa:do_sth这个设计实在是不爽,你就算不小心写错成.了,语法上也没任何问题,运行时搞不好都检查不出来,行为是不确定的。主要的缺点就是如果table中方法太多了,创建起来比较耗时,所以我一般就导导函数给lua,而不用什么类。

再回来看接口,tutor介绍了一个常用的叫error:

type error interface {
    Error() string
}

Tutor中这一篇到这居然就完了,往后走就是并发……

好吧,你的类型系统里是不是少了点什么? datatype呢…… 什么原来没写在tutor里,我在effective_go里找到类似的东西了:type switch

恩这个卧槽的做法如下:

func f(x int) interface{} {
    if x < 0 {
        return 3
    } else {
        return "str"
    }
}

func main() {
    var t = f(2)
    switch t.(type) {
    case string:
        fmt.Println("string")
    case int:
        fmt.Println("int")
    }
}

说实话有了这些基础的话,用起来就没什么问题了,并发这件事情并不是干什么都要用的,实际上Go的并发模型基本上是为服务器设计的,所以之后再慢慢看。

Read More...

Go语言观察笔记 [上]

published on

正文之前

最近吉他班上完了,在凑齐人上高级班之前多写点Post。

本来想写点Continuation相关的东西,类似call/cc, coroutinecps什么的, 但是暂时没拿准怎么动笔比较好。这些东西在我自己搞懂之前,看过不少讲解,还有很多例子和比喻,最后都不知所云。搞懂了之后再去看,就知道在讲什么了。所以我可能会试着写一点draft,但是要到能放出来可能还要花一些时间去琢磨下。

最近对Go有了点兴趣,想看一看。当然很大程度上我只是想找一门带有以下功能的语言:

  • 静态类型
  • GC
  • 丰富的库,易用的包管理器

语言设计本身倒是题外话了,比如我最喜欢scheme,但是其标准库实在是没什么到操作系统的接口,能做的实事就偏向纯计算了。什么你说有扩展,好吧每个实现扩展的都不一样…… 这用起来也太残念了吧。

所以现在先来看Go,看完了准备看Rust。

于是这里的笔记和评论是来自一个初学者的看法,所以大家不要吹毛求疵了。

路径

Go的开发涉及两个路径,一个叫GOROOT,一个是GOPATH。简单来说GOROOT是Go安装的位置,GOPATH是开发的工作区。

如果像我这种懒人在Windows下用msi安装的,只要配置一个GOPATH的环境变量即可。Go相关的程序在GOROOT/bin下,而第三方程序和你自己编译出来的就在GOPATH/bin下

另为了配合包管理器,最好顺便把git和hg装上

Tutor

Go很不错的一点是自带了一个指南,我就准备一边看指南一边往下写了。

首先指南被分为3部分,基础概念,方法和接口,以及并发。那么我预计也拆3篇分别写写。

基础概念

分包是个好的idea, 新一点的语言大多都带上了这个特性。

Go里面需要显示在文件头部写上package xxx,如果是lib,就取最近一级文件夹名(其实应该是建议文件夹名就取lib名),如果是执行程序,就用package main

如果是导入的话写成

import "fmt"
import "math"

import (
    "fmt"
    "math"
)

当然按照我的习惯,肯定会选前一种,因为每一行做一件事修改的时候看diff会比较舒服类似:

 - import "math"
 + import "net"

 - "math"
 + "net"

这样你会发现看下面这个光看修改的这一行不会很确定是改了啥,这就需要diff提供足够多的上下文了。这其实也是一个你最好每行只定义一个变量的好理由。

函数和类型定义

Go的类型表达式其实很搞,从看上去的样子推测。应该是故意采用把c语言的定义方式反过来似的。

比如(先抛开var func这两个关键字) :

  • C:int a,Go:a int
  • C:int a[3], Go: a [3]int
  • C:int *a, Go: a *int

然后函数定义:

  • C: int a(int x, int y), Go: func a(x int, y int) int

怎么样,像不像是故意反过来的。

Go的网站上其实有一个专门的页面讨论了这个问题,因为这种类型的写法人比C的容易理解,更加nature。

嗯,当然了,这种后置的类型写法自然比C容易理解。当然说实话我觉得能比C的类型写法更难理解的语言实在是不多了。你既然都不沿用C的写法了,就不好好考虑下把类型的声明方式搞好一点么。

这样一后置,哪怕学学pascal,写成func a(x:int, y:int):int我觉得也看得爽一点。

来换用不同的语言上几个例子感觉一下:

  • Go: func map(f func(int) int, s []int)
  • C: int[] map(bool (f *)(int), int s[]),当然C其实没有bool,数组还要另外传长度,这样太苦了我们就放过把。
  • C++: vector<int> map(function<int(int)> f, vector<int> s),当然为了写短点我把名字空间去掉了。
  • Pascal: function map(f : Functor, s : IntArray) : IntArray,当然pascal很贱的不让你写一个复杂的类型表达式,而只能一步一步通过中间的类型名称来。所以pascal种类型名字很重要。
  • Haskell: map:: (Int -> Int) -> [Int] -> [Int]

懒得列下去,欢迎大家多找找。

Go这里还有另外一个比较蛋疼的设计就是可以缩写:比如func go(x int, y int) int可以写成func go(x, y int),这个实在是太囧了,我看了好久都不能习惯。原因在于你会注意到这里有一个微妙的优先级不一致性:在前一个写法中,我们看到的东西类似于[x int], [y int],而在第二个场景下就变成了[x,y] int,注意按照这个标注,在前一个方案里面,空格的优先级是比较高的,而在后一个方案里面,又要让x y先按,结合起来,再去一起看后面的类型。这应该就是这里有点反直觉的感觉的地方吧。

由上我不推荐使用这个缩写,其实Go为了简化写法带来的设计基本都有点不给力,实在是郁闷。

然后函数可以返回多个值,如例

func swap(x, y string) (string, string) {
    return y, x
}

不得不说要能写成

func swap(x:string, y:string) : (string, string) {
    return y, x
}

不是很好嘛。不过这个功能是很好的,而且还有可以写成命名返回的方式。类似Pascal中通过给函数名赋值来指定返回值:

func swap(x string, y string) (a string, b string) {
    a, b = y, x
    return
}

变量定义

写法:

   var x, y, z int
   var x, y, z int = 1, 2, 3
   var b1, b2, s1 = true, false, "no"

上面第三行提供了类型推倒

另一个带了类型推导的写法:

b1, b2, s1 := true, false, "no"

为什么要发明一个这么不一致的写法,我只能猜测,大概是为了写出下面的代码:

for i:=0; i<10; i++ {
     fmt.Println(i)
}

好吧,我也不知道在Go里面为什么不支持写成: for var i=0; i < 10; i++ {,而非要发明新的写法。等我再看到后面如果发现别的地方要用到再说好了。

另补充,把var换成const可定义常量

基本类型

  • bool
  • string
  • int int8 int16 int32 int64
  • uint uint8 uint16 uint32 uint64 uintptr
  • byte
  • rune
  • float32 float64
  • complex64 complex128

控制流

  • 循环: for
  • 条件: if,条件中可以加分号;,这样可以像for一样先执行一句话,应该是为了方便定义一部分只在if中用的变量(同时在条件和body会用的那些),这样可以限制这些变量的作用域,使变量局部性更好,代码更容易读(过了这段就可以忘了这个变量了)。

Struct

基础篇里面的struct估计是在为后面的接口篇打基础吧,就当是这样好了,先接着看。

定义一个struct,老规矩,和C反过来:

type Vertex struct {
    X int
    Y int
}

恩,这里也可以缩写,缩写也是和c的缩写反过来的X,Y int

使用和C一样都是用.,初始化的可以直接指定每个字段的值,否则就默认填0了

指针: 类型如上所述是写成 *Vertex,Go里面指针直接用.就相当于->了。指针不能进行算数运算(否则没办法实现靠谱的gc)

通过new(Vertex)可以分配一个新的Vertex,虽然Go里面把new称作函数,但是估计还是当作一个运算比较好,因为其接受的是一个类型而不是值。到目前为止暂时没看到Go提到类型是值的内容,因为听说有反射,估计可能确实类型就是值,等看到了就当这段没说好了。

Slice

Slice就是带有长度的数组,类似C++的vector,但用处不同,Go tutor链接到了一篇文章专门讲Slice的,留待后面看了补一篇关于Slice的讨论好了

For-Range

for还有另外一种写法:

for i, v := range []int{2, 3, 5, 7} {
    fmt.Printf("%d: %d\n", i, v)
}

map

map就是来自C++的map,存放一个字典。写法略微妙:var m map[string]Vertex,表示keystring类型,valueVertex类型。嗯,再揣摩一下设计的用意是说这个m的类型表示你需要用一个string类型的值放到方括号内,像这样:m[str],你就得到了一个Vertex类型的值嗯。好吧管他原意是什么,就这样吧。

字面量的写法类似Json。

delete(m, key) 用来删除。 elem, exist = m[key]。这样可以用exist检查是否在其中。

函数可以作为值使用

也支持词法闭包,恩非常好

switch

switch语句不需要手工写break了,如果要往下,就写上fallthrough。可以去掉表达式当作lisp中的cond语句来用

上篇完

还剩下slice,之后来讨论。

接下去应该就要进入接口篇了。

Read More...

怎样调试程序2 - 各式各样的bug

published on

介绍一下常见bug的分类,这个是我之前从Udacity的Software Debug公开课上看来的,挺有意思。

Bohrbug

指一个稳定的bug,名字取自波尔的原子模型。这些bug行为稳定,你可以通过特定的方法来复现,一般只需简单的将其修正,再用同样的步骤验证其不再出现即可。

Heisenbug

这个名字取自海森堡测不准原理,即观测会对结果产生影响。

就是说一个bug,正常运行的时候会发生,但是当你尝试去调试它的时候,它又正常了。

这种情况其实非常常见,当你调试程序的时候,你可能需要在程序中插入一些log指令来记录下关键的调试信息,或者在一个debugger中运行你的程序,这使得和正常运行的时候产生了不同的结果。

这种bug的常见起因有以下几类:

  • 没有初始化的变量,恩常常在调试器中因为内存布局发生改变就初始化了。
  • 浮点数相关的编译优化,浮点数相关的计算开了编译优化之后往往和编译前不完全等价,在不开编译优化进行调试时可能就没能触发特定的bug。
  • 并发场景,在竞争的情况下,速度慢的程序可能就撞不上bug了。

Mandelbug

这个名字来自于曼德博的分形学,分形的思想常被用于模拟真实世界混沌粗糙的现象。在这里Mandelbug就是描述某种牵涉到方方面面原因的bug,以至于你根本不知道该怎么下手去修复。甚至可能你只能知道这里有个bug,但完全理不清背后的原因。

这种现象在现实中的逻辑复杂的软件中时常可以见到。尤其当你去留意各式各样关于赶时间的游戏开发者调试和修复bug的趣闻的时候,你可以收集到大量这般莫名其妙的bug。

Schrödinbug

这个名字来自著名的薛定谔。这使说系统中有一个bug,但是没人知道。直到有一天一个程序员仔细看了代码…… 恩,你懂的,就是在说那个没人看就即活着又死了的猫。

想看一点例子么,你可以去stackexchange.com上去找到相关的问题,在这免费给他们打个广告。

最后的补充

上面4个是从课上听来的,下面来一个从Yin Wang的blog上看到的:Higgs-Bugson

一种假想中的 bug。它一般是跟据运行日志的少数记录和零星含糊的用户报告推测出来,但是在开发员的机器上很难重现。

这个名字是来自希格斯玻色子(Higgs boson),是一个理论模型中预测出来的粒子,直到2013年才被实验证实。

Read More...

怎样调试程序1 - 序

published on

准备写一个系列,介绍调试程序的一些方法。调试程序是在学校里面最难学到的,非常需要实践训练的一项技能。因为今天时间不多,先写个序,之后慢慢的写。

总体来说,调试的总体思路是:

观察现象 -> 建立假设 -> 设计实验 -> 验证假设

一旦假设通过,分析出出现现象的原因,那么就可以根据原因进行相应的fix了。

当然其中的会涉及到很多的因素(也就是为什么目测可以写一个序列了):

  • 对待调试系统整体的熟悉程度
  • 调试工具,以及对调试工具的熟悉程度
  • 调试的策略
  • 推理的能力

等等,这里只是举了一些基本的例子。实际中,经验也会是极其重要的一部分,所以多写程序,多调试的路线是不可避免的。

参考资料

以前,谈论调试的资料还是比较少的,现在就不一样了,你在douban上搜索调试,可以找到一系列的教程,在公开课程网站udacity上还有专门的软件调试公开课。所以你不一定要看这个序列的教学,也可以考虑去找本书看看,或参加一个公开课程。

总之请等待之后的文章吧。

Read More...

垃圾回收机制简介

published on

什么是垃圾回收?

如果你是一个传统的C/C++语言或Pascal语言的用户,可能会对垃圾回收这个名词感到模式。而对于函数式语言来说,垃圾回收一直是一个不可缺少的组成部分。到目前来看,凡是比较新的语言,不管是不是函数式的,基本都吸取了这个特性,提供了垃圾回收机制作为内存管理的方案。

那么什么是垃圾回收呢,对于C语言来说,你如果需要申请一段内存保存你的数据,那么在用完了之后,必须显式的告诉系统,这段内存不用了,而可以复用。这个要求对程序员的负担其实挺重的,必须清楚的确定每个对象的生存周期。而且在有的场景下,很难决定何时来释放这个对象(比如多线程环境下不知道别人在不在用)。

于是就会有自动的内存管理方案,垃圾回收机制产生了。其作用是在一个内存不用了之后,系统可以自动再利用这段内存,而不用产生泄漏。其要点在于及时。即不能太早也不能太晚,太早的话可能别人还要用这个对象,太晚的话就可能会浪费太多内存。当然这两个条件,不能早是绝对要满足的,而是否可以晚一点是一个相对宽松的条件,可能会为了各种因素来取舍(比如性能)

那么如何进行垃圾回收呢,其主要分成两个部分

  1. 如何判断一个对象是否可以释放了
  2. 如何管理内存的申请和释放的操作

基本方法

实际使用中,垃圾回收可能是很多方法组合而成的,而其基本的思路基本有3种:

  • 引用计数
  • 标记-清扫
  • 节点复制

引用计数

引用计数的原理比较简单,只要我在每个对象的开头附加一个域,统计有多少个指针指向这个对象。当指针赋值的时候,被指向的对象的计数+1,没被指向的对象的计数器-1。当一个对象的计数器变成0的时候,说明没有指针指向它了。那么就可以释放掉它。

比如C++中的std::shared_ptr就是使用引用计数的原理来实现的。

引用计数的优点:

能很快的进行释放,如果没人用了,马上就能知道。这属于渐进式的收集,和那些一开始垃圾回收就要停住别的地方的程序相比,是个很大的优点。

能马上知道何时可以回收的好处还有别的一些,这里就不多展开了。

引用计数的缺点:

  • 最主要的缺点是对付不了环形的结构,如果A对象有B对象的引用,而B对象又有A对象的引用,这样他们的引用计数永远都不会变成0,即使没有从全局变量区或堆栈来的指针能都访问到他们了。
  • 第二点比较复杂的是如果是多线程的环境下,维护引用计数的成本很高。需要使用锁,或者复杂的硬件机 制来保证原子性。
  • 第三点是它需要附加一些空间来保存引用计数的值。在小对象多的情况下空间浪费很高。

尽管有缺点,但都会有人研究怎么补偿这些问题,但是这里只是做个简介,就不再展开。

标记清扫

另一个被广泛使用的计数就是标记清扫。比如在lua就是用了一种渐进式的标记清扫算法进行的垃圾回收工作。boehm给C做了一个保守的收集器,也是基于这个算法,而且这个收集器被guile拿去用在收集scheme里面的对象了。

其基本原理如下,假设分配程序叫alloc_mem:

alloc_mem(size) {
    if (!pool_can_alloc(size)) {
        mark_sweap()
    }
    return alloc_from_pool()
}

mark_sweap() {
    // mark 阶段
    mark(root)
    mark(stack)
    // 清扫阶段
    for (object : all_objects) {
        if (not_marked(object)) {
            free(object)
        }
    }
}

mark(object) {
    // 标记当前的对象
    set_marked(object)
    // 递归的去标记改对象引用了的那些对象
    for (ref_obj : get_ref_obj(object)) {
        mark(ref_obj)
    }
}

简单来说,就是把引用关系看成一个有向图,做一次dfs,把能到达的对象都标出来,剩下的统统干掉。

这里面可能要考虑的一些问题:

  • 这里是stop the world的收集,也就是说一旦进入了这里面,程序遇到内存分配的时候都得等在这。所以基本上就干不了什么事了。在一些实时性要求比较高一点的地方就不好使用了,简单的话可以在比较要紧的时候禁止执行gc,过后再说,当然更好的是用渐进式、分代等优化策略。
  • 这里mark的过程是递归的,实际实现的时候要考虑堆栈溢出的风险。尤其是想想如果遇到一个很大的链表的时候。这里面也有一些相应的技巧可以降低gc过程中对内存的消耗。

节点复制

节点复制算法比较有意思,就是我现在的堆我只用一半,当这一半满了的时候,我们按照标记-清扫的办法来寻找存活节点,在寻找的时候我们并不用进行标记,而是将其复制到堆的另一半里面。这样标记的过程一完成,我们就把所有存活节点弄到新的半区去了,然后记得把引用改成到新的半区里的对象的位置,旧的半区直接抛弃就行了,接下来就可以在新的半区继续分配内存了。

这样做的优缺点和前面的方法就截然不同了:

优点:

  • 分配内存简单:每次只要在上次分配的地方再继续往后分配即可
  • 对象都连续存放在一块,对缓存友好
  • 只要访问存活的对象就行了,而不像标记清扫算法那样在清扫阶段会访问所有对象

缺点:

  • 复制起来需要花费时间(特别如果都是大对象)
  • 需要留出一半的空间

这个方法带来的移动对象可以提供命中和简化分配是一个很好的思路,所以为了不用两个堆,就产生了标记-缩并的思路:在同一个堆里先标记,再把存活对象纷纷往前移动到开头的位置。在javascript引擎v8中的垃圾回收就是用缩并的方式进行的。

进一步的内容

垃圾收集相关的研究相当之多。有一本非常好的书对各个方面进行了详尽的讨论:《Garbage Collection: Algorithms for Automatic Dynamic Memory Management》,而且居然还有中译本,虽然翻译的已经绝版了。

里面还进一步涉及了下面一些更高级的主题

  • 分代,很多对象生命周期很短,而长的一般保持很久,所以收集的时候可以将它们区别开。
  • 渐进式,平滑的收集需要的一些技术。
  • 并发式,在并发环境下怎么进行垃圾回收。
  • 硬件相关 / 缓存利用

(完) 本来想配点图的,终究又不知道怎么画比较好,于是放弃了。

Read More...

使用markdown来编写一本书

published on

有时候,我们时不时会冒出写一本书的想法。如果是小说,那么都是一些文本,写起来问题不大,而如果是技术书籍,你就会对排版这件事有一些担心,优秀的排版效果是一本优秀的书不可缺少的内容,尤其是当里面有很多数学公式或者代码的时候,排版的效果对于看书的人来说影响还是挺大的。

这种时候,你回去找一个排版工具,比如Word或者是LaTeX,但是你会发现Word用起来比较麻烦(咦?当你的内容多了,每个内容去排版保持一致性比较费事),而用LaTeX还是有点麻烦,因为你老是写成一些类似下面的代码

    \section{这是一章}
    \subsection{这是一节}

    一部分正文
    \begin{itemize}
       \item 列表项1
       \item 列表项2
    \end{itemize}

这样,这里面其实冗余比较多,和html比较类似,源文件比较繁琐,也不是很适合直接阅读。所以考虑到我们可以用markdown来生成html (不知道markdown是什么?搜索引擎可以帮助你。),于是我们也可以试着用markdown来生成pdf

用到的工具

  • pandoc 这是一个强大的格式转换工具,我们可以依靠它从markdown转换成很多别的格式。这里我靠它转换成latex再进一步生成pdf。实际上也用通过markdown产生html再产生pdf的用法,看你对哪种方式比较熟悉即可。
  • python 脚本语言,用来制作build脚本,实际上你可以用很多别的东西来代替比如ruby makefile或者是doc的批处理等。
  • texlive 用来将.tex文件转换到pdf,由于需要考虑支持中文,我们使用里面的xelatex程序,实际上还有不少tex的可用环境比如MikTex

然后开始动手

先看我们的目录规划:

    content/
       \-  chapter1.markdown
       \-  chapter2.markdown
             ...
    meta.json
    process.py
    template.tex

content下面就是我们写的内容了

meta.json是一个用来描述我们书本结构的东西。具体内容我随手定了一个:

	[
        { "name" : "Part1", 
      	  "chapters" : [ 
              { "name" : "The My First Chapter", "file" : "content/chapter1.markdown" }
              { "name" : "Other Chapter", "file" : "content/chapter2.markdown" }
          ] 
        }
        { "name" : "An other part", 
      	  "chapters" : [ 
              { "name" : "Just another Chapter", "file" : "content/chapter3.markdown" }
          ] 
        }
    ]

这里面描述了书的结构:一共两个部分,第一部分有两章,第二部分有一章。我用这样一个文件来描述这样一个结果,如果你的书结果比较简单,比如直接按章分了,那么甚至可以省略这个文件。只要构建脚本里面能够正确理解章节的结构即可(比如通过文件名的模式来理解)。

然后process.py文件是负责构建的脚本,具体内容如下:

    import subprocess
    import json
    import os
    from string import Template  

    import sys 
    reload(sys) 
    sys.setdefaultencoding('utf8') 

    def get_file_content(filename):
        f = open(filename)
        data = f.read()
        f.close()
        return data

    meta = json.loads(get_file_content("meta.json"))

    content = ""

    for part in meta:
        content += "\part{%s}" % part['name']
        for chapter in part["chapters"]:
            content += "\chapter{%s}" % chapter["name"]
            content += subprocess.check_output(["pandoc"] + [chapter["file"]] + ["-t", "latex"])
    
    t = Template(get_file_content("template.tex"))

    f = open('output.tex', 'w')
    f.write(t.substitute({'body' : content}))
    f.close()

    os.system("xelatex output.tex")

可以看到其就是根据meta里面的描述,调用pandoc生成latex格式的内容后拼起来,并替换了template.tex文件里面的body部分,然后调用xelatex进行输出。template.tex就是tex文件的模板了,用来控制具体的输出效果,这里给一个参考的:

    \documentclass{book}
    \usepackage[BoldFont,SlantFont,CJKchecksingle]{xeCJK}
    \setCJKmainfont[BoldFont=SimHei]{SimSun}
    \setCJKmonofont{SimSun}
    \parindent 2em

    \usepackage[pagestyles]{titlesec}
    \titleformat{\part}[display]{\centering\Large\bfseries}{第 \thepart 部分}{1em}{}  
    \titleformat{\chapter}[hang]{\Large\bfseries}{第 \thechapter 章}{1em}{}
    \titleformat{\section}[hang]{\bfseries}{第 \thesection 节}{1em}{}      
    \titleformat{\subsection}[hang]{\bfseries}{第 \thesubsection 小节}{1em}{}      

    \title {测试的主题}
    \author {作者}
 
    \begin{document}
    \maketitle
    \tableofcontents

    $body

    \end{document}

下一步

  • 试着自己来写一本书吧。
  • 写书的时候还要考虑一些别的章节,比如前言和附录,为了简单起见,这些内容这里面都没有处理,为你的书加上这些内容。
  • 如果你的书本里面有代码,试着写个脚本把代码抽取出来进行自动的测试,使得他们编译,运行都无误,如果注释里面有测试数据,还应该可以进行自动化的验证执行结果。这样你就避免了很多书籍里面都能见到的错误。
Read More...

TopCoder题解 - DefectiveAddition

published on

这次偷了点懒,选了一道850分的,吃午饭前看了题意,吃饭的时候简单的想一下,回来写下来也不长就完成了。

题目来自SRM564 Div I,叫 DefectiveAddition

题目大意

给定一个数组 cards[],大小50以内,再给出一个数n,要你找出另一个数组a[],长度和cards[]相同,且对应项都不超过cards, 即满足 0 <= a[i] <= cards[i],并且要求a[0] xor a[1] xor ... a[m] = n,其中m为数组的长度

基本想法

看到xor运算,有经验的人很容易想到每一位之间是互相独立的,很多问题就可以利用这个特性按不同的位单独处理即可。

这个问题稍微有点麻烦的在于,稍微想一下很容易明白,低位上可能的取值是对高位是有依赖的。不过就算是有这个条件,最高的那一位是不依赖别的位的,所以可以从这上面开始考虑。

首先看一下样例,可以先解决掉一种极端情况:n 位数太大了,以至于不管怎样最后xor出来的结果都不可能达到n了,这种可以简单的先排除掉。

现在看所有的数最高为xor起来的结果,就两种可能:01,如果这一位的值和n对应的这一位不相等,那么可以认为至少有一个高位为1的数,最后变成了高位为0的数。 而如果高位异或起来和n相等的话,就存在所有的数高位不变的情况。但是所有数高位不变的情况其实很好处理:我们只要把所有数(包括n)这一位去掉,然后还是同样的这个问题求解即可。

现在就剩下高位至少有一个从1变为0了的情况。

方案计算

现在考虑高位至少有一个位数从1变成0了怎么统计方案数。

直接考虑有点麻烦,先看假如我们枚举每个数高位是0还是1,全都的数都定下来了之后,我们就知道每个数剩下的位数有多少种取值方法了:

  • 如果高位不变,则相当于去掉高位,可以从0取到剩下的数:比如11保持高位不变,则有11 - 8 + 1 = 4
  • 如果高位从1变成了0,那么低位可以任意取01,所以有2^k种:比如11可以选0->7 8种

注意到从1变成0的那些数的低位可以任意取,而且现在至少有一个,所以我们留下第一个(编号最小的),让剩下的数随便取 (用乘法原理即可得到方案数)。这个数的取法会由剩下的数确定下来(可以通过其它数xor完之后再和n求异或的结果确定)。所以这样我们就计算出了方案数。

但是,这样算很慢,因为要枚举方案数,所以复杂度略高。但是熟悉的同学很快会发现这个枚举可以通过动态规划的方来快速计算。方法是这样的:

我们用 f[i][j] 表示前 i 个数中,有j个从1变到0的数的情况下,方案数是多少。计算方法如下:

# if cards[i] 高位是0:
  f[i][j] = f[i-1][j] * (cards[i] + 1)
# else: cards[i]高位是1:
  f[i][j] = f[i-1][j] * (cards[i]去掉高位 + 1) + f[i-j][j-1] * (2 ^ k) [当j>1的时候]

这样递推一遍就是了。

整体做法相当于这样:

  • 检查是否无解,直接返回0
Read More...

Topcoder题解 - UnkownTree

published on

2013年开始了,今年我准备学不少新东西,而且已经学过的东西也挑选了一些内容准备 进行提高,而算法就是其中之一。因为以前已经在里面投入过不少功夫,所以想试试看 最高能达到怎样的程度。

对于训练来说,有两个很重要的要点如下:

  • 反馈,做了练习之后能够得知正误,反馈越及时越好
  • 在学习区练习,这一点简单来说就是练习需要能学到新东西,不要老是搞自己很容易解决的,但是也要是自己目前的能力可以接受的,要是完全搞不懂,也是浪费经理。

由于上面的第二点,我选择了Topcoder DIV1下面的1000pt的题目。这些题目的素质比较稳定,大多属于我个人可以接受的范围,也能够在线提交,得到方便的测试,及时的反馈。所以我今年关于算法方面的主要工作就是慢慢分析一些Topcoder的题目,可能不定期参加一些比赛。为了整理在思考这些题目中的思路,故预备整理一系列的题解。

这些题解主要记录我在分析这些问题中的思路,所以和正统的习题解答看上去可能不一样。不过对于想要借鉴的同学应该会有一定的帮助。

题目大意

这回我们选择的题目叫 UnkownTree 是SRM565 Div I的1000pt题

题意是说我们现在描述一棵树:

  1. 树上有3个点被标记为A B C
  2. 除了这3个点外还有N (1<=N<=50)个点,编号为1到N
  3. N个点到A的距离用数组distanceA记录,同样到B的距离用distanceB记录,CdistanceC同理
  4. 图中边的长度都是正整数

现在给定了distanceA distanceB distanceC, 问满足条件的树有多少棵(最后模一个数M避免大数运算)

初步尝试

拿到问题后最先想到的就是找几个例子,画几个图看看有没有什么规律。

画了两张纸后,看不出什么头绪,放弃……

于是转入了逐步分析的路线。

分析: 标记1个点的情况

首先想到简化题目条件,最简单的当然是只给定一个distance数组的情况。即只限制到A点的距离。

这样不是很难想到,我们将这个A点作为树的根,那么每个点的父亲要么就是A,要么是一个到A距离比自己更小的点。于是要计算方案也很简单了,我们知道每个点有多少个点可以作为它的父亲,那么这个点就有多少方案,整个树的方案数就是将各个点比其小的点的个数+1(根)乘起来即可。

这个状况可以参考下图来理解:

图1

分析: 标记2个点的情况

现在考虑给定到两点的距离的情况,现在A B被标出来了,已知所有点到A的距离和到B的距离。那么满足条件的树是什么样的?

首先我们会想找出A B之间的关系。很容易想到就是先计算A B的距离是多少。

一旦想到距离,我们就很容易考虑到一个问题: A B 是直接相连还是经过了中间某个点连接?

根据已有的条件,我们倒是肯定不了实际情况是哪种。但是我们可以分情况讨论:

A B 直接相连的情况

简单的分析可以得出现在任意一个点到A的距离和到B的距离的差就是A B间的距离。而且必须满足所有的点到A的距离和到B的距离差必须是都等于同一个值。此时AB的路线上不存在别的点

A B 不直接相连的情况

如果A B 没有直接相连,那么至少有一个点在A B之间的路径上,那么A B间的距离应该等于这个点到A的距离加上这个点到B的距离。在这个条件下,我们可以对所有点计算出两个距离的和,很容易想到最小的就是A B间的距离。

有了上面的思考A B,不难想到所有到A距离+到B距离等于A B距离的点都在AB的路径上

不在A B路径上的点

简单的画一下图容易发现,这些点肯定都通过AB路径上的某个点(包括A B),连接到的A B这两点。那么,我们把路径上的每一个点都看作根,别的每一个点很容易计算出是连接到哪一个根的,并且到根的距离是多少,这样我们就转化到了一个点的距离的问题!!用上面分析的方法算吧。

2个点的方法总结

最后回顾下两个点的情况的计算方法:

  1. 分两种情况(直接相连和不直接相连),分别统计可能的结果再加起来
  2. 对于每种情况,计算出A B路径上的所有节点 (为了方便,我们称这条链为骨架
  3. 对于不在骨架上的点,计算其通过骨架上哪个点连接到骨架中,并且距离对应点的距离是多少。
  4. 对于骨架上每个点,现在知道所有连接它的点和到它的距离,用前面分析的方法计算方案数,再把所有骨架上点的方案数乘起来即可。

完成: 标记3个点的情况

有了2个点的思路,很容易想3个点的情况类似,也是要先找出骨架来,不过再那之前,我们会发现这回要枚举的情况挺恶心的,因为每两个点都有可能直接相连,所以要枚举7种情况(不可能3个点两两相连,否则出现环了)。

枚举完之后,会发现骨架也有2中类型,如下面的图所示,这个可以通过计算确定出是哪一种,而不用枚举,不过要分情况处理。

2种情况

骨架确定之后,工作和2个点的完全一样了:每个点找一个位置挂上去,然后统计方案。

3个点的关键在于将要讨论的情况变多了,需要合理设计程序,使得共同的逻辑部分可以公用代码。各种情况处理的时候多加小心即可。这个代码量问题完全符合Topcoder一贯的作风,使得这题最后只有3人提交,2人pass了系统测试。

Read More...

Y-combinator的推导

published on

今天花费了巨大的努力,自己推导了一遍Y-combinator。发现结果蛮简单的,就是中间遇到了几个障碍消耗了很久,作此文记录一下。

下文代码均使用scheme,不过对其要求不高,本来我对scheme知道的也不多。

引入:什么是Y-combinator

这里直接讲这玩意做什么的吧,历史上是怎么产生的我就没追溯了。

一句话来描述就是,我们可以通过这个玩意编写匿名递归函数。

先看例子吧,举个简单的递归函数:计算阶乘(好像大家都喜欢用这个例子)

(define fact
  (lambda (n)
    (if (equal? n 0)
        1
        (* n (fact (- n 1))))))

注意如果我们要将其写成一个匿名函数,那么我们不可能在函数里面使用fact,那么通过加一个self参数可以解决这个问题。

(define fact
  (lambda (self)
    (lambda (n)
      (if (equal? n 0)
          1
          (* n (self (- n 1)))))))

这样调用的时候写成: ((fact fact) 6),可惜这样写是错的…., 因为上面最后一行需要写成 (* n ((self self) (- n 1)))))))

这样就编写出来了可以匿名递归的函数,但是有一个麻烦的地方是你程序里面要写成(self self),别人调用的时候也要写两遍函数名,这样就还有改进的空间。下面开始改进,我们用F表示这个函数,我们自己希望写成(不包括define F的部分):

(define F
  (lambda (self)
    (lambda (n)
      (if (equal? n 0)
          1
          (* n (self (- n 1)))))))

然后有一个运算符Y,只要执行(Y F),就得到了我们想要的内容。比如

(define fact (Y F))
(fact 6) ;=> this return 720

那么主要的工作就是这个Y长什么样了

Y的推导

注意到由于F的新写法,我们必须把正确的函数传进去,而不是传F自身,而正确的函数就是我们想要的(Y F),我们从这里开始。

(define Y
  (lambda (F)
    (F (Y F))))

这里的Y出现了递归,我们利用上文已经实现过的匿名递归技术来解决这个难题(写起来麻烦没关系,只要这次麻烦过了,呵呵~),将这个东西的名字叫做self-Y好了,于是代码演化成下面这样:

(define Y
  (let ((self-Y (lambda (self)
                  (lambda (F)
                    (F ((self self) F))))))
    (self-Y self-Y)))

哦,我们居然把Y写出来了,可惜这里面还有一点小问题,仔细看一下你会发现这简直就直接死循环了啊… 问题在于这个问题是个递归的,而你想把它展开却没有边界条件…… 这就变成无限循环了。

于是有意思的地方来了,我们可以借用Lazy计算的思路,等到我要用到这个函数了,我再做这个运算,于是变成:

(define Y
  (let ((self-Y (lambda (self)
                 (lambda (F)
                   (lambda (n)
                     ((F ((self self) F)) n))))))
    (self-Y self-Y)))

这样只有当我们给出了F的参数之后,相应的展开工作才会进行,我们的fact函数可以完美运作了。

至此,我们就成功的推导出来了Y的实现。可喜可贺,可喜可贺。当然,对于我来说,只支持一个参数的F函数当然不够满意,利用scheme的语法特性,我们可以改成下面这样。

(define Y
  (let ((self-Y (lambda (self)
                  (lambda (F)
                    (lambda n
                      (apply (F ((self self) F)) n))))))
        (self-Y self-Y)))

使用的例子

最后给一个使用匿名的递归函数的例子, 下面的语句计算了1到7的阶乘:

(map (Y (lambda (self)
          (lambda (n)
            (if (equal? n 0)
                1
                (* n (self (- n 1)))))))
     '(1 2 3 4 5 6 7))
Read More...