算法中的增长率标记法及含义

  • T(N) = O(f(N)) 表示T(N)的增长率小于等于f(N)
  • T(N) = Ω(g(N)) 表示T(N)的增长率大于等于f(N)
  • T(N) = θ(h(N)) 表示T(N)的增长率等于h(N)
  • T(N) = o(p(N)) 表示T(N)的增长率等于p(N)

当且仅当T(N) = O(f(N))且T(N) = Ω(f(N))时，T(N) = θ(h(N))。

算法

常用数学公式

最近复习算法和数据结构，记录下一些数学公式，顺便了解下latex。

指数

X^{A}X^{B} = X^{A+B}

\frac{X^{A}}{X^{B}} = X^{A-B}

(X^{A})^{B} = X^{AB}

X^{N} + X^{N} = 2X^{N} \neq X^{2N}

2^{N} + 2^{N} = 2 * 2^{N} = 2^{N + 1}

对数








级数
















模运算

如果N整除A-B，即(A-B)/N为整数，则认为A与B模N同余，记为A≡B(mod N)。例如：11≡7≡3(mod 4)


数学

node.js在项目中应该放在哪个位置

用了node.js这么长时间，对node.js擅长和不擅长的领域算是比较清晰了。

进程与线程

进程是计算机中已运行程序的实体，一个进程可以包含多个线程，多个线程共同某个进程的工作。一个CPU同一时间只能处理某个进程的任务。所有的线程共享着计算机的内存，没有做任何的隔离。但是，为了保证某些数据的安全，会在内存中使用互斥锁（Mutual exclusion，缩写 Mutex）及信号量（Semaphore）。互斥锁允许且只允许同一时间只有一个线程操作共享内存，其它线程必须等待该线程处理完成后再对该内存块进行处理；信号量的逻辑与互斥锁相似，只是同一时间允许N个线程对共享内存进行操作，当名额满了之后其他线程必须等待。
这篇文章很好的解释了进程与线程的关系，以及他们对CPU和内存的使用方式。

阻塞I/O和非阻塞I/O

写程序，操作文件、读写数据库和请求第三方服务等都是常有的事，这些都是I/O，I/O是非常耗时间的。

当程序采用阻塞I/O的策略时，线程遇到I/O操作就会等待，直到I/O操作结束，再继续执行，例如PHP语言，就是采用这种机制。那么PHP采用这种机制，如果一个请求由于I/O操作导致线程被阻塞，是否会影响其它请求的响应时间呢，答案是不会的，看多线程与单线程里面的解释。

当程序采用非阻塞I/O的策略时，线程遇到I/O操作时，会通知另外的线程去处理，然后主线程挂起一个回调函数，并继续执行其他的任务，不会做任何的等待，直到这个I/O操作完成，另外的线程将结果返回给主线程，主线程调用之前挂起的回到函数，继续执行接下来的操作。

node.js就是采用非阻塞I/O和事件轮询的方式。我们知道Javascript单进程单线程的语言，但是所谓的单线程只是说他执行任务时用的是一个线程，我们称之为主线程，既然有主线程，那就说明肯定还有其他线程，是的，就是任务队列，专门负责处理I/O操作，当node.js的主线程发现了一个异步行为，他会将该任务挂起，将他提交给任务队列去处理，直到任务队列处理完该任务并返回处理结果时，主线程再调用处理该结果的回调函数继续执行。通过这样的方式，主线程不需要等待任何I/O操作，使主线程的资源利用率成倍提升。

单线程与多线程

上面的内容中提到，PHP采用了阻塞I/O的方案，该方案会等待I/O操作结束再继续执行接下来的代码。那么这样的方式，如果同时多个请求进来了，由于I/O阻塞的原因会不会出现某个请求执行了很久，导致后面的请求响应慢的问题，答案是不会的。因为PHP采用了多线程的处理方案，当有一个请求进来的时候，PHP就会开启一个线程来处理一个请求，一个请求对应一个线程，那么一个请求所出现的问题是不会影响到另一个请求的（CPU和内存富足的情况下）。PHP的这种方案使得各线程之间相对安全，不会互相影响，但是弊端也是明显的，当I/O出现时，PHP始终处于等待状态，这导致CPU的利用率低，并且，一个请求进来就创建一个线程，这对内存的要求较高，因此，在高并发的情况下，需要横向扩展PHP服务器以满足高并发的需求，很多时候都是因为线程过多导致内存不足的问题。

node.js的非阻塞I/O和事件轮询机制很好的优化了这个问题，通过非阻塞I/O提高了CPU的利用率，并且单个线程对内存的需求肯定比PHP少得多，因此node.js更能扛得住高并发。但任何事情都是双面的，有优点就必然有确定，单线程的javascript，如果某个请求出现了异常，就会导致整个进程不用了，当然，我们有解决方案可以让程序在出现异常的情况下自动重启。还有就是如果你在node.js的主线程执行了高CPU运算的操作，那将是灾难。因为在主线程中，除了I/O是异步的，其他运算都是同步的，一个高CPU运算的操作会导致后续的请求全部被卡住。

因此，node.js虽然被很多人追捧，但是，如果用的不好，还不如写PHP。node.js更适合做任务的分发者而不是执行者！！！

架构图

如果我有一个团队，我更愿意这样去搭建一个后端的服务，node.js不太适合出现在数据层，除非真的只是增删查改而没有其他高耗CPU的操作，node.js更适合作为前端的路由去分发请求，他自身不应该出现过多的CPU操作，如果有，请用fork。

node.js

通过RSA实现SSH免密登录及mosh替换SSH避免断网断线

1.SSH是我们常用的连接服务器的工具，频繁的输入账号密码会很麻烦，通过RSA的公私钥机制，可以实现免密登录。方法是将客户端的公钥放到服务器的~/.ssh目录下，并重命名为authorized_keys；

2.SSH工具采用的是TCP连接，在网络断开的情况下SSH就会自动断开，于是终端会变成假死状态，必须关了重开，很麻烦。mosh使用UDP连接，不用担心断网重连的问题。mosh的使用，必须拥有服务端，即除了客户端需要安装mosh外，服务端也需要装mosh，之后通过命令mosh root@<your host>即可完成连接。

ssh

数据结构的一些基本概念

抽象数据类型

抽象数据类型(abstract data type, ADT)是一些操作的集合。对诸如表、集合、图和它们的操作一起可以看作是抽象数据类型。

表

数组

使用数组实现表结构时，在元素的增删比较麻烦，例如在0位增加一个元素，需要将所有元素后移一位，删除一个元素，需要讲所有元素前移一位，时间复杂度位O(N)。

链表

链表实现表结构时，增删操作的时间复杂度位O(1)。假设链表有5个节点，当需要在2和3之间增加一个节点时，只要创建一个新的节点空间，让2的next指针指向这个新创建的节点，再让新创建节点的指针指向3这个节点，则新增操作完成。删除某个节点时，讲节点的前一个节点的next指针指向当前节点的下个节点，并删除当前节点即可。

双向链表

双向链表与链表的差别在于，双向链表出了有next指针指向下一个元素，还有prev指针指向前一个元素，形成了双向链。

循环链表

循环链表的特别在于，最后一个元素的next指向第一个元素，而第一个元素的prev指向了最后一个元素。在双向链表中，这两个指针指向的都是null。

栈

队列

数据结构

javascript实现快速排序 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'use strict';
/* jshint node: true */

const len = 100;
const ary = new Array(len).fill(0).map(() => Math.floor(Math.random() * len));

let ret = (function fastsort(ary) {
	if (ary.length <= 1) return ary;

	let k = Math.floor(Math.random() * ary.length);
	let l_ary = ary.filter((item, index) => (index != k) && (item < ary[k]));
	let r_ary = ary.filter((item, index) => (index != k) && (item >= ary[k]));

	return fastsort(l_ary).concat(ary[k]).concat(fastsort(r_ary));
}(ary));

console.log(ary);
console.log(ret);
javascript

C语言中整型的二进制表示

C语言中，正数的原码、反码和补码都是一样的，但是负数的的表示是其补码，补码是反码+1。

int类型是4字节，表示-2^31 ~ 2^31-1

我们设定一个变量60，看它各运算后的结果

60的二进制表示为00000000 00000000 00000000 00111100

~60，我们对60取反，得到这样的二进制11111111 11111111 11111111 11000011

首位的比特位是1，表示这是一个负数，C语言中的负数是补码表示，我们需要讲补码转为原码才知道该二进制在C语言中表示什么编码

补码是反码+1，因此反码为11111111 11111111 11111111 11000010

原码为反码除符号位外其他位求反，因此，原码为10000000 00000000 00000000 00111101，即-61

因此~60 == -61

60 << 2，我们对60左移两位，得到这样的二进制00000000 00000000 00000000 11110000

这是一个符号位为0的二进制，表示的结果为正数，240

C

git踩坑记录

我在我的机器上能够通过配置ssh key访问github管理代码，但是在公司的服务器上不管怎么配置都不行，实在搞不懂了，然后同事送我这行代码，只要输一次账号密码，然后敲上这句，搞定，下次不用再输入账号密码了。

1
git config credential.helper store

修改了了一堆文件后，偶尔会出现某个文件只是为了调试而加了console之类的代码，这时候你想把他还原

1
git checkout <file name>

git

Javascript异步调用顺序执行方法

在使用异步回调的时候，我们经常会接住async等模块的帮助，但是有时候我们仅仅只需要一个异步调用同步执行的方法，似乎没必要使用那么多的代码，那么，异步调用顺序执行的方法如果自己写要怎么写呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
(function() {
    var fns = [].slice.call(arguments);

    fns.map(function(fn, i, fns){
        fns[i] = function () {
        	var args = [].slice.call(arguments);
            fn.apply(null, i + 1 === fns.length ? args : [fns[i + 1]].concat(args));
        }
    });
    
    fns[0].call(null);
}(function(next) {
    setTimeout(function() {
        console.log('method 1');
        next('method 1', 'complete!');
    }, 200);
}, function(next, a, b) {
    setTimeout(function() {
        console.log(a, b);
        console.log('method 2');
        next('method 2', 'complete!');
    }, 100);
}, function(a, b) {
    console.log(a, b);
    console.log('end');
}));

// method 1
// method 1 complete!
// method 2
// method 2 complete!
// end

一开始我一直处理不好next和data混合在一起的处理方法，直到我看到了一段类似的代码才醒悟。当前函数执行完之后调用next函数时，只有实际数据部分，但是下一个函数的定义却有一个next的第一参数，因此，我们需要讲原有的函数做替换，让他可以正常的接受当前函数传递过来的参数，并且执行的时候加上next参数。

javascript

我是如何构建我的后端服务器的

最近有空的时候一直在整理自己的后端代码，希望整理出一套较为通用的代码，可以运用到大多数的项目中去。现在的项目基本都是前后端分离的，后端只负责提供restful api接口，根据不同的项目，和前端会有不同的集成方式，例如app的后端，基本就是一个独立的项目，我个人的博客后端，我会考虑使用nginx做一个转发，当接收到/到请求时，转发给前端页面处理；当接受到/service请求时，转发给后端处理，这些请求基本上都是前端的ajax请求，避免了跨域的麻烦。后端的代码中我们只要用一个简单的use方法做转发可以将/service的请求转回原地址了。

我的项目目录：

1
controller // 存储控制器的文件夹
library // 存储通用代码的文件夹
- error.js // 通用错误定义
- helper.js // 系统级通用函数定义，例如jwt令牌生产和校验
- middleware.js // 中间件定义
- util.js // 常规通用函数定义，一般以lodash或系统内置的util模块为基础，md5等自己常用的方法
model // 存储mysql、mongo及redis数据模型的文件夹
- mysql // mysql
- mongo // mongodb
- redis // redis
- index.js
node_modules // node.js的模块
router // 系统路由
- v1.js // 版本1的路由
- v1_1.js // 版本1.1的路由
- index.js // 通过use方法调用各版本路由
service // controller和model之间的业务逻辑代码
test // 单元测试文件夹
.gitignore
app.js // 启动文件
config.js // 配置文件
package.json // 模块配置文件
readme.md

所有的请求都会经过路由再到达控制器，路由是所有代码内容的第一关，特别是在app项目里面，url一旦发布就难以修改（客户端也可以通过默写热修复的方法处理），url地址的设计好坏对于项目维护很重要。我在定义路由的时候，会有一个总的index.js文件，app.js只要引入这个文件即可，项目就可以访问到所有版本的api。

index.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
'use strict';
/* jshint node: true */

const Mdl = require('../library/middleware');
const Ctr = require('../controller');
const Router = require('koa-router');
const v_1 = require('./v1');
const v_1_1 = require('./v1_1');
const v_admin = require('./admin');
const router = new Router();

// restful api v1
router.use('/1', v_1.routes(), v_1.allowedMethods());
// restful api v1.1
rotuer.use('/1.1', v_1_1.routes(), v_1_1.allowedMethods());
// manage api
router.use('/admin', v_admin.routes(), v_admin.allowedMethods());

router.all('*', function*() {
	this.status = 404;
});

module.exports = router;

v1.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'use strict';
/* jshint node: true */

const Ctr = require('../controller').v1;
const Router = require('koa-router');
const v1 = new Router();

// 增加用户
v1.post('/user', Ctr.User.create);
// 删除用户
v1.delete('/user/:user_id', Ctr.User.delete);
// 查询用户信息
v1.get('/user/:user_id', Ctr.User.read);
v1.get('/user', Ctr.User.read);
// 修改用户信息
v1.put('/user/:user_id', Ctr.User.update);

在我的controller service model三个文件夹下，都会有一个index.js的文件，controller会被路由引入，controller又会引入service，service又引入model，最终到达数据库。我比较习惯用一个单独的大写字母来标示一些特殊的集合。

1
2
3
4
const U = require('../library/util');
const H = require('../library/helper');
const S = require('../library/service');
const M = require('../library/model');

一开始用这种方法的时候，总会担心别人的批评，因为这种看不出是什么鬼的定义很容易被喷，有点过不去心里的坎，不过后来想想，规则就是人定的，为什么一定要遵守别人的规则，自己觉得好久即可。以前做PHP用think PHP框架也有类似的语法。用一个字母表示一个集合，确实是蛮实用的。

service作为服务层，承载着所有增删改查的业务逻辑处理，虽然有模型层把控数据格式，但是模型层很多时候只会返回诸如Validation error之类的单一错误提示，这样的提示很难判定是哪个地方出了异常，所以在数据进入模型层之前，我会对参数做断言判断，而断言的异常情况，会统一定义在library/error.js文件里。

登录验证的服务层

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
exports.verify = function*(account, password) {
  assert(H.isAccount(account), 'ACCOUNT_INVALID');
  assert(U.isPassword(password), 'PASSWORD_INVALID');

  let rs = yield M.Mysql.User.findOne({
    where: { $or: [{ mobile: account }, { email: account }] },
    include: [{
      model: M.Mysql.UserProfile,
      through: {
        attributes: ['gender']
      }
    }]
  });

  assert(rs, 'USER_GONE');
  assert(rs.password == H.generatePassword(password, rs.password_salt), 'PASSWORD_ERROR');

  let access_token = yield H.signToken(U.extend(rs, { password_salt: null }, U.extend.RN));
  let refresh_token = yield H.signToken({ user_id: rs._id }, refresh_token_expires);

  return { access_token: access_token, refresh_token: refresh_token };
};

error.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
'use strict';
/* jshint node: true */

exports.ACCOUNT_INVALID = {message: '账号无效', code: 400};
exports.PASSWORD_INVALID = {message: '密码无效', code: 400};
exports.PASSWORD_ERROR = {message: '密码错误', code: 400};
exports.USER_GONE = {message: '用户不存在', code: 410};
exports.PARAM_INVALID = {message: '参数错误', code: 400};
exports.MOBILE_EXISTS = {message: '手机号码已存在', code: 409};
exports.EMAIL_EXISTS = {message: '电子邮箱已存在', code: 409};
exports.OBJECT_ID_INVALID = {message: '无效的查询ID', code: 400};
exports.EMAIL_INVALID = {message: '电子邮箱格式错误', code: 400};
exports.MOBILE_INVALID = {message: '手机号码格式错误', code: 400};
exports.BOOK_GONE = {message: '书籍不存在', code: 400};

有了assert，于是代码里必然要出现try {} catch(e) {}的代码。每个接口都写一遍try catch会很麻烦，既然error可以统一由error.js定义，那么统一处理也是可以的

登录验证的controller

1
2
3
4
5
6
7
8
exports.verify = H.f(function*() {
	let account = this.request.body.account;
	let password = this.request.body.password;

	let ret = yield S.Auth.verify.call(this, account, password);

	this.send(200, ret);
});

正常来讲，verify这个方法只要返回一个Generator function即可，为了把try catch的代码提取出来，我包多了一层函数用来处理异常。这个函数定义在我的library/helper.js文件里面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
exports.f = function(func, error) {
	error = error || {};
	return function*() {
		try {
			yield func.call(this);
		} catch (e) {
			let obj = error[e.message] || E[e.message] || {message: C.debug ? e.stack : '未知异常', code: 500};
			if (typeof obj.message === 'string') {
				obj.message = {
					code: 1,
					message: obj.message
				};
			}
			this.send(obj.code, obj.message);
		}
	};
};

函数的名字主要是为了简短，又想不出太好的命名，就直接给了个f，函数的两个参数，第一个就是传入进来的generator function，第二个是自定义的错误释义，因为有时候我们需要返回的错误解释也许不是error.js里面定义的那个，或者说有时候同样是401的状态码，但是可能是不同情况导致的，例如有可能是令牌过期，也有可能是用户修改了密码，要求重新登录，于是你必须给出不同的释义。

模型层基本用的都是orm框架，较好的把控了数据问题，关系数据都存在mysql数据库，较少的数据存mongo，例如书籍这类树形的数据。

node.js
,