Skip to content

Category Archives: 生活志

《简明数论》的简明笔记(下)

x²≡d (mod p)的问题。 ax²+bx+c≡0 (mod p)可通过配方转化。 (2ax+b)²≡b²-4ac(mod p) d是p的二次剩余当且仅当方程有解,否则为二次非剩余。 既约剩余系中恰有(p-1)/2个二次剩余和(p-1)/2二次非剩余。 d是二次剩余当且仅当d(p-1)/2≡1 (mod p),否则模为-1。 于是两二次剩余或两二次非剩余的积为二次剩余,二次剩余与非剩余的积为二次非剩余。 Legendre符号当d是p的二次剩余、非剩余及p|d时分别取值1、-1、0。 Gauss二次互反律的主要应用似乎是用来简化及计算Legendre符号的值,以求解二次同余方程。 但在编程中可直接利用来计算,复杂度是相同的。 Jacobi符号具有与Legendre符号相同的互反律,但似乎就与二次同余方程没什么关系了,目前还没看到应用。 关于同余方程的Lagrange定理的内容是同余方程的解数不超过它的次数。 可用归纳法证明,很优雅。 n次同余方程有n个解,当且仅当f(x)的次数小于等于p,且f(x)除xp-x所得的余式模p恒等于0。 对于次数大于p的高次同余方程,总存在一个次数不大于p、首项系数为1的等价同余方程,即是xp-x除f(x)所得的余式(再将首项系数化为1)。 例外是余式模p恒等于0,不妨认为此时的等价同余方程就是xp-x。 事实上,简化高次同余方程也可避免做多项式除法,可用Fermat小定理xp≡x (mod p)直接降低次数。 模为素数幂的同余方程的解法看上去很强大,但是前提是需要先解出模为素数的同余方程啊!难道除了直接验证没什么通用的解法?26节先放下。

MSRA实习纪(一):面试篇

(我目前正在面试 Facebook 的 winter intern,所以还是先赶快把这段欠了很久的面经写出来以攒人品吧。) 我面试的是 MSRA 的 Innovation Engineering Group (创新工程组),面试官是一位 RSDE II。他在面试之前跟我用电话和邮件确定了电面的时间,而后我的电话就非常准时的如约而至了。(题外话:Facebook 的电话就似乎没有那么准时。) 面试时不仅需要接电话,还需要进入一个网页版的聊天系统,这个系统可以即时对话,还有虚拟的白板可以用文本或图像写写画画,之后的写代码环节就是在这个白板上进行的。 接了电话,寒暄过后就进入聊项目阶段。首先是对我简历上列出的项目经历做了些蜻蜓点水式的随机提问,应该是为了确认基本的真实性。而后,面试官问我这些项目经历中最大、最复杂的是哪个,我回答说是大一至大二暑假时跟着翁凯老师做的那个嵌入式Linux的项目。于是就开始深入地聊这个项目,比如说,为什么会选择AT91RM9200做CPU。这个问题我之前从来没想过,因为芯片选型这些重要决策当时都是翁凯老师确定的啊。于是便磕磕绊绊地说了些计算能力和外设接口满足需求、性价比高、省电、CPU频率可调之类的。 聊过简历上的项目后,又问了和编程语言相关的问题,既有客观题又有主观题。我记得的有C#里面的Property是干什么用的,动态语言和静态语言的区别,C#属于动态语言还是静态语言——最后这个问题比较tricky,传统上来说C#是根正苗红的静态的面向对象语言,但C# 3.5和4.0增加了一些比较“动态”的特性,但我在面试当时其实只知道这些动态特性的存在,并不了解具体有哪些。(应该还有别的很简单的客观题我记不起来了。) 下一个阶段是时间最长的,基于一个假想的项目来提问各种问题。大概是说有一个唱片公司在全国各地开了很多家买唱片的连锁店,连锁店内用电脑展示歌手、唱片、歌曲等信息,顾客可以用店内的电脑完成浏览、查询、试听等操作。首先问的是这样一个系统的架构,我答就是有一个中央服务器,店内的电脑连接服务器获取信息什么的。(不详细写了我当时的答案了,时间久了也不可能记那么清楚。)然后问到说现在这样一个系统性能很差,应该怎么办。我答性能问题首先一定要profiling,看到底哪里是性能瓶颈才能对症处理,比如说服务器性能差、网络性能差、客户端性能差需要优化的东西就完全不一样。面试官补充说道是网络带宽的问题,店里面都只有拨号网络,问我应该怎样优化。我回答了几方面:一是可以削减传输的内容,例如音视频功能在带宽不够的前提下可以考虑不予提供;二是可以对传输的内容进行压缩,压缩有有损和无损两种,分别可以应用于图像、音频、视频内容及文本内容;三是可以在客户端做缓存,下载过的东西就不要重复下载;四是网络实在很差的情况下可以考虑不用网络,假设信息更新频率不是那么快,可以考虑每周一次把数据更新刻成光盘快递给所有分店(这个有点是为了展示自己具有“think outside the box”的能力故意说的)。然后面试官就问,缓存的话可以怎么实现。我就答了算法可以用LRU、MRU什么的;数据结构根据储存在内存还是硬盘上可选用 hash table、B+ tree  等。然后面试官又非常详细地追问了一下只用内存的LRU具体怎么实现,我就详细地答道可以用一个 linked list 和一个 hash table 来做什么什么的,互相之间怎么着用指针指来指去怎么添加怎么删除什么的。 最后一个阶段是实际写代码,在那个可以实时看到对方打字过程的聊天工具里写,不要用IDE、编译器。先是让选语言,说我简历上列的那些个语言里除了Haskell 面试官不会其它可以任选。我考虑自己多年OI到ACM/ICPC的经验就选了C++。结果呢,要求实现一个排序。说起来比较囧,其实我最不会写排序了。高中的时候搞OI,其他用Pascal语言的同学都把快排背得滚瓜烂熟,而我则很轻松地用标准库里的qsort函数搞定(至今怨念OI比赛不准用STL);大学里搞ACM/ICPC更是有STL里好用的sort函数用啦。所以说虽然说要让我敲一个二分图匹配、平衡二叉树或者最小费用最大流什么的我都能基本做到随手就来,对于自己好多年都没有写过一次的排序我还是比较没信心。最终我选择了时间复杂度达到理论最优而又写起来相对不容易错的 merge sort 来写。由于第一次在这样的环境和场景下写程序,写的时候极其紧张(一紧张连new和delete都忘了怎么用了直接图省事写了句“int temp[n]; // C99”),代码写得磕磕绊绊,不过似乎最终还是一遍就写对了。还是感谢OI和ACM/ICPC为我打下的扎实的coding基础啊。 最后面试官问我还有没有什么问题要问他,我什么问题都想不到就说没有。不过我后来想到,也许应该最后问他一下他对我面试的表现总的评价怎么样,对我个人能否给出什么建议这样的问题。即便面试官回避问题或者干脆不答,也许也能有一点谨慎好学的印象分。如果面试官答了那就有可能是真知灼见的建议。 和预先通知的一样,这场面试总共耗时整整一个小时。 我后来意识到,我在面试中踏入的最大的误区是,在面试时被问到问题完全没必要等面试官话音刚落就回答。这是出于日常生活中两人交替说话时的行为习惯。但我现在觉得完全没必要在面试中也这样,对于比较复杂无法在一两句话内答完的问题,尤其是主观问题,完全没必要把自己第一感觉得到的答案直接说出来。可以直接跟面试官说我想一下,然后花个三十秒考虑一下各种可能性,分几点来回答,然后再有条理地说出来,这样可能会给人感觉更好。 悟到的另一条面试经验是,由于面试官问的很多问题都会直接基于你的简历中的内容。确认简历中内容的真实性也肯定是面试官的一项重要任务。所以有必要在面试前把自己的简历好好过一下,考虑一下每一项能力、经历等描述有哪些可以提问的角度,预先自我演练一下。比如说,把自己简历中从前做过的项目仔细过一下,不仅要想清楚自己在其中的作用和贡献应该怎样表述和展示,还有必要想一下整个项目在选型、架构等重大决策有哪些、为什么这么做,尽管那些决策自己可能并没有参与做出。 好了,这篇就是这样,敬请期待今后的“MSRA实习纪”系列。将来还可能会有Facebook面经以及我真心希望能有的Facebook实习纪哦!

《番茄工作法图解》书评

(首先一个小小声明,我手中的这本《番茄工作法图解》不是自己花钱买的,而是图灵公司送的样书,所以本篇书评的独立性其实可以存疑。) 2010年2月底,我看到 The Pragmatic Bookshelf 上全场五折的活动,就非常开心地去买了久闻盛名的 Pragmatic Thinking and Learning 这本书。正待买单时,想到现在这个全场五折的活动实在是优惠幅度很大,也许应该看看还有没有什么想要的书顺便一起买了。于是就在他们的新书中浏览,看到了这个我一向很喜欢的技术出版社竟然出了一本讲时间管理的书,于是一下子就很好奇,又去了解了一些背景资料后,就带点冲动地买下了这本 Pomodoro Technique Illustrated(从而正对活动策划者的胃口)。说来也巧,《番茄工作法图解》译者大胖同学第一次读到这本书的原稿还是我给他发的电子版呢。 Pomodoro 这个词是意大利语中的“番茄”的意思。番茄工作法的要义,在于将任务在时间维度上的不确定性分解成固定的“时间盒”(time box),只专注于一次集中精力25分钟。在每个时段都高度集中精力的前提下,用花在任务上的时间盒数量而非完成的工作量来度量成果和效率。以我的经验,这种方法在手边有多项优先级接近的的任务需完成时最有效:通过时间盒的轮换,任务的切换变得规律而有序,既不会因为其它同样很重要的任务而分心,也不会让任何一项任务迟迟不开始。而在有一项任务优先级明显高于其它任务时,例如这一天就只有一个程序要编或一篇东西要写的时候,番茄工作法的功效就只剩下提醒你有规律地工作一段时间就休息一下而已了。其实,番茄工作法不是很像操作系统任务调度中的时间分片(time slicing)机制么? Pomodoro Technique Illustrated 是我所知的最优质的讲番茄工作法的书了,也是我读过的讲时间管理的书中最好的一本。这本书的主要优点在于,不仅讲明了“什么”以及“怎样”践行番茄工作法,还通过广泛的文献引用及综述阐述了“为什么”番茄工作法有效。在知其然且知其所以然的前提下,方法就从死板的教条变成了自身知识体系的一部分,可以根据自身的情况灵活运用了。书中全彩印刷的精彩的思维导图及其它卡通风格的可爱插图也为全书增色不少。 我自己在试图“灵活运用”番茄工作法的时候,遇到过一些应该避免的误区。首先,应该将番茄工作法的计时系统严格地仅应用于学习和工作中,而不要试图将休闲娱乐也纳入到番茄钟的管辖范围。我在尝到番茄工作法的甜头后,曾经想用番茄钟来规划自己休闲娱乐的时间,给上网闲逛之类的行为严格计时。这表面上看来很好,但实际却可能会大大消减“番茄钟”与“全神贯注”二者之间的反射习惯。给休闲娱乐做些规划很好也很有必要(例如 reverse calender 的方法就值得推荐),但将它与用来提高精力集中度的番茄工作法混为一谈则可能得不偿失。第二点是,应该对番茄钟之间的间隔休息时间严格计时。我一般习惯在这三至五分钟的时间从座位上起来走动一下,接杯热巧克力或者泡杯茉莉花茶,窗外远望一下。但这段时间如果没有计时提醒的机制的话,很容易一下子就用掉了十几分钟。这样每工作二十五分钟就休息十几分钟的方式自然是超没效率的。所以,我在非常需要集中精力的时候,会严格地每工作二十五分钟休息五分钟,这样时钟的分针和休息或工作的情境就有了严格的映射。 番茄工作法也不是完全没有缺点。我发现自己在应用番茄工作法一段时间后,似乎长时间集中精力的能力有所下降。也就是说,每集中精力二十五分钟后,就会自然而然地期待能休息一下,不休息就会觉得精力下降。如果这种现象越发显著的话,那还真是一个挺严重的问题。为此,我接下来打算尝试改变一下番茄钟的时长,每工作五十分钟休息十分钟。不过这是不是一个好主意还真得试过才知道。 我近些年已经完全不读翻译版的技术图书,一方面是因为中文技术图书市场在品位上存在着较大的滞后,另一方面则因为大部分中文技术图书的翻译质量实在是惨不忍睹。这样读原版书读久了,脑海中针对编程技术建立起的概念体系也都自然地用上了英文的语汇,很多时候遇到中文技术语汇(例如“锁存器”)完全反应不过来说的是什么。 如果把大胖翻译的这本《番茄工作法图解》也看作技术图书的话,这还是我几年来第一次读翻译版的技术图书。我对它的翻译质量的评价是:相当好。我之前读过全书的英文版,且对书中涉及的内容知识体系有所了解。在拿到出版社寄来的样书时,我还特别在留意翻译上的可以改进之处。结果完全没有发现可以察觉到的误译——这根据我对中文技术图书翻译之普遍质量的了解,属于相当罕见的质量水准了。译本的一项贴心之处是,将书末参考文献中有出中文版的书目都标注了中文书名及出版社,鉴于这本书的参考文献列表相当有用,这真的是可以给读者节省工夫呢。 如果非得要从个人角度吹毛求疵的话,我是希望译文的风格能在可意译之处更大胆一些。 例如,本书序言中提到的作序者的妻子“Sia”被翻译为“阿霞”,这一下子就让我眼前一亮,可惜之后的人名翻译没有保持这样讨巧的风格。像是书中每章开头处出现的卡通角色“黄瓜”和“洋蓟”(我之前都从来没听说过这种蔬菜啊),若是我操刀翻译的话会将其译成“瓜仔”及“菜头”。 就是这样了。希望番茄工作法能同样提升你的工作效率哦!

MSRA实习纪(零):简历篇

我从2011年1月25日起在 MSRA (Microsoft Research Asia) 的 Innovation Engineering Group 实习,为期约六个月。在此期间,我会在遵守保密协议、保守商业秘密的基础上,对这次实习经历做一些心得体会的总结。以下是本系列的首篇文章,主要是写了我在正式发出实习申请之前写简历时收获的自我认识。 2010年11月27日,我看到刘未鹏(pongba)发的一条tweet,说他们组要招实习生,为期至少六个月。后来我又收到了未鹏的邮件,问我能否推荐实习生人选。 我知道未鹏在MSRA工作,但当时并不清楚他具体在哪个组。但是我当时的想法是,不管未鹏在哪个组,我相信他的选择,他所在的那个组就是我想去的那个组。我对未鹏的了解始于高中的时候,那时刚刚学了C++,于是就像很多C++程序员一样不可救药地沉迷于这门其创造者都需要别人来教他怎么用的语言的奇迹淫巧中,于是就如同艺术领域的初学者第一次踏入罗浮宫一般,带着崇敬和仰慕半懂不懂地阅读未鹏当时名为“C++的罗浮宫”的博客中 template metaprogramming 之类的C++高级技巧。 然而,高中时的我从未鹏的博客上收获的绝不仅仅是C++的语言技巧。正是从未鹏的博客上,高中的我初次领略了理论计算机科学的美:到现在,我还清楚地记得自己初次阅读《康托尔、哥德尔、图灵——永恒的金色对角线》一文时,被高密度的既极度新鲜又激动人心的概念轮番轰炸(哥德尔不完备性定理、Lambda演算、停机问题、Y Combinator、不动点定理、对角线方法、罗素悖论⋯⋯),那种醍醐灌顶般被震撼到几乎忘记了呼吸的美妙感受。——这就是我在计算机科学领域的真正启蒙吧。 也正是从未鹏的博客上,我理解到了一个程序员最重要的工具是他的大脑,任何fancy的语言、框架、IDE以及各种 buzzwords 的重要性都远不及他的学习方法、思维能力、行为习惯、心智力量的重要性,而正是这些“内功”层面的东西决定了卓越程序员与普通程序员的分野。 (扯一句题外话,刚才提到了我在计算机科学领域的启蒙始于未鹏的博客,而我在有关但并非完全等同的软件工程领域的启蒙则始于某个记不清楚的日期逛北京王府井书店时,出于不可知的原因央求同行的姑父给我买下了一本2004年3月第1次印刷的《程序员修炼之道——从小工到专家》,即 The Pragmatic Programmer: From Journeyman to Master 的中译本。同时,那次经历也是我第一次见识到用一张薄薄的卡片刷一下就能付款。) 接到未鹏发来的邮件时,我自己还并没有找实习的打算,于是我通过论坛等方式把这条实习信息传达给了浙大ACM集训队的现役及往届队员,还给一些我觉得可能会想实习的学长打电话询问,但大家都纷纷表示很难抽出整整六个月的空来。 后来,由于一些莫名其妙的动机,我产生了想离开杭州一段时间的念头。于是我就跟未鹏说我找到可以推荐的人选了,其实就是我自己,呵呵~接下来的当务之急就是写一份简历。坦率讲,这还是我第一次需要写份正襟危坐的简历呢。写之前觉得很容易,不就是把自己干过啥会干啥一条一条列出来么。没想到写了又写改了又改花了大约三天左右才写好第一个让自己满意的版本。(我当前版本的简历可以在这里访问到。) 写了一份正式简历才知道,尽管从前并没有人找我要过这个,但写简历的过程还是给人挺多启迪的。比如说,简历的第一个Section一般都是叫“Objective”,也就是简述你个人在事业和求职方面的目标。我以前并没有仔细思考过这个问题的答案,所以在这三天里一边写其它的部分一边思考,最终写上了一句“Build tools that make programmers’ life more fulfilling, including mine”。——这肯定并不是最终的答案,也许以后的经历会告诉我这个目标定得过于宽泛或者过于狭窄或者并不那么适合自己,但我非常高兴自己能在大三上半学期而不是更晚的时候对这个问题的答案进行了仔细的思考,并给出了一个让当时的自己满意的表述。 对于我来说,在事业方面的困扰从来都不是选择太少而是选择太多:从大方向上来说,不管是 Computer Science 还是 Software Engineering 都可以说是感兴趣且有一定基础;从更细分的 topics 来考虑的话,programming language theory, compiler construction, functional programming, […]

Authentic Happiness 读书总结

0. 缘起 始于3月31日的凌晨,止于4月6日的黄昏,我投入地阅读了这本名为 Authentic Happiness (台译《真实的快乐》)的书,它的主题是“积极心理学 (Positive Psychology)”(另译“正向心理学”或“正面心理学”,不过我更喜欢“积极”这种提法)。 我对心理学的了解开始于高中时阅读的《精神分析引论》《梦的解析》等弗洛伊德的著作,在读这本书以前也大体上局限于他创立的精神分析学派。可是后来我逐渐意识到,弗氏的学说固然有其历史意义(也许也蕴含有限的现实意义),但是把它作为一种指导个人生活的思想,却是我犯下的一个极大的错误。(我最近购买了《弗洛伊德批判》一书,打算藉此进一步清除心中的流毒,也许等我读完会专门撰文展开。) 最早了解到 Martin Seligman 这位学者以及他参与创立的“积极心理学”这一心理学分支,是在他以此为题的一次 TED 演讲中(顺便强烈推荐下 TED.com,绝对是开阔眼界提升思想的大宝库)。当即我就在 Kindle Store 上购买了他的书并放入 to-read 列表,不过直到最近完结掉其它好几本书以后才终于开始阅读,初读一两章便相见恨晚。这是一本让我感到思想被颠覆的书,这种感觉在我的读书历程中极其罕见。读的过程中,我在 Evernote 软件里用英文做了几十K的摘抄和笔记,以下是我整理那些笔记时用自己的话复述全书的读书总结。 (需要注明的是,本书第11、12两章,特别地讲了积极心理学在“Love”和“Raising Children”两个方面的应用,我在读的时候跳过了。因为这两方面的快乐,一个我当前足够满足,另一个则还为期遥远。为了看上去更有体系,话题相近的第10章“Work and Personal Satisfaction”也被略过了,也就是说完全没有总结 Positive Institution 这个话题。) 1. 基本问题 心理学的中心话题一度主要是关于如何治疗心理疾病 (mental illness) 的(这也正是弗洛伊德作为一名心理医师 (psychiatrist) 的切入角度),而积极心理学则聚焦于如何使正常人拥有更好的生活。事实上,即便从心理疾病的角度去考虑,积极心理学也提供了有效的预防手段。积极心理学期望的成果是快乐 (happiness or wel-being),研究对象包括积极的情感 (positive emotions)、积极的特质 (positive traits) 和积极的组织 (positive institution),这也正是本书的三个部分分别所讲述的。 什么是快乐呢?这个问题并不仅仅是简单的享乐主义理论 (simple hedonic theory) 能解释的。快乐也并不仅仅是快乐的感觉 (feelings)。简单的享乐是能引发快乐的“快捷方式” […]