分类目录归档:正经

腾讯实习笔试面试小记

四月过了快一半了我却一篇文章都没写,但是我四月要写四篇!包括一篇 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 的启发。(参见第一条评论,是我搞错了) 继续阅读

我已落榜,感觉不是特别糟糕

是的,高考失败了。尽管根据降分政策,我所用来保险的一个大学或许还有些渺茫的希望,这件事还没开始办,但是失败就是失败。

满分600 分,语文96 分,数学59 分,外语51 分,生物99 分(但是生物有降分,算作94 分)。 总分刚好 300 分,本科分数线 331 分。保险的大学可以加20 分,即使这样也差11 分(不过政策上还有降分投档,但是根据往年记录并没有降分投档过)。

最遗憾的是数学。在高考前我数学估计已经在90 分左右了。我本身做题慢,所以一直需要手表控制节奏,然而在考试前手表被我摔坏了。随后考试时候因为把握不了时间,心彻底紊乱,低级错误让我丢了至少20 分。这并不是自己为失败找的借口。

我是努力过的,那么多数学题,十几分几十分上升的数学成绩,翻烂的词汇手册,考前一个月恶补生物写的满满的笔记本。这些不会因为高考成绩而化为乌有。

接下来要做的,无非就是挣扎一下看看能不能上本科,不行的话就上专科,专升本。说起来也没什么。

想读的书还是读,想做的事还是要做。

 

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

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

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

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

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

如何进行讨论

定义

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

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

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

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

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

态度

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

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

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

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

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

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

青春期的郁躁疾走

这本来是在S1 马区发的帖子。帖子前还注明不要转发到Twitter 或者 饭否。因为耻度太大。仔细想想耻度也不是特别大,我还是自己转发到Blog 上吧。

0

初中时候单恋过一个女生(顺便小学时候也朦胧的喜欢过一个),毕业以后快三年了,没有对任何女生喜欢过。倒不是初中时候喜欢的魅力多大(说实话我连长得什么样都忘了,听说留长头发了,有点惆怅,大概有男朋友了吧),我自己倒是有点渴望想喜欢别人,但是到底没人给我喜欢。当然也可能是高中这几年患上了交际惰性,再加上个人原因不断变化学校,同学的名字大多忘了,至少没有能记住名字的妹子。

1

自己不知不觉似乎养成了一个自卑的性格。我在这里说自卑,是前几天和一个朋友聊天他形容我的。但是我自己感觉,我对自己的认识是比较客观的,我没必要妄自菲薄,我对自己的评价有足够的依据,但说出来就是自我暴露狂了。

小学(还是初中?)的时候就在想,长大以后一定不要找长得漂亮的女孩子,况且长得漂亮的女孩子一定不会喜欢我的。现在想,我这种废柴也不会有生物喜欢上的吧。就算有什么妹子被蛋疼星人灌了迷/魂/药(S1你的敏感词有点神经)喜欢了我,如果让我分裂一个我出来的话,一定会很认真的阻止她。

2

我很理想,对爱情的想法还是最理想的那种,你爱我我爱你,两情相悦,不顾其他任何,和初恋结婚到白头偕老,躺在藤椅上晒晒太阳追忆时光。
概率上来说遇见那么好的爱情最后还能修成正果,或许中彩票以后拿钱四处砸妹子还要现实点。
继续阅读

小小的理想

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

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

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

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

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

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

不应如此编程

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

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

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