分类目录归档:正经

腾讯实习笔试面试小记

四月过了快一半了我却一篇文章都没写,但是我四月要写四篇!包括一篇 Trait 和 Monad。

稍微讲一下最近的事情,起因是有人觉得我蛮不错的推荐我去参加鹅厂的实习。真是谢谢

人家貌似不知道我是专科生,然后我看着每个岗位都写着本科学历心里有点忐忑,本来想不去的,但是想一想自己被刷下来了也是个经验呀。

然后去笔试了。笔试的不怎么样,人家还是 Javascript ObjC Java C++ C 混合起来考的。

很多数学题我都半蒙半做的,比如说最后有一道猴子摘香蕉,以为是自己一直搞不清楚的排列组合题,没仔细看,蒙了个 C_{50}^{2} 结果是这是个 fib 函数……

没想到通过了,让我去面试。

第一个面试官让我选个项目来说,我就说 ika 了,毕竟是料蛮足的。

然后就谈到编译这块去了,编译器,编译优化以及Gradual typing。反正挺顺利的。

然后出了个算法题,两个数集合并,我说了两个方法:

第一个是以一个数集建立二叉查找树,然后第二个数集查找。实际上随后想了想排序然后二分查找就行的,主要是原地。

第二个方法,我想到编程珠玑上面的 bitmap,所以说把数集作为位向量保存,他让我算算大小如何,我算了一下反正蛮大。后来算了一下 int 的话两个数集需要正好 1GB,这方法真臭……问我内存受限的时候怎么办,我就说 hash……嘛,一开始就说 hash 才好吧,半生不熟想要一个时髦的方法来卖弄 Orz
继续阅读

只有咸鱼看不懂的解释器科普 第一步:解析

嗯,这篇文章是我用来介绍自己的解释器 ika 的,不是宜家是乌贼娘!

ika

ika 其实没有什么独创的设计思想都是抄袭来的,所以我觉得要介绍还不如写一篇科普文。

当然这篇科普文会比较简略,毕竟我也扯不出那么多嘛,不过看完了,虽然不能让你闭着眼睛写一门语言,不过该给你的都会给你……吧。

继续阅读

pyPEG 一个很不错的 PEG 文法 Parser 生成器

所谓 Parser(维基百科称作语法分析器,但是我还没见什么人这样说。) ,就是把字符串转化成程序内部的数据结构,所有编程语言,或者 JSON,XML 这种都需要 Parser。一开始人们人肉写 Parser,然后人们崩溃了,尝试提取 Parser 的模式出来,创造了 Parser 生成器,Parser 生成器通过某些规则来生成 Parser,这种规则就是描述语言文法规则的形式文法,常用的是 BNF 以及其扩展。

因为第四次(还是第五次?)重写自己的 Scheme 解析器,看了自己人肉手写的 Parser,虽然经过多次重构,逻辑更清晰一致,但是还是十分冗杂,本来一直在犹豫要不要用 Parser 生成器,最后 Belleve 大神的文章让我下定决心(已成为脑残粉!本来对 Node.js 不屑一顾,现在打算试试了),用,找不到合适的就写。

我之所以那么纠结用不用 Parser 生成器的原因,一是我想让自己这个东西变得纯净,不是依赖别人的轮子,而是从头发明轮子。二,也是最重要的是 Python 最知名的 Parser 生成器 PLY,并不符合我的口味,先不提很久没更新了,更重要的是,PLY 大量使用了反射,破坏了 Python 原本的模式,以前缀为约定,并不美。

中间还在 GitHub 上找到一个同样是 PEG 文法的 Parser 生成器 但是很遗憾,Python 2 Only。最终还是选择了 pyPEG,虽然感觉知名度不太高,但是文档完备,支持 Python 3 ,而且用法也很清新。

因为这个是我用的第一个 Parser 生成器,所以我不能给你讲 PEG 文法好在哪里,不过和 (E)BNF 最大的差别就是,表达式的析取 (expr | expr) 是有顺序的,如果匹配了一个,就会终止匹配,所以 | 在 PEG 文法里面会写作 /。

虽然说是 PEG 文法,其实并不是像别的工具一样,程序员通过 PEG 文法来写,而是用 Python Class,根据规则来进行,这样虽然有一点麻烦和不直观(嗯,主要是写递归规则的时候有点麻烦。),但是因为不像别的库,没有形式化语言和程序语言的连接问题(比如说 Yacc,里面既有 BNF 也有 ),感觉有点清爽。

于是我用了五行就写了一个 S 表达式解释器,但是现在不这样了,因为 Python 有递归深度限制,还有一些特殊情况比如说 Quote。

具体的用法就看文档吧。

函数式编程简介

这是我为了学校的一个活动准备的讲稿,这几天会不断编辑。

伪代码

为了便于理解,这里用类似 JavaScript 的代码,在文中可能不会给出函数的具体实现,但都是容易实现的。

在这里,我尽量使用比较通用的名词,但是因为语言不同也会有差异。

另外,JavaScript 也算是函数式编程语言,所以文中的伪代码在简单的修改以后应该可以运行。

什么是函数式编程?

广义上很多编程语言都是函数式编程语言,比如说 Python、Ruby,而在最近 Java 8 和 C++ 11 都引入了很多函数式特性。

概括说,函数式编程往往有这些特点,而且这些特点是有关联的:

  • “第一级”(first class)的函数,常常使用高阶函数来抽象。
  • 利用递归进行循环。
  • 将程序看作表达式的组合,尽量避免“副作用”——很少使用变量!
  • 惰性求值。

下面就稍微说一说。 继续阅读

诡秘深奥的现代魔法 1.2 下

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

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

1.2.4  求幂

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

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

练习 1.19

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

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

生命,宇宙,以及一切的元

这篇文章想写很久了,这两年稍微了解了一点公理系统,哥德尔不完备定理以及其它的一些杂七杂八的东西总结的一些粗浅的玩意儿。如果看到上面一些名词就猜到我大概想要说些什么的人,基本上也不用看这一篇文章了。

从小时候开始,我注意到一个很有趣的现象,对生活中的任意问题“钻牛角尖”“打破沙锅问到底”,最后总会得到一个无法解决的问题。

“妈妈你为什么一定要我吃蔬菜?” “因为吃蔬菜会让你身体健康。”

“妈妈我为什么要身体健康?” “因为身体健康了以后才能活得长久。”

“妈妈我为什么要活?” “……没有为什么,因为你就要活下去。”

往往会收敛到一个哲学上的“终极问题”上。 继续阅读

关于讨论

在目睹以及亲身参与了网络上的许许多多的讨论以后,我觉得,现在网络那么发达,但是讨论的方式还是那么简陋,许许多多有意义的讨论到了最后都变成攻击和谩骂,所以我一直在设想一种讨论的新的方式。

WikiGit 给了我一点启发,如果一篇文章能不断完善的话那不是很好?相同观点的人去完善同一个论述,论述中发表出自己的论点论据,要反驳的人也逐条反驳。

借由开源软件中常见到的“分支”的概念,也可以想象:一篇论述,如果有人想要在原有的基础上引申发展以及修改,形成了一篇新的论述的话,那就可以在原有的论述上开启一条分支进行修改,之后他的论述就是从原论述引申的新论述。

从用户的角度上来讲,这种讨论似乎是没有什么趣味的,过多的要求严谨会让人心力憔悴,但是我觉得这不是问题,维基百科看起来也没有什么趣味。

下面就是详细的说说这种机制的细节。

继续阅读

一个解释器

在军训的闲暇写下这个文章。

几个星期前的时候,我突然想做一个Scheme 解释器,然后就去做了,尽管我《SICP》第二章还没仔细看完。在经过这辈子第一次天昏地暗的专心Coding 了以后,成品出来了。也是我第一次做出能拿得出手的东西。

但其实这东西技术含量不高,关键的代码只占用了编码时间的20% 剩下的时间都用来写配套的代码,重构和修改代码还有收拾自己的愚蠢Bug。

时间不多,简单说一下结构和核心代码。 继续阅读

Pectin 简单说明

Pectin 是我一个小小的项目,目的是给Tornado 添加一些实用而必要的特性,这些简单的东西我猜已经被人完成过几十上百遍了,不过独立出来成为一个轮子就能方便一些。鉴于有人发邮件来问了,我就稍微的说明一下这个小东西。搭配上项目中本来的说明例子

是什么?

Pectin (果胶)的意思是“胶合层”,而且是很薄的一层胶合层。功能上基本上是通过给Tornado 的类重写方法来实现的。

具体来说,只需要利用Python 的多重继承,应用一些Mixin 就可以实现,也就是说Pectin 其实算是类似“插件”或者“补丁”的一类东西。 继续阅读

Python 所容易忽视的

当你觉得自己Python 入门了,至少不会因为基础的问题而苦恼的时候,有些问题实际上很多人没有注意到。

另外注意,各种内置method (E.g: __getitem__),以及生成器迭代器的使用都是基础。

这是一篇简洁的拾缺补漏的文章,给出一些常见问题——的文章的链接。

另外,有问题可以去看Stackoverflow

独特唯一的万法之法 – 《什么是数学》读书笔记 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。这本书曾是麻省理工的编程入门课程的教材,但是难度一点都不符合“入门”,但我也不清楚是否真的能行,如果没学过编程的人对自己有信心的话可以借来看看。

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

如何进行讨论

定义

讨论不是辩论,讨论的目的在于达成共识而不是获得胜利。但是网络中充斥着辩论,我觉得,进行辩论的人并不是一开始就有意识的去辩论,而是不知不觉中已经在辩论了。

我姑且认为,影响讨论的因素大致上可以分为下面这五点:

  1. 态度
  2. 表述
  3. 信息量
  4. 个人观念
  5. 智力

并且,智力对讨论的影响可以认为接近于0,又不是数学讨论。

理想中讨论的目的就在于交流两个人掌握的不同的信息,最后推出相同的结论。如果不能达成共识,说明个人观念之间有不可协调的矛盾。也就是说3 和4 是目的。

态度

所以,决定讨论能否正确进行的因素还是态度,态度有很多方面,比如说好好的表达,对这个论题的重视和认真程度等等。 继续阅读

一本不存在的小说的收费说明

并没有这本小说,仅仅是模拟了有小说的情况给出的收费说明,来表示我对作品收益的看法。

这本小说是收费小说。你一定很费解,明明是收费小说,为什么能在网站上免费的读到作者自己放出的所有章节内容。

在付费页面,你可以自己制定价格,不管是一块钱还是十块钱,都算购买了这本小说——当然,0 元也算。

那么我为什么说这是一本收费的小说呢?看起来和免费的,同时希望获得捐款的小说一模一样。 继续阅读

小小的理想

算不上什么理想其实。算是可见的目标吧。也不是什么雄心大志。

以前也说过,还申请了域名挂了个WP博客,不过我现在是自然没心力做的。

只是想着,我学习的时候要抄那么多笔记,老师要总结那么多种解题方法……这样的事情随时随地在各地发生。

每年每年学生都要抄他们学长学姐抄过的笔记,看老师的水平笔记的质量也参差,再好的老师也可能有疏漏,实在浪费了太多太多时间和精力。这种浪费真的是不必要的。既然是应试,就应该高效率。

网上要找到好的资料实在太难了,不是少,而是多而滥而没有系统。如果用类似Wiki的方式,大家一起来维护多好。当一个网上笔记,有丰富的图示,树状结构的安排,甚至相关的视频,论文等资源的连接,那该有多好。

有这样想法的肯定不少,但是考上大学了以后自然就抛到脑后。如果我考上大学了会尝试着去干的。很多东西 比如高考我们都改变不了,但是总能做点什么的。

不应如此编程

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

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

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

告别在概率的岔口

偶然点开浏览器,发现你已经离开。

一开始没有什么实感,很遥远。

然后我以为我会悲伤,但只是茫然。以前和我说过话开过玩笑帮助过我的那个人永远没了。

之前是有的,现在一下子怎么会没有呢。玻璃碎了,留下的还是玻璃,瓷器碎了,留下的还是瓷器。人没了,就没了。

我不懂你所想,无法体会你的心情,甚至无法因为你的离开而悲伤,所以只能说再见了。

我是相信量子永生的。

生命游戏的较少步骤方式

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

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

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

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

单单记录细胞

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