Posts

Static VS Dynamic 静态动态对比 一门语言称之为静态或是动态，指的是它在什么时候进行类型检查。 ML VS Racket 可以有两种看法： ML 某种程度上是 Racket 的子集，Racket 支持的写法更多，因为一部分 Racket 中允许的表达式不会被 ML 的静态检查通过。比如 if 语句的两个分支返回不同的类型。 Racket 里的变量其实不是“没有类型”，而是只有“一个类型”。 datatype theType = (* 所有的变量类型都一样，所以没有必要标注或是检查 *) Int of int | (* 变量所持有的值是有不同类型的，即运行时值是带有所谓标签的 *) String of string | Pair of theType * theType | Fun of theType -> theType | ... Static Checking 静态检查 静态检查处在语法分析之后，程序运行之前，所以称之为“编译时检查”（但这跟语言用编译器还是解释器没有关系）。静态检查如何作用是语言定义的一部分，有的语言做得多有的语言做得少，给定检查规则，也可以自己实现工具来做期望的检查。 实现静态检查的方式主要是类型系统，但类型系统只是实现静态检查的方式，而不是静态检查的目的。静态检查的目的是防止错误，但这个错误的范围很有限，比如大多数静态检查都不会检查数组是否越界，静态检查也没法告诉你某个地方你应该用乘法但是你用了加法。它能防止的是，字符串不能与整型相除，某个类型不能做某些事情。 相比于动态检查（即给值加上标签，运行时进行检查），静态检查其实拒绝了一部分并不会出错的程序。这里值得讨论的东西在于，首先，你如何定义错误。 考虑一个简单的“错误”： 3 / 0，你可以在下面这些时间点阻止这个“错误” Keystroke-time： 在编辑这段代码的时候阻止，意味着你写下 3 / 0 就已经是一个错误 Compile-time： 当静态检查器“看到”这段代码的时候阻止，意味着这段代码不应该出现 Link-time： 当发现这段代码会被调用的时候阻止，意味着调用这段代码是一个错误 Run-time： 当执行这段代码的时候阻止，即被 0 除这个运算是一种错误 Even-later 执行这段代码没有错，但如果用到了这个运算返回的结果（可以是一个表示未定义的标识，比如 undefined），才是一种错误（比如把 undefined 用作数组下标） 甚至用返回的结果来做计算也没错，3 / 0 应该表示正无穷，同样的 tan(π/2) 也表示正无穷，你可以让它参与计算（事实上， Racket 里 (/ 3.0 0.0) 就返回 +inf.0） 第二个值得讨论的就是如何定义正确，怎么判断类型检查是符合语言定义的。 ...

Ruby 部分 Ruby 有如下重要特性 纯面向对象(pure OOP)：Ruby 中的所有值都是对象，每个表达式执行后都得到一个对象（有些面向对象语言不是这样，比如 Java 中的整型、布尔型、浮点数字面量都不是对象） 基于类的面向对象(class-based)：每个对象都是类的实例。类决定了对象所拥有的方法。（有些语言也不是基于类的，典型的如 JavaScript 是基于原型的） 混入(mixin)：多重继承（C++）与接口（Java）之间的一个折中。Ruby 中每个类都只有一个父类，但是可以有任意数量的混入，不像接口，它们可以定义方法（而不只是要求某个方法要存在）。 动态：Ruby 允许在任意对象上以任意参数调用任意方法，还可以在运行时改变类和对象的属性 反射(reflection)：可以在运行时知道对象的类是什么，有哪些方法 闭包（block and closure）：block 几乎就是闭包并且可以方便地用来使用库中的高阶函数，由于众多迭代函数的存在，Ruby 中也几乎不会显示使用循环。Ruby 中也有完整的闭包（proc） 脚本语言（script language）：脚本语言没有一个精确的定义，它意味着能够快速地写出简短的程序，方便地操作文件和字符串，较少考虑性能 流行于 Web 应用开发：Ruby on Rails 是一个非常流行的服务端框架 Class-Based OOP 基于类的面向对象 面向对象有如下几条规则： 所有变量都是对象的引用 给定一个对象，可以通过调用它的方法与之交流，也可以被称为发送消息 每个对象都有其私有的状态，只有对象自身的方法才能访问和修改状态 每个对象都是类的实例 类决定了对象的行为，类包含了方法的定义，它决定了对象如何处理它收到的调用（消息） 在另一些面向对象语言比如 Java/C# 中，大部分的规则都被实现了，然而 Ruby 给出了一个更完整的实现。 例如： 一些字面量在 Java/C# 中不是对象，违反了规则1 Java/C# 中有 public 的属性，违反了规则3 Calling Methods 调用方法 e0.m(e1, e2, ...) 与其他语言类似，首先得到表达式 e0, e1, e2… 的结果 obj0, obj1, obj2, … ，然后以 obj1, obj2, … 调用 obj0 的方法 m。方法调用另一种普遍的说法是消息传递，即向 obj0 传递了消息 m，附带 obj1, obj2, … 为参数，这种说法“更面向对象”，因为我们不关心接受者 obj0 是怎样实现的，只关心它能够接受并处理消息 ...

Racket 部分 Racket 是一门由 Scheme 而来的动态类型、函数式的语言 P.S. 其实比起 Scheme，它有类和对象 Syntax 语法 Racket 在语法方面比较特别，有两个特点：括号和前缀表达，例子见后文。 Racket 里的所有东西都可以分为两种情况： 原子类型 (atom)： 字面量： #t, 11, “hi”, null, etc. 变量名：x 关键字： define, lambda, if, etc. 一个在括号中的序列 每个序列中的第一个元素会对后面的元素产生作用 如果第一个元素不是关键字且整个序列是表达式的一部分，那就把它作为函数来调用 （包括 +, -, *, / 也都是函数） 整个序列表示了对应的抽象语法树且没有二义性 Delayed Evaluation And Thunk 延迟计算 语言设计上的一个关键语义：子表达式什么时候被求值 对于 Racket, ML 以及大部分语言来说，当调用函数时，传入的参数表达式在执行函数体前被求值。但如果这个参数是一个函数，那在被调用之前，函数体的代码是不会被执行的。 (define (my-if-bad x y z) (if x y z)) ; 无论 x 真假，y 和 z 都会被求值 (define (my-if x y z) (if x (y) (z))) ; 当 y 和 z 是函数时，只会求值其中一个 这种用来延迟计算的函数称为 thunk ...

Introduction 背景简介 这份笔记是我学习华盛顿大学开设的《编程语言》时记录整理，这门课程主要通过介绍三门语言来讲授编程语言的方方面面，以及不同的语言特性对编写程序的影响。对于熟悉常见编程语言比如 Java/C/C++/Python/JavaScript 的开发者来说，这门课能够开阔眼界，从而了解语言的表达力和局限性。 目前该课程仍然在 Coursera 上有开设：https://www.coursera.org/learn/programming-languages 笔记中不会过多介绍基本语法，只谈一些重要的特性。如有需要也可参考我学习时的课堂讲义和完成的作业：https://github.com/novakoki/Programming-Language Categories 编程语言分类 教授将语言按照主要的特性分成四类，其他的特性会穿插介绍 函数式 (Functional) 面向对象 (Object-Oriented) 静态 (Static) ML Java 动态 (Dynamic) Racket Ruby Essential Parts 编程语言组成部分 语法 (Syntax) 语义 (Semantic) 习惯（Idioms）: 常用的一些利用语言特性的套路，比如 C++ 的 RAII 库（Libraries）: 现成可以用的库，以及如操作文件这种没法自己实现的功能 工具（Tools）: 编译器（Compiler）, 命令行（REPL）, 调试器（Debugger）, etc. 这里重点看一下语法和语义的差别。经常看到有人会说某个语言的新特性只是语法糖而已，没有什么实质性作用。 ML 部分 Static Type 静态类型 ML 是一门静态语言，静态是指它在运行前进行类型检查 val x = e (* 称之为一次数据绑定， e 为一个表达式 *) 然而我们要看到的不仅仅是这样一句语法描述，还要了解背后的语义，即类型检查和求值。 val x = 1 (* x 的类型为 int，值为 1 *) (* 每做一次数据绑定，当前环境都会更新，这个环境即作用域，后面会详细讨论 *) val y = x + 2 (* y 的类型为 int, 值为 3 *) val z = y + "3" (* 类型检查失败， + 不能用于 string 与 int 之间 *) val z = w (* 类型检查失败，当前环境中找不到 w *) 关于静态与动态，之后将与 Racket 对比来看，这里只提一些 ML 的特性。 ...

之前在公司花了大约一个星期的时间把负责开发的会员卡模块从 Vue1 升级到了 Vue2，中间经历了不少坑，其中大部分是因为原本的代码偏离 Vue2 的最佳实践比较多（主要是数据流是双向还是单向），另一部分是因为 Vue2 底层的变化（引入了 Virtual DOM）。 升级的缘由及考量 升级的考量无非两个方面，是否满足现在和以后的需求，升级的好处和代价分别有多大。 需求 首屏服务端渲染的需求，由于存在两套技术栈，一套是 PHP 模板，一套是前后端分离的 Vue 和 Play for Scala，当从旧有页面切换到 Vue 编写的页面时，会有明显的空白加载时间 组件校验的需求，当时还是官方推荐的 vue-validator 还不支持这一点，但在它 3.0 的计划中，并且只支持 Vue2。 这也是一个很大的考量因素，即 Vue 周边的一些东西最后可能都会根据 Vue2 来开发和迭代。 一些已有的 bug，但在 Vue2 中修复了。比如 v-model 的 number 修饰下， input 为空时会变成 0（后面看到这个 bug 在 Vue1 中也修复了，但并不能排除一些小 bug 可能不会再考虑 Vue1）。 好处 除了解决上述需求和问题之外，我暂时没有找到一个让我从 Vue1 升级到 Vue2 决定性的优势。 代价 迁移所需要的时间，这个时间不真的开始改代码其实很难估计，当时我用 vue-migrate-tool 检测出大约几百处需要修改（这里不包括 Vuex），我预计的时间是两到三天，实际花了一个星期。而且在升级过程中，项目是无法完整运行的（为什么说完整？因为只要一个模块一个模块改，就能保证有一部分是可运行可测试的）。以及包括后续升级其他也用 Vue1 开发中或开发完的项目所需时间。 项目迁移完成之后的风险，即使有良好的单元测试也无法保证和之前 Vue1 版本表现是真的一致了 学习成本，这个比起 Angular 是好多了，大多数变化都在 API 改名字之类的语法层面，而且大多数变化是在做减法，在减去一些不常用的或是累赘的 API，但其实 Vue2 改动了一些底层的东西（主要是 Virtual DOM），导致语义风格上其实有一些变化了（我认为是开始偏向 React 了） 服务端渲染方面，就不仅仅是前端的问题了，整个前后端的架构也要动，涉及到后端和运维方面的改变。要考虑是不是加一层 Node 作所谓后端的前端，可行性和整个项目进度是否允许等等。（最终这个项目没有用 Vue 的服务端渲染，而是用 Play 直出一部分公共的组件（侧边栏、顶部导航等），再加载 Vue 的 JS 文件去渲染剩下的部分） 总结一下，如果没有找到一个促使你升级的决定性因素，升级要谨慎，可以考虑还在开发中的以及后续项目尽量遵循 Vue2 一些最佳实践，少用 Vue2 废弃的东西。 ...

笔试 选择题忽略 问答题： 用原生JS实现一个接口，能够用Ajax上传文件并显示上传进度，上传完成后接收一个来自服务器的json数据 实现一个三列布局 如何防范CSRF（跨站请求伪造） 请列举减少HTTP请求数和资源文件大小的方法 Reference 列举实现跨域请求的方法 一面 一上来先是自我介绍，在这个过程中，面试官会看你的简历 Q：CSS和JS熟悉哪个？ A：JS Q：浏览器端的JS包含哪几个部分？ A：ECMAScript+DOM Q：DOM包含哪些对象？ A：Node对象，然后继承下来的有Document,Element,Text，还有想不起来了 (常用的：Node(Document, Element, CharacterData(Text, Comment, CDATASection), DocumentFragment), Window, Attr, NodeList, Event, etc. ) Q：JS有哪些基本类型？ A：Number, String, undefined, null, 还有引用类型的 ( 这里我少答了Boolean，然后我以为问的是数据类型。ES6 新增了 Symbol ) Q：基本类型和引用类型有什么区别？ A：赋值的时候基本类型按值，引用类型按引用，就是基本类型会复制一份，引用类型就是一个新的指针。函数传参的时候都是按值传递. Q： var obj = {a : 1}; (function (obj) { obj = {a : 2}; })(obj); //问obj怎么变？ ``` A：外面的obj不变，因为里面等于让局部的obj指向了一个新的对象 // 下面两题是因为我简历有写我会C++ Q：C++ 的引用类型是怎么样的？ A：C++ 里面的引用相当于一个变量的别名，对引用做操作也会影响该变量 Q：JS 和 C++ 有什么区别？ A：面向对象不一样，C++ 是类式继承，JS 是原型链式。C++ 在函数式方面没有JS来的强。JS 没有 C++ 的一些高级特性，比如模板、泛型。 Q：实现一个左边定宽右边自适应的两列布局，要求使用浮动和flex两种方法 A： ...

What: 在写我的blog-generator的时候，遇到了传说中面试经常考的对象复制的问题。 在用Jade模板的时候，要用同一个模板渲染出不同的文章，就需要有不同的locals。 一开始的想法是，用Jade里面的include markdown，这样只要文件名做变量就可以了，然而事实上Jade并不支持动态include。 于是只能改用先用marked解析markdown文件为字符串然后填充进去，假设有如下内容 post.jade article !{article} //- 这里是解析markdown后得到的字符串，会带有很多转义符号，所以用 !{}的变量表达 locals.json { "articles": { "title": "path", "title1": "path1" }, "article": "balabala..." } 那么在JavaScript中就可以 gulp.task('template', ()=>{ var locals = require('./locals.json'); for (var title in locals.articles) { /* 这里做markdown解析并改变locals中article的值 */ gulp.src('./post.jade') .pipe(jade({ locals: locals })) .pipe(rename(`${title}.html`)) //gulp.dest只能指定输出的目录而不能指定文件名，需要rename = require('gulp-rename') .pipe(gulp.dest('./posts')); } } ) 然后一切都是由异步引起的问题了，为了符合gulp的风格，我用stream来读取markdown文件的内容 var stream = fs.createReadStream(locals.articles[title]); var data = '';stream.on('data', (chunk) => { data += chunk;}); stream.on('end', () => { locals.article = marked(data);}); 因为显然这个过程是异步的，所以我用一个闭包来存每次迭代的title gulp.task('template', ()=>{ var locals = require('./locals.json'); //这里我一度以为locals也会是在闭包环境里的 for (var title in locals.articles) { ((title, locals) => { return () => { var stream = fs.createReadStream(locals.articles[title]); var data = ''; stream.on('data', (chunk) => { data += chunk; }); stream.on('end', () => { locals.article = marked(data); //这里是会影响外部的locals的 gulp.src('./post.jade') .pipe(jade({ locals: locals })) .pipe(rename(`${title}.html`)) .pipe(gulp.dest('./posts')); } ); } })(title, locals); } 事实上这样最终只会产生相同的页面，即最后迭代的那一次。 意识到了其中的问题所在之后，我继续做了些修改 ...

what: Q: <div></div> <p></p> div { position: fixed; height: 35px; } p { margin-top: 15px; } 问div距离窗口上边的距离是多少？ A: 15px why: 在没有指定left，top等的情况下，它们的默认值为auto，意味着div的位置应该放在其静态位置， 即在其正常文档流中的位置。 那么问题转变为，div的静态位置应该在哪？这里涉及到一个外边距层叠的问题，p元素和body有15px的margin， 在没有清除样式的情况下，浏览器默认body与html之间有不定大小的margin，这两个垂直距离上的margin会发生层叠， 即最终body与html之间有了15px的margin，所以div就和窗口上边有了15px的margin how: BFC: 深入理解BFC和Margin Collapse 如何解决外边距叠加的问题？

理论 流程 分割成很多个同类型的子问题(Divide) 递归地解决这些子问题(Conquer) 合并子问题的答案(Combine) 主序定理(The Master Method) 对于递推式： $$T(n)=aT(n/b)+O(n^d)$$ 有如下结论： $$T(n)=\begin{cases} &O(n^d)&\text{if}&d\gt\log_ba\\ &O(n^d\log n)&\text{if}&d=\log_ba\\ &O(n^{\log_ba})&\text{if}&d\lt\log_ba \end{cases}$$经典算法 整数乘法(Karatsuba Multiplication) 归并排序(Mergesort) 逆序数(Counting Inversions) 最近点对(Closest Pair) 矩阵乘法(Strassen’s Subcubic Matrix Multiplication) 快速排序(Quicksort) 选择问题(Selection)

快速排序是一个典型的分治(DIVIDE-AND-CONQUER)算法. QuickSort(array A,length n) if n == 1 return pivot = ChoosePivot(A,n) Partition A around pivot Recursively sort 1st part Recursively sort 2nd part 而决定这个算法效率的关键就在于枢纽点(pivot)的选取，因为这直接影响到分割(partition)的好坏。最坏情况下，即每次选取的枢纽点都为最大或最小的数，则时间复杂度为 $\theta(n^2)$ .而如果能够奇迹般地每次都选择了中位数，时间复杂度就为 $\theta(n \log n)$ .以上都为理想情况的分析，而对于排序来说，效率的衡量在于比较次数。以下对各种枢纽点的选取方法做一个比较次数的测量，数据为10000个0~9999之间的整数。 选取首尾元素 首：162085次比较 尾：164123 这种方法的效率取决于输入数据的预排序程度，如果是已经有序的状态，则效率很低 三数中值分割法，即选择下标为第一个、最后一个、中间的三个数的中位数作枢纽点 138382 效率很高 随机选取枢纽点 测试了五次： 148958，149598，163443，161712，161399 随机选取枢纽点无疑是安全的，因为不可能每次都选中最坏的情形。但是另一方面，随机数的生成也耗费了时间，对实际排序的时间造成了影响。 所用的数据： http://spark-public.s3.amazonaws.com/algo1/programming_prob/QuickSort.txt 参考资料： http://www.nowamagic.net/librarys/veda/detail/2397 参考代码： #include<iostream> #include <fstream> #include <cstdlib> #include <ctime> using namespace std; int sum = 0; int pivot(int* A,int lo,int hi){ // 三数中值分割法 // int a = A[lo]; // int b = A[hi]; // int c = A[(lo+hi)/2]; // if(( (a>=b) && (a<=c) ) || ( (a>=c) && (a<=b) )) // return lo; // if(((b>=a)&&(b<=c))||((b>=c)&&(b<=a))) // return hi; // if(((c>=b)&&(c<=a))||((c>=a)&&(c<=b))) // return (lo+hi)/2; //首尾 //return lo; //return hi; //随机 //srand((int)time(0)); //return lo + rand()%(hi-lo);} void swap(int& a,int& b){ int tmp = a; a = b; b = tmp; } void QuickSort(int* A,int l,int r){ if(l == r+1) return; // for(int i = 0;i < 10;i++) // cout<<A[i]<<" "; // cout<<endl; int p = pivot(A,l,r); //cout<<A[p]<<" "; swap(A[l],A[p]); int i = l + 1; for(int j = l + 1;j <= r;j++){ if(A[j] < A[l]){ swap(A[j],A[i]); i++; } sum++; } swap(A[l],A[i-1]); QuickSort(A,l,i-2); QuickSort(A,i,r); }