分类目录归档:笔记

诡秘深奥的现代魔法 1.3 下

虽然是下,但是因为只剩一个小节了所以没什么好说

1.3.4 过程作为返回值

过程作为返回值,意思是在函数里面用 lambda 动态的生成一个函数作为返回值,作为一种抽象工具来说是十分强大的,在后面的例子里也能看到。

这一小节的实例是牛顿法,可以逼近方程的解,我猜计算器解方程就用得是这种方法。

在这个例子里面,“高阶函数做抽象”这一节里面学到的方法基本上都被用到。

后面的习题看着虽然吓人,之前还吓退了我,不过硬着头皮去做会发现不难。

练习 1.45

这一题要写代码不断试做实验,但是因为用了前面的习题的代码所以要保证前面的习题的正确。

实验以后可以看到:(平均阻尼次数 -> 开次方数)

  • 2 -> 4
  • 3 -> 8
  • 4 -> 16
  • 5 -> 32
  • ……

显然是对数的规律,k次开方最少需要 \lfloor lg(k) \rfloor 次平均阻尼,lg 代码懒得写,是从这里复制的。

诡秘深奥的现代魔法 1.3 上

用高阶函数做抽象

终于来到这里了,前面的大都是开胃菜,我们常说的函数式编程最大的特点就是,函数也像一个数据一样可以被放进数据结构里面,也可以作为参数传入,作为返回值,在程序中动态生成,一个常用的行话叫做:把函数作为一等公民。

这个特性能让程序的表现力大大提高,以至于很多新旧语言都吸纳了这个特性。我们从现在开始真正学习抽象这个极其有力的魔法,到了这本书后面你就会觉得,自己动手让没有 OO (面向对象)特性的 Scheme 语言支持 OO 实在是一件简单的事情。有人想对 C 这样做,最后出来的是 C++!玩笑玩笑。

言归正传,书中也讲了,高阶过程就是将过程作为参数或者返回值的过程,在数学里面很高端地叫做“泛函”,还有一个高大上的数学分支叫做“泛函分析”,我是完全搞不懂啦。

继续阅读

诡秘深奥的现代魔法 1.2 下

这个系列好久没写了,刚刚依靠光速浏览看到了第三章的结尾,于是回顾以前的章节开始认认真真读第二遍了。看以前的写的内容感觉就像习题解答一样无趣,于是多一点理解少一点习题,有趣的习题当然还是要写的,没写出来的习题也应该在这个仓库里面,如果没有的话大概是我不会做。

1.2 过程与它们所产生的计算

1.2.4  求幂

这里介绍了求幂的一种\Theta(\log(n))时间界。特别舒爽。下面的习题里面的迭代计算过程的求幂比较简单,后面的练习 1.17 也没什么难点。

对数步骤的求幂已经很让人奇异了,下面还有对数步骤的斐波那契数。

练习 1.19

这一题别看说什么变换族,什么让你证明,实际上挺容易的。

a\leftarrow bq+aq+ap
b\leftarrow bp+aq
.
继续阅读

独特唯一的万法之法 – 《什么是数学》读书笔记 0-0

又挖了一个读书笔记的坑。

虽然都是极其重要的著作,但是《什么是数学》无疑比《SICP》更重要和基础。

标题中 0-0 代表的是第一遍阅读的读书笔记,第一遍阅读不纠结太难的地方,也不做习题,可能会跳过很多章节也不按书中的顺序来,主要是概览。因为不算真的在仔细地读,所以就当作第0 遍吧。

“独特唯一”很明显是取自书中对数学的形容;“万法之法”意思是,所有像魔法一样的东西,根底里都是数学。

希望能和《SICP》 结合起来来说,比如说数学归纳法和算法的循环不变式……不过《SICP》 并没有看到讲循环不变式。

莱布尼茨在他的二进位算术中看到了宇宙创始的原像,他想象1 表示上帝,而0 表示虚无,上帝从虚无中创造出所有实物,恰如在他的数学系统中用1 和0 表示了所有的数。

看优秀的教材一定要一页一页仔细看,我之前对前面的学过的内容直接跳过,然而刚才一页页读发现这才有收获,很多序言中表明是“高深”的部分也不用害怕,先看看,如果能勉强看懂就不要放弃。

感觉看这本书最浅的乐趣是看里面数学史,然后就是理解现成的概念,再然后是理解美妙的证明——或许之后就是完成里面的习题和思考题吧。投入的思索越多最后获得的乐趣就越大。

诡秘深奥的现代魔法 1.2 上

1.2 过程与它们产生的计算

菜鸟的读书笔记,如果有常识性错误和非常识性错误请毫不留情的开口指正!

1.2.1 线性的递归和迭代

能耐心看这个语焉不详的文章的读者都知道递归和迭代是两种循环的方式。但是SICP 中说道,一个递归的过程中也有递归和迭代的区别,这就是文中所说的:递归计算过程,和迭代计算过程,我们通常说的递归和迭代只是从语法上而言的,书里说的是计算过程,一个递归计算过程需要维护一个栈来储存信息,所以所需的空间是线性增长的(空间复杂度O(n)),但是迭代计算过程对空间的要求是常数级的(O(1)),是维护着一系列“状态”,当调用自身的时候,其会释放空间,所以会保持函数的递归深度为1。
所以如果要用递归过程的话,如果可能最好用迭代计算过程,当然,编译器或者解释器要支持尾递归优化(当一个过程是迭代计算过程,那么就可以说是尾递归的),能够在递归中不断释放栈,比如说我喜欢的Python 就不支持,仁慈的终生独裁者先生还讲了一堆说程序员最好不要用递归balabala,不过这种实用主义的哲学正是Python 的魅力所在。

迭代计算过程就是那种其状态可以用固定数目的状态变量描述的计算过程,而与此同时,有存在一套固定的规则,描述了计算过程在一个状态到下一个状态转换时,这些变量的更新方式;还有一个(可能有的)结束检测,它描述了这一计算过程应该终止的条件。

注:书中说常见语言的递归过程,即使是尾递归也往往需要线性储存空间,但是现在C 是支持尾递归优化的。并且即使编译器没有尾递归优化也可以用手动 goto 语句来实现。 继续阅读

诡秘深奥的现代魔法 1.1

改名叫《诡秘深奥的现代魔法》,“诡秘深奥”是书中第一章形容程序设计语言的词语。

注意!翻译过程中有一些错误,可以看之前先根据勘误表改正,注意勘误表中有一条关于微分方程的勘误(dy/dt 被勘误表改成 dy/dy)可能是错的(原文的方程可能是对的),修改的时候注意。(update: 我发邮件过去确认了我的猜测是对的,之后可能会被更正。)

这一小结说的内容比较基本,讲述了程序设计和Lisp 里面的一些基本原理。

正则序和应用序

我是这样理解正则序和应用序的,正则序是先展开后求值,应用序是先求值再展开。正则序更常用的术语是惰性求值,我比较熟悉的Python 中的生成器就是惰性求值的例子,其他语言也有类似的,似乎都是受Lisp 的启发。(参见第一条评论,是我搞错了) 继续阅读

诡秘深奥的现代魔法 – SICP 读书笔记 0

明天高考成绩出来以后,这个读书笔记如果没坑,说明我还好。我现在心情压抑的转移注意力。

《计算机程序的构造和解释》(Structure and Interpretation of Computer Programs ,简称SICP,豆瓣链接维基词条)这种好书,很早我就买了,几年了我常常带在身边想要翻看,结果只看了一点点,但是因为常常带在身边,有的时候用作鼠标垫什么的,前几页就磨损的很厉害,我总是很自豪地说我把SICP 翻烂了。

实际上Scheme (SchemeLisp 的一个方言,也是SICP 的教学语言)也就写了个hello world。这本书曾是麻省理工的编程入门课程的教材,但是难度一点都不符合“入门”,但我也不清楚是否真的能行,如果没学过编程的人对自己有信心的话可以借来看看。

现在,在高考成绩发表前的忐忑中,我打算一边看,一边连载读书笔记和习题解答。当然,也有些有趣的摘抄。 继续阅读

CellCraft

昨天无聊的时候开始YY,想到《凉宫》里面那个宇宙战争游戏,于是想想如果自己来搞一个类似的会怎么搞,又想到EVE里面的各种气死牛顿的设定,于是YY出了个这个东西。

这是什么?

基于我贫乏的物理知识储备空想出来的战略游戏,不过虽然是空想出来的,但是技术上实现似乎没什么难点。

基本规则

玩家操控一个或多个Cell(按理说是宇宙飞船,但为了减轻美术负担,就抛开太空背景吧,假象画面是白茫茫的背景下一堆球型的细胞在互殴,如果认为是淋巴细胞发射抗体的话也没错),夺取充斥在宇宙中的资源(Resource)。 继续阅读

不应如此编程

最近因为学习的关系很少碰代码。

最近看了一下自己写的代码,是一个链表,看到一行(链接),代码的意思是增加数据结构的计数器,我看到这一行的时候却疑神疑鬼了,因为这被包含在初始化一个节点的函数中,但还有其他的一些函数,比如说在特定位置插入,我写的时候或许会忘了一件事:“计数器已经加过了” 而再加一遍。

仔细检查了一下这里应该没出现问题,其他操作都没有动计数器,依赖计数器的函数工作也很正常,然而让我感觉不好的并不是可能出错,而是我看到这行语句以后不确定别的地方没有干不应该干的事情。如果我有底气,看到这行代码心里也就能保证这行代码只出现在这一个函数里面。 继续阅读

生命游戏的较少步骤方式

这种文章在各位大大看来一定是班门弄斧了,而且说的东西其实也是特别简单的,只是记录一下,如果有更好的希望说一下。

程序员了解了生命游戏的规则以后大多会直觉的想到这样一种方式,建立一个二维数组,每一个数组里面存放这True或者False,当然也不一定是数组,二进制文件什么的,反正是矩阵。

直觉的方式,深蓝色是处理中的,浅蓝色是处理过的

反正我一开始也是这样想的,不过很容易就想到为什么要用一个矩阵来一遍一遍的轮呢,可以光靠细胞之间的位置来确定,也就是说光记录细胞的坐标就好了。

单单记录细胞

下面详细说一下,感觉很多地方还有可以简化的地方,靠计算细胞间的距离(坐标差的绝对值)很容易确定一个坐标的生死。 继续阅读

一些Vim 插件

常用的那些我就不说了。插件最好用 Vundle 管理,方便的仿佛就像改革开放一样。

Raimondi/delimitMate 括号补全,很多补全脚本都有问题,这个不错

Lokaltog/vim-powerline 漂亮的状态栏

FencView.vim 自动识别编码,是中国人就装!(XD)

还有这个,是修改过的Python 缩进插件。

推荐这个文章,这个Blog 有很多不错的插件。

脑内高手之:昨晚睡不着YY了个P2P网络

小时候我问电脑老师,为什么普通网页不用P2P技术老师讲了一堆意思是不方便什么的。
昨天看到有人传言饭否有可能又要关了,虽然我不怎么信的,但是还是想到了这东西,于是睡觉的时候空想了一下,不过感觉这方面应该有很多大牛在研究也肯定有成果了而且我只看过P2P的维基百科,很多机制其实是绕了远路的,所以这篇稚嫩的文章仅仅是我为了凑Blog更新的一篇口胡而已。

纯属意淫。当小说看也行。

这个网络是什么样子的?

一个没有中心服务器的纯PeerToPeer网络,用户之间传递的不是图片啊什么的而是可读的文本信息。用户之间有一种类似微博客的结构,也就是你广播的信息只有关注了你的人能接收,你也只会接收你关注的的人。

这个网络有什么用?

避免审查?虽然想这么说但是有上百种更加简单的方法来避免审查,而且按照我的幻想IP都是赤裸裸的保存在Sqlite的,于是这只是没有实际用途的门外汉空想而已。 继续阅读

将Vim 默认剪贴板设为系统剪贴板

在vim 里访问系统剪贴板,你先要按“””,然后按“+”最后按“p”或者“y”,烦得要死,今天打算解决这件事,一开始思路是用map,结果用的不熟练出现了诡异的状况,只好求助Google 大神了,大神给我指明了一条命令:

写在~/.vimrc 或者win下面的~_vimrc就行。

Update: 刚刚在Linux下面试了试,不行,查到了这个Wiki Accessing the system clipboar

如果不行试试看

PS:最近放暑假,不对是寒假 了,整天沉迷在代码和天际省。